Pourquoi le hashCode () de Java dans String utilise-t-il 31 comme multiplicateur?

Selon la documentation Java, le code de hachage d'un Stringobjet est calculé comme suit:

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

en utilisant l' intarithmétique, où s[i]est le i ème caractère de la chaîne, nest la longueur de la chaîne, et ^indique l'exponentiation.

Pourquoi 31 est-il utilisé comme multiplicateur?

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

Selon Effective Java de Joshua Bloch (un livre qui ne peut pas être assez recommandé, et que j'ai acheté grâce aux mentions continuelles sur stackoverflow):

La valeur 31 a été choisie car il s'agit d'un nombre impair impair. S'il était pair et que la multiplication débordait, l'information serait perdue, car la multiplication par 2 équivaut à un décalage. L'avantage d'utiliser un nombre premier est moins évident, mais il est traditionnel. Une belle propriété de 31 est que la multiplication peut être remplacé par un changement et une soustraction pour une meilleure performance: 31 * i == (i << 5) - i. Les machines virtuelles modernes effectuent automatiquement ce type d'optimisation.

(extrait du chapitre 3, élément 9: toujours remplacer le code de hachage lorsque vous remplacez égal, page 48)

Comme le soulignent Goodrich et Tamassia , si vous prenez plus de 50 000 mots anglais (formés comme l'union des listes de mots fournies dans deux variantes d'Unix), l'utilisation des constantes 31, 33, 37, 39 et 41 produira moins de 7 collisions dans chaque cas. Sachant cela, il n'est pas surprenant que de nombreuses implémentations Java choisissent l'une de ces constantes.

Par coïncidence, j'étais en train de lire la section "codes de hachage polynomiaux" quand j'ai vu cette question.

EDIT: voici le lien vers le livre PDF ~ 10 Mo auquel je fais référence ci-dessus. See section 10.2 Hash Tables (page 413) de Data Structures and Algorithms in Java

Sur (principalement) d'anciens processeurs, la multiplication par 31 peut être relativement bon marché. Sur un ARM, par exemple, ce n'est qu'une 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 excellent algorithme de hachage, mais il est suffisamment bon et meilleur que le code 1.0 (et bien meilleur que la spécification 1.0!).

En multipliant, les bits sont décalés vers la gauche. Cela utilise davantage d'espace disponible de codes de hachage, ce qui réduit les collisions.

En n'utilisant pas une puissance de deux, les bits de poids faible de droite sont également remplis, pour être mélangés avec la prochaine donnée entrant dans le hachage.

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

Vous pouvez lire le raisonnement original de Bloch sous "Commentaires" dans http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Il a étudié les performances de différentes fonctions de hachage en ce qui concerne la "taille de chaîne moyenne" résultante dans une table de hachage. P(31)était l'une des fonctions communes à cette époque qu'il a trouvées dans le livre de K&R (mais même Kernighan et Ritchie ne pouvaient pas se rappeler d'où cela venait). En fin de compte, il a dû en choisir un et il l'a donc pris P(31)car il semblait fonctionner assez bien. Même si ce P(33)n'était pas vraiment pire et que la multiplication par 33 est également rapide à calculer (juste un décalage de 5 et un ajout), il a opté pour 31 car 33 n'est pas un nombre premier:

Parmi les quatre autres, je choisirais probablement P (31), car c'est le moins cher à calculer sur une machine RISC (car 31 est la différence de deux puissances de deux). P (33) est également bon marché à calculer, mais ses performances sont légèrement inférieures et 33 est composite, ce qui me rend un peu nerveux.

Le raisonnement n'était donc pas aussi rationnel que la plupart des réponses semblent le laisser entendre. Mais nous sommes tous bons pour trouver des raisons rationnelles après des décisions intestinales (et même Bloch pourrait être enclin à cela).

En fait, 37 fonctionnerait plutôt bien! z: = 37 * x peut être calculé commey := x + 8 * x; z := x + 4 * y . Les deux étapes correspondent à une instruction LEA x86, c'est donc extrêmement rapide.

En fait, la multiplication avec le premier 73 encore plus grand pourrait être effectuée à la même vitesse en réglant y := x + 8 * x; z := x + 8 * y.

Utiliser 73 ou 37 (au lieu de 31) pourrait être mieux, car cela conduit à un code plus dense : les deux instructions LEA ne prennent que 6 octets contre les 7 octets pour déplacer + déplacer + soustraire 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 du pont Sandy d'Intel, avec une latence accrue de 3 cycles.

De plus, 73 est le numéro préféré de Sheldon Cooper.

Neil Coffey explique pourquoi 31 est utilisé sous Aplanir le biais .

Fondamentalement, l'utilisation de 31 vous donne une distribution de probabilité de bit de jeu plus uniforme pour la fonction de hachage.

Extrait de JDK-4045622 , où Joshua Bloch décrit les raisons pour lesquelles cette (nouvelle) String.hashCode()mise en œuvre particulière a été choisie

Le tableau ci-dessous résume les performances des différentes fonctions de hachage décrites ci-dessus, pour trois ensembles de données:

1) Tous les mots et expressions avec des entrées dans le 2ème dictionnaire intl de Merriam-Webster (311 141 chaînes, longueur moyenne 10 caractères).

2) Toutes les chaînes dans / bin / , / usr / bin / , / usr / lib / , / usr / ucb / et / usr / openwin / bin / * (66 304 chaînes, longueur moyenne 21 caractères).

3) Une liste d'URL collectées par un robot d'exploration qui a fonctionné pendant plusieurs heures la nuit dernière (28 372 chaînes, longueur moyenne de 49 caractères).

La mesure des performances indiquée dans le tableau est la "taille moyenne de la chaîne" sur tous les éléments de la table de hachage (c'est-à-dire que la valeur attendue du nombre de clés se compare pour rechercher un élément).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

En regardant ce tableau, il est clair que toutes les fonctions à l'exception de la fonction Java actuelle et des deux versions cassées de la fonction de Weinberger offrent d'excellentes performances, presque indiscernables. Je suppose fortement que cette performance est essentiellement «l'idéal théorique», ce que vous obtiendriez si vous utilisiez un véritable générateur de nombres aléatoires à la place d'une fonction de hachage.

J'exclurais la fonction WAIS car sa spécification contient des pages de nombres aléatoires et ses performances ne sont pas meilleures que celles des fonctions beaucoup plus simples. Chacune des six fonctions restantes semble être un excellent choix, mais nous devons en choisir une. Je suppose que j'exclurais la variante de Vo et la fonction de Weinberger en raison de leur complexité supplémentaire, bien que mineure. Parmi les quatre autres, je choisirais probablement P (31), car c'est le moins cher à calculer sur une machine RISC (car 31 est la différence de deux puissances de deux). P (33) est également bon marché à calculer, mais ses performances sont légèrement inférieures et 33 est composite, ce qui me rend un peu nerveux.

Josh

Bloch n'entre pas tout à fait dans cela, mais la raison pour laquelle j'ai toujours entendu / cru est que c'est l'algèbre de base. Les hachages se résument aux opérations de multiplication et de module, ce qui signifie que vous ne voudrez jamais utiliser des nombres avec des facteurs communs si vous pouvez l'aider. En d'autres termes, les nombres relativement premiers fournissent une distribution uniforme des réponses.

Les nombres qui composent en utilisant un hachage sont généralement:

• module du type de données dans lequel vous le mettez (2 ^ 32 ou 2 ^ 64)
• module du nombre de seaux dans votre table de hachage (varie. En java utilisé pour être premier, maintenant 2 ^ n)
• multiplier ou décaler par un nombre magique dans votre fonction de mixage
• La valeur d'entrée

Vous ne pouvez vraiment contrôler que quelques-unes de ces valeurs, donc un peu de soin supplémentaire est dû.

Dans la dernière version de JDK, 31 est toujours utilisé. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()

Le but de la chaîne de hachage est

• unique (voir opérateur ^ dans le document de calcul du code de hachage, cela aide à unique)
• coût pas cher pour le calcul

31 est la valeur maximale peut être mise dans un registre de 8 bits (= 1 octet), est le plus grand nombre premier peut être mis dans un registre de 1 octet, est un nombre impair.

Multiplier 31 est << 5 puis se soustraire, donc besoin de ressources bon marché.

Je ne suis pas sûr, mais je suppose qu'ils ont testé un échantillon de nombres premiers et ont constaté que 31 donnait la meilleure distribution sur un échantillon de chaînes possibles.

C'est parce que 31 a une belle propriété - sa multiplication peut être remplacée par un décalage au niveau du bit qui est plus rapide que la multiplication standard:

31 * i == (i << 5) - i