Comment fonctionne un HashMap en Java ?

Question

Comme je l'ai compris, je pense :

1. Il est parfaitement légal que deux objets aient le même code de hachage.
2. Si deux objets sont égaux (en utilisant equals ), ils ont le même code de hachage.
3. Si deux objets ne sont pas égaux, ils ne peuvent pas avoir le même code de hachage.

Ai-je raison ?

Maintenant si je suis correct, j'ai le doute suivant : HashMap utilise en interne le code de hachage de l'objet. Si deux objets peuvent avoir le même code de hachage, alors comment la fonction HashMap suivre quelle clé il utilise ?

Quelqu'un peut-il expliquer comment HashMap utilise en interne le hashcode de l'objet ?

Answer 1

Un hashmap fonctionne comme suit (c'est un peu simplifié, mais cela illustre le mécanisme de base) :

Il dispose d'un certain nombre de "godets" dans lesquels il stocke les paires clé-valeur. Chaque godet a un numéro unique - c'est ce qui identifie le godet. Lorsque vous placez une paire clé-valeur dans la carte, le hashmap examine le code de hachage de la clé et stocke la paire dans le godet dont l'identifiant est le code de hachage de la clé. Par exemple : Le code de hachage de la clé est 235 -> la paire est stockée dans le godet numéro 235. (Notez qu'un godet peut stocker plus d'une paire clé-valeur).

Lorsque vous recherchez une valeur dans le hashmap, en lui donnant une clé, il regardera d'abord le code de hachage de la clé que vous avez donnée. Le hashmap cherchera ensuite dans le seau correspondant, puis il comparera la clé que vous avez donnée avec les clés de toutes les paires dans le seau, en les comparant à equals() .

Vous pouvez maintenant voir comment cette méthode est très efficace pour rechercher des paires clé-valeur dans une carte : grâce au code de hachage de la clé, la carte de hachage sait immédiatement dans quel seau chercher, de sorte qu'elle ne doit tester que ce qui se trouve dans ce seau.

En observant le mécanisme ci-dessus, vous pouvez également voir quelles sont les exigences nécessaires sur le site de l hashCode() et equals() méthodes de clés :

• Si deux clés sont identiques ( equals() renvoie à true quand on les compare), leur hashCode() doit retourner le même nombre. Si les clés ne respectent pas cette règle, des clés égales pourraient être stockées dans des compartiments différents, et le hashmap ne serait pas en mesure de trouver des paires clé-valeur (car il chercherait dans le même compartiment).

• Si deux clés sont différentes, il importe peu que leurs codes de hachage soient identiques ou non. Elles seront stockées dans le même bucket si leurs codes de hachage sont les mêmes, et dans ce cas, le hashmap utilise equals() pour les différencier.

Answer 2

Votre troisième affirmation est incorrecte.

Il est parfaitement légal que deux objets inégaux aient le même code de hachage. Il est utilisé par HashMap comme un "filtre de premier passage" afin que la carte puisse rapidement trouver possible les entrées avec la clé spécifiée. Les clés ayant le même code de hachage sont ensuite testées pour vérifier leur égalité avec la clé spécifiée.

Vous ne voudriez pas exiger que deux objets inégaux ne puissent pas avoir le même code de hachage, car cela vous limiterait à deux objets. 32 des objets possibles. (Cela signifierait également que les différents types ne pourraient même pas utiliser les champs d'un objet pour générer des codes de hachage, car d'autres classes pourraient générer le même hachage).

Answer 3

Vous trouverez d'excellentes informations sur le site http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Pour résumer :

HashMap fonctionne sur le principe du hachage

put(clé, valeur) : HashMap stocke les objets clé et valeur comme Map.Entry. Hashmap applique hashcode(key) pour obtenir le bucket. S'il y a collision ,HashMap utilise LinkedList pour stocker l'objet.

get(clé) : HashMap utilise le code de hachage de l'objet clé pour trouver l'emplacement du seau, puis appelle la méthode keys.equals() pour identifier le nœud correct dans LinkedList et renvoie l'objet de valeur associé pour cette clé dans Java HashMap.

Answer 4

Le hashcode détermine quel seau de la hashmap doit être vérifié. S'il y a plus d'un objet dans le godet, une recherche linéaire est effectuée pour trouver l'élément du godet qui correspond à l'élément désiré (en utilisant la balise equals() ).

En d'autres termes, si vous avez un hashcode parfait, l'accès au hashmap est constant, vous n'aurez jamais à itérer à travers un godet (techniquement, vous devriez aussi avoir des godets MAX_INT, l'implémentation Java peut partager quelques hashcodes dans le même godet pour réduire l'espace nécessaire). Si vous avez le pire code de hachage (qui renvoie toujours le même nombre), votre accès à la table de hachage devient linéaire puisque vous devez rechercher chaque élément de la carte (ils sont tous dans le même godet) pour obtenir ce que vous voulez.

La plupart du temps, un code de hachage bien écrit n'est pas parfait, mais il est suffisamment unique pour vous donner un accès plus ou moins constant.

Answer 5

Vous vous trompez sur le point 3. Deux entrées peuvent avoir le même code de hachage mais ne pas être égales. Jetez un coup d'œil à l'implémentation de HashMap.get de l'OpenJdk . Vous pouvez voir qu'il vérifie que les hachages sont égaux et que les clés sont égales. Si le troisième point était vrai, il ne serait pas nécessaire de vérifier que les clés sont égales. Le code de hachage est comparé avant la clé car la première est une comparaison plus efficace.

Si vous souhaitez en savoir un peu plus à ce sujet, consultez l'article de Wikipédia sur Adressage ouvert Résolution des collisions qui, je crois, est le mécanisme utilisé par l'implémentation d'OpenJdk. Ce mécanisme est subtilement différent de l'approche "bucket" mentionnée dans l'une des autres réponses.