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

Question

Selon la documentation Java, le Le code de hachage pour un objet String est calculé comme suit:

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

     

en utilisant int l'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 devrait être un nombre premier relativement grand. Alors pourquoi pas 29, ou 37, voire 97?

Answer 1

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

  

La valeur 31 a été choisie car il s’agit d’un nombre premier impair. S'il était égal 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 clair, mais c'est traditionnel. Une belle propriété 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 machines virtuelles modernes effectuent automatiquement ce type d'optimisation.

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

Answer 2

Comme le Goodrich et Tamassia le soulignent, si vous prenez plus de 50 000 mots anglais des listes de mots fournies dans les deux variantes d’Unix), en utilisant les constantes 31, 33, 37, 39 et 41, produiront 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 polynomial &"; quand j'ai vu cette question.

EDIT: voici un lien vers le livre PDF de ~ 10mb auquel je fais référence ci-dessus. Reportez-vous à la section 10.2 Tables de hachage (page 423) de Structures de données et algorithmes en Java

Answer 3

Sur les processeurs (principalement) anciens, la multiplication par 31 peut être relativement peu coûteuse. Sur un bras, 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 séparée et une instruction de soustraction. Cependant, si votre multiplicateur est lent, c'est toujours une victoire. Les processeurs modernes ont tendance à avoir des multiplicateurs rapides, ce qui ne fait pas beaucoup de différence, du moment que 32 se place du bon côté.

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

Answer 4

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

En n'utilisant pas une puissance de deux, les bits de poids faible et de droite sont également renseignés pour être mélangés au prochain élément de données entrant dans le hachage.

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

Answer 5

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é la performance de différentes fonctions de hachage en ce qui concerne la & Quot. Chaîne moyenne résultante & Quot; dans une table de hachage. P(31) était l'une des fonctions courantes de cette époque qu'il avait trouvée 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 a donc pris P(33) car il semblait bien performer. Même si <=> 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:

  

Du reste   Quatrièmement, je choisirais probablement P (31), car c’est le moins cher à calculer sur un RISC   machine (car 31 est la différence de deux puissances de deux). P (33) est   de même pas cher à calculer, mais sa performance est légèrement pire, et   33 est composite, ce qui me rend un peu nerveux.

Le raisonnement n’était donc pas aussi rationnel que le suggèrent beaucoup de réponses. Mais nous sommes tous bons pour trouver des raisons rationnelles après les décisions instinctives (et même Bloch pourrait être enclin à cela).

Answer 6

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

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

Il peut être préférable d’utiliser 73 ou 37 (au lieu de 31), car cela conduit à un code plus dense : les deux instructions LEA ne prennent que 6 octets par rapport aux 7 octets pour déplacer + déplacer + soustraire multiplication par 31. Un inconvénient 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.

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

Answer 7

Neil Coffey explique pourquoi 31 est utilisé sous biais .

En gros, utiliser 31 vous donne une distribution de probabilité plus uniforme pour la fonction de hachage.

Answer 8

De JDK-4045622 , où Joshua Bloch en décrit les raisons pourquoi cette (nouvelle) mise en œuvre String.hashCode() a été choisie

  

Le tableau ci-dessous récapitule les performances des différents hash   fonctions décrites ci-dessus, pour trois ensembles de données:

     

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

     

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

     

3) Une liste des URL rassemblées par un robot d'indexation ayant fonctionné pendant plusieurs          heures la nuit dernière (28 372 chaînes, longueur moyenne 49 caractères).

     

La mesure de performance 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 la valeur attendue du   nombre de touches comparé 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 sauf pour   la fonction Java actuelle et les deux versions cassées de Weinberger   fonction offre d'excellentes performances presque impossibles à distinguer. je   conjecture fortement que cette performance est essentiellement la   " idéal théorique " ;, ce que vous obtiendriez si vous utilisiez un vrai aléatoire   générateur de nombres à la place d'une fonction de hachage.

     

J'éliminerais la fonction WAIS car ses spécifications contiennent des pages de nombres aléatoires et ses performances ne sont pas meilleures que celles des autres   fonctions beaucoup plus simples. Chacune des six fonctions restantes semble être   excellent choix, mais nous devons en choisir un. Je suppose que j'écarterais   La variante de Vo et la fonction de Weinberger en raison de leur ajout   complexité, même 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 pouvoirs de deux). P (33) est également bon marché pour   calculer, mais sa performance est légèrement pire, et 33 est   composite, ce qui me rend un peu nerveux.

     

Josh

Answer 9

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

Answer 10

Bloch ne va pas tout à fait dans le sujet, mais la raison que j’ai toujours entendu / cru est qu’il s’agissait d’une algèbre fondamentale. Les hachages se résument à des opérations de multiplication et de module, ce qui signifie que vous ne voulez jamais utiliser des nombres avec des facteurs communs si vous pouvez vous aider. En d’autres termes, les nombres premiers premiers fournissent une distribution égale des réponses.

Les chiffres qui composent un hachage sont généralement les suivants:

• module du type de données dans lequel vous l'avez inséré (2 ^ 32 ou 2 ^ 64)
• module du nombre de seaux dans votre table de hachage (varie. En java, il était premier, maintenant 2 ^ n)
• multipliez ou décalez d'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. Un peu plus d'attention est donc nécessaire.

Answer 11

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

Le but de la chaîne de hachage est

• unique (permet de voir l'opérateur ^ dans le document de calcul du hashcode, l'aide est unique)
• coût bas pour le calcul

31 is max value peut être inséré dans un registre de 8 bits (= 1 octet). Le nombre premier le plus grand que vous pouvez placer dans un registre à 1 octet est un nombre impair.

Multiplier 31 est < < 5 puis se soustraire, il faut donc des ressources peu coûteuses.