hash() implémentation en java

Question

Je passe par la classe HashMap en Java. Ma compréhension est que la capacité de table de hachage est 2 à la puissance du nombre de seaux (capacité 16 signifie quatre seaux). Lorsque put (key, value) est appelé, key.hashCode() renvoie un nombre entier et cette paire nouvellement ajoutée (clé, valeur) est placée en fonction du nombre de buckets key.hashCode()%. Mais ce qui suit est la mise en œuvre effective dans HashMap.class

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16); 
} 

À partir du code ci-dessus, je ne suis pas en mesure de comprendre comment la mise en place de la valeur key.hashCode() dans des seaux se produisent.

Answer 1

Ce code ne "colle" pas le hashCode aux buckets, il "étale" simplement le hashcode rendant les bits supérieurs plus significatifs. Voici le javadoc de cette méthode.

Calcule key.hashCode() et étale (XOR) les bits de hachage les plus élevés à abaisser. Étant donné que la table utilise le masquage power-of-two, les ensembles de hachages qui ne varient que dans les bits au-dessus du masque actuel entreront toujours en collision. (Parmi les exemples connus, on trouve des ensembles de clés flottantes contenant des nombres entiers consécutifs dans de petits tableaux.) Nous appliquons donc une transformation qui répartit l'impact des bits supérieurs vers le bas. Il y a un compromis entre la vitesse, l'utilité et la qualité de propagation des bits. Parce que de nombreux hachages communs sont déjà raisonnablement distribués (donc ne profitent pas de la propagation), et parce que nous utilisons des arbres pour gérer de grands ensembles de collisions dans les bacs, nous avons juste changé certains bits de la façon la moins chère possible pour réduire les pertes systématiques, ainsi que d'incorporer l'impact des bits les plus élevés qui, autrement, ne seraient jamais utilisés dans les calculs d'index en raison des limites de la table.

La fixation réelle à godets se fait dans la méthode getNode(int, Object):

first = tab[(n - 1) & hash] 

où hash est le résultat de hash(Object) et n est la taille de la table de hachage.