Pourquoi la fonction hashCode() de Java dans String utilise-t-elle 31 comme multiplicateur ?

Question

D'après la documentation de Java, le [code de hachage](http://java.sun.com/javase/6/docs/api/java/lang/String.html#hashCode()) pour un String est calculé comme suit :

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

en utilisant int arithmétique, où s[i] est le i e caractère de la chaîne, n est la longueur de la chaîne, et ^ indique une exponentiation.

Pourquoi 31 est-il utilisé comme multiplicateur ?

Je comprends que le multiplicateur doit être un nombre premier relativement grand. Alors pourquoi pas 29, ou 37, ou même 97 ?

Answer 1

Selon l'ouvrage de Joshua Bloch Java efficace (un livre qu'on ne saurait trop recommander, et que j'ai acheté grâce aux mentions continuelles sur stackoverflow) :

La valeur 31 a été choisie parce que c'est un nombre premier impair. Si elle était paire et que la multiplication débordait, des informations seraient perdues, car la multiplication par 2 est équivalente à un décalage. L'avantage d'utiliser un nombre premier est moins clair, mais il est traditionnel. Une propriété intéressante de 31 est que la multiplication peut être remplacée par un décalage et une soustraction pour de meilleures performances : 31 * i == (i << 5) - i . Les VM modernes effectuent ce type d'optimisation automatiquement.

(extrait du chapitre 3, point 9 : Toujours remplacer le hashcode lorsque vous remplacez les égaux, page 48)

Answer 2

Goodrich et Tamassia ont calculé, à partir de plus de 50 000 mots anglais (formés par l'union des listes de mots fournies dans deux variantes d'Unix), que l'utilisation des constantes 31, 33, 37, 39 et 41 produira moins de 7 collisions dans chaque cas. C'est peut-être la raison pour laquelle tant d'implémentations Java choisissent ces constantes.

Voir la section 9.2 Tables de hachage (page 522) du document Structures de données et algorithmes en Java .

Answer 3

Sur les anciens processeurs (pour la plupart), la multiplication par 31 peut être relativement bon marché. Sur un ARM, par exemple, cela ne représente qu'une seule instruction :

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

La plupart des autres processeurs nécessiteraient une instruction de décalage et de soustraction distincte. Cependant, si votre multiplicateur est lent, c'est toujours une victoire. Les processeurs modernes ont tendance à avoir des multiplicateurs rapides, donc cela ne fait pas beaucoup de différence, tant que 32 va du bon côté.

Ce n'est pas un grand algorithme de hachage, mais c'est suffisamment bon et meilleur que le code 1.0 (et bien meilleur que la spécification 1.0 !).

Answer 4

En multipliant, les bits sont décalés vers la gauche. Cela utilise une plus grande partie de l'espace disponible des codes de hachage, réduisant ainsi les collisions.

En n'utilisant pas de puissance de deux, les bits d'ordre inférieur, les plus à droite, sont également remplis, pour être mélangés avec la prochaine donnée entrant dans le hachage.

L'expression n * 31 est équivalent à (n << 5) - n .

Answer 5

En fait, 37 ferait très bien l'affaire ! z := 37 * x peut être calculé comme suit y := x + 8 * x; z := x + 4 * y . Ces deux étapes correspondent à une instruction LEA x86, ce qui est donc extrêmement rapide.

En fait, la multiplication par un nombre premier encore plus grand 73 pourrait se faire à la même vitesse en mettant y := x + 8 * x; z := x + 8 * y .

Utiliser 73 ou 37 (au lieu de 31) pourrait être mieux, car cela conduit à code plus dense : Les deux instructions LEA ne prennent que 6 octets contre les 7 octets de move+shift+subtract pour la multiplication par 31. Une mise en garde possible est que les instructions LEA à 3 arguments utilisées ici sont devenues plus lentes sur l'architecture Sandy bridge d'Intel, avec une latence accrue de 3 cycles.

D'ailleurs, 73 est le numéro préféré de Sheldon Cooper.