Deux clés ayant un hashCode différent peuvent-elles faire partie du même compartiment dans HashMap en Java?

Question

J'ai une HashMap. Il y a 16 compartiments dedans (par défaut). Est-il possible que deux clés ayant des hashCodes différents fassent partie du même seau? Ou est-ce toujours un nouveau bucket est créé pour un hashCode différent et de cette façon le HashMap étend la taille du bucket?

Lire beaucoup de messages, mais seulement me suis embrouillé.

Answer 1

Oui, c'est possible. Puisque le nombre de seaux est beaucoup plus petit que le nombre de hashCodes possible (le nombre de seaux est proportionnel au nombre d'entrées dans le HashMap alors que le nombre de hashCodes possible est le nombre de valeurs possibles int, ce qui est beaucoup plus le mappage final d'un hashCode à un compartiment est effectué par un opérateur de module, donc plusieurs hashCodes peuvent être mappés au même compartiment (si, par exemple, vous avez 16 compartiments, les hashCodes 1 et 17 seront mappés au même compartiment (Notez que par hashCode je ne veux pas dire la valeur retournée par la méthode hashCode, puisque HashMap applique une fonction supplémentaire sur ce hashCode afin d'améliorer la distribution des codes de hachage)). C'est pourquoi hashCode seul n'est pas suffisant pour déterminer si la clé que nous recherchons est présente dans la carte - nous devons aussi utiliser equals.

Answer 2

REPRISES DE How HashMap works in Java:

Depuis le tableau interne de HashMap est de taille fixe, et si vous gardez le stockage d'objets, à un moment donné de la fonction de hachage de temps sera de retour même emplacement de seau pour deux clés différentes, ce est appelé collision dans HashMap. Dans ce cas, une liste liée est formée à cet emplacement de compartiment et une nouvelle entrée est stockée en tant que nœud suivant.

Et puis quand il si nous voulons get que l'objet dans la liste, nous avons besoin equals():

Si nous essayons de récupérer un objet à partir de cette liste chaînée, nous avons besoin d'un contrôle supplémentaire pour la recherche correcte valeur, ceci est fait par la méthode equals(). Comme chaque nœud contient une entrée, HashMap continue de comparer l'objet clé de l'entrée avec la clé transmise en utilisant equals() et quand elle retourne true, Map renvoie la valeur correspondante. Renvoie interger dans java afin que vous deviez mapper la plage d'entiers à la taille du compartiment

Answer 3

hashcode() Si vous mappez d'un ensemble plus grand à un ensemble plus petit, vous aurez toujours des collisions. Si vous regardez le code source de HashMap, vous trouverez la méthode suivante pour mapper int à la longueur du seau.

static int indexFor(int h, int length) { 
      return h & (length-1); 
} 

Le code de hachage est prétraitée pour produire une distribution uniforme en utilisant:

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
    } 

applique une fonction de hachage supplémentaire à un hashCode donné, qui protège contre des fonctions de hachage de mauvaise qualité. Ceci est critique car HashMap utilise des tables de hachage power-of-two length, qui sinon rencontrent des collisions pour hashCodes qui ne diffèrent pas dans les bits inférieurs. Note: Les clés nulles correspondent toujours au hash 0, donc index 0.

HashMap source