recherche d'un element dans hashtable

Bonjour,
Pour en finir avec le hashtable, et merci à ceux qui m'ont aidé hier.
Le principe de recherche lorsqu'on fait par ex :

Code:

---

1 2 3 4 5 6 7 8 9

maTable = new Hashtable(); Roman livre = new Roman("A l'Ouest", 1); maTable.put(1, livre); livre = new Roman("A l'Est..", 2); maTable.put(2, livre); ... //Pour retrouver le livre A l'Ouest livre = (Roman)maTable.get(1);

---

Donc la démarche : lors de la recherche get(1), ne renvoi pas directement l'objet , il regarde le hashCode correspondant. Cependant ce hashCode peut-être correspondre a une seule clé ou a plusieurs, dès lors la méthode equals intervient pour vérifier la cocordance de l'attribut, et renvoi le bon objet.?
merci de vos corrections

Salut,

Citation:

---

Envoyé par totoche

Donc la démarche : lors de la recherche get(1), ne renvoi pas directement l'objet , il regarde le hashCode correspondant. Cependant ce hashCode peut-être correspondre a une seule clé ou a plusieurs, dès lors la méthode equals intervient pour vérifier la cocordance de l'attribut, et renvoi le bon objet.?

---

Non : tu utilises des Integer comme clef et le hashcode d'un Integer correspond à sa valeur...

get(1) renvoi directement l'élément livre associé.


a++

Bonjour adiGuba, et merci de ta promptitude
mais alors comment fait on lorsqu'on n'utilise pas un integer comme clé. :mur:

Code:

---

1 2 3 4 5 6 7 8 9

maTable = new Hashtable(); Roman livre = new Roman("A l'Ouest", 1); maTable.put(livre, livre); livre = new Roman("A l'Est..", 2); maTable.put(livre, livre); ... //Pour retrouver le livre A l'Ouest livre = (Roman)maTable.get(?);

---

merci

Peut-etre dans ce cas precis (ou l'objet est sa propre cle) peut-etre n'est-il pas pertinant d'utiliser une Map.

Salut,

Je crois que tu confonds un peu tout.

Reprenons depuis le début :

Un HashTable est une collection qui associe une clé à une valeur. Ici, tu as associé un Integer (la clé) à un Roman (la valeur).

Lorsque tu veux récupérer un Roman, tu appelles get et tu lui passes une valeur, à savoir dans ton exemple l'entier 1.

Comment fait Java derrière : il compare dans toutes les valeurs celle qui est exactement égale à 1.
Or, on sait que la fonction hashCode renvoie un entier qui sera toujours le même pour un objet donné, donc java sait que le hashCode de la clé que tu lui donne et le hashCode de la clé mémorisée sont strictement identique. Mais il sait aussi que deux objets inégaux n'ont pas forcément un hashCode différents. Le hashCode lui permet donc de filtrer les clés pour faire une recherche qu'on pourrait qualifier d'élaguée. Si, sur un éventail de 10 000 clés, seules 25 ont le même hashCode que la clé que tu recherches, c'est d'autant plus rapide, celà ne fait, au plus, que 25 appels à equals.

Donc, en résumé, hashCode est une fonction pour élaguer la recherche, equals une fonction pour la recherche en elle même.

Lorsque tu n'utilise pas un Integer comme clé, c'est exactement la même chose : tu redéfinis hashCode (il est d'usage de faire renvoyer à hashCode la somme des hashCode des objets composant l'objet en lui même) et equals.

Exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class MonObjet { Integer numero; String name; public int hashCode() { return name.hashCode()+numero.hashCode(); } public boolean equals(Object o) { if(! o instanceof MonObjet) return false; MonObjet temp=(MonObjet)o; return numero.equals(temp.numero) && name.equals(temp.name); } }

---

J'espère que j'ai été assez clair, sinon n'hésite pas à demander !

F.

Pour illustrer ce qu'a dit Mavina voici un schema tel que l'utilisaient mes profs de C a la fac pour nous expliquer le fonctionnement d'une (Hash)Map. Attention il s'agit uniquement d'une representation parmi d'autres, cela ne sous-entend pas qu'une Map est forcement implementee via des listes chainees.

Soient les cles Ka, Kb, Kc, Kd, Kn, Kp et Kz. Par la fonction de haschage Hash() nous avons :

Hash(Ka) = Hash(Kc) = H0

Hash(Kz) = Hash(Kd) = Hash(Kp) = H1

Hash(Kb) = H2

Hash(Kn) = Hm

On voit bien q'une requete sur Hash(Kc) va retourner H0 soit 2 cles possibles : Ka et Kc. On compare alors les cles jusqu'a trouver Kc et on retourne l'objet Vc qui lui est associe.

J'ai compris que lors de l'insertion dans une table il y a d'une part la clé et l'objet

Code:

---

maTable.put(key, objet);

---

et d'autre part la génération de son code, via la méthode hascode.
tout les objets ont une clé et une seule, mais certains peuvent avoir le même code, généré par la méthode hashcode.
[/CODE]

Citation:

---

Quand la méthode hashCode() est-t'elle utilisée ? Lors de l'insertion d'un élément dans un Hashtable, la méthode hashCode() est appelée pour classer l'instance dans un sous-ensemble. Lors de la recherche d'un élément, la méthode hashCode()sur l'instance à rechercher sert à sélectionner le sous-ensemble correspondant

---

http://www.prados.fr/Langage/Java/hashCode/hashCode.pdf

Mais comment fait-on sans parcourrir tout la table ?:

Code:

---

1 2 3 4

for (Enumeration e = maTable.keys(); e.hasMoreElements();){ livre = (Roman)maTable.get(e.nextElement()); if (livre.getTitre()=="LivreRecherche"){

---

Citation:

---

(il est d'usage de faire renvoyer à hashCode la somme des hashCode des attributs composant l'objet en lui même)

---

donc si l'on est capable de reconstruire le hashCode de l'ojet qu'on recherche on doit pouvoir boucler que sur les clés ayant le même hashcode, non?

je sais je suis un :boulet:
quand j'aurai compris j'aurai compris...
Merci de votre ++ Aide

La recherche n'est pas faite par toi, la méthode get(key) le fait pour toi, et elle met moins de temps si hashCode est redéfini dans la classe de key, voilà tout

F.

Citation:

---

Envoyé par totoche

et d'autre part la génération de son code, via la méthode hascode.

---

Le hashcode n'est pas créé il est seulement utilisé pour classer rapidement les clefs et seulement les clefs...


a++