Hashtable.ContainsKey se base sur quoi?

**stephane.julien** · 11/03/2008, 17h17

Bonjour,

J'ai une Hashtable dont la clé est une classe perso. Seulement, lorsque je fait MaHashtable.Containskey(), ça me retourne toujours false.

J'ai pourtant redéfinit la méthode Equals()... J'ai également essayé d'implémenter l'interface IComparable, mais rien...

Est-ce que quelqu'un peut m'aider? Merci d'avance...

**BCmDev** · 11/03/2008, 17h19

Quand tu ajoutes un élément dans ta Hashtable, tu l'ajoutes en définissant une clef. C'est dans ces clefs que ContainsKey() recherche. Es-tu bien sûr de lui fournir une clef valide (et non par exemple l'élément indexé) ?

**Guulh** · 11/03/2008, 18h39

Il me semble que la HashTable se base sur la fonction GetHashCode, que tu dois donc surcharger.

**cinemania** · 12/03/2008, 10h18

Le principe d'une table de hashage c'est de recouvré un élément le plus rapidement possible en fonction d'une clé, peut importe soit t'elle d'ailleurs.

En réalité le but est de convertir une recherce habituellement en O(n) en O(1), ce qui signifie qu'habituellement une recherche qui parcours toute la liste afin de trouver l'élément va là retourner l'élement en 1 seule (ou 2) opérations de lecture dans la liste...

La hashtable n'a de réel intérêt qu'au dela de la cinquantaine d'enregistrements, en dessous, un tel mécanisme est une perte de temps.
Pour pouvoir classer et ordonner les clés, une hashtable utilise des banques, qui selon l'implantation peuvent être un index vers un sous tableau, ou un index dans un tableau principal et dans une table de liaison.
Ensuite quand tu ajoute un couple clé/valeur, la hashtable calcul (ou demande à l'objet clé) un code de HASHAGE (GetHashCode()) ce code qui est un entier, est l'identifiant de banque. La hashtable va donc aller chercher dans cette banque, la clé. Ensuite il s'agit d'une recherche de type liste chainée normale avec comparaison pour chaque clé (Equals).
Si l'algorithme du Hashcode permet suffisamment d'enthropie, on peut estimé que la recherche de l'élément sera en temps O(1).
Plus ton algorithme de hashage (GetHashCode()) retourne des code différents pour des éléments différents, plus tu as de chance minimiser le temps de recherche.

Si tu te ne redéfini pas le GetHashCode de object, celui-ci est basé et calculé, comportement similaire en java, sur l'adresse mémoire de l'instance... Dans ton cas à moins de rechercher clairement l'instance que tu as utilisée comme clé, tu ne la trouvera jamais dans ta hashtable.