Pourquoi le hashcode () de Java dans String utilise-t-il 31 comme multiplicateur?
en Java, le code hash pour un objet String est calculé comme
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
utilisant int arithmétique, où s[i] est le i TH caractère de la chaîne, n est la longueur de la chaîne, et ^ indique l'exponentiation.
pourquoi 31 est-il utilisé comme un multiplicateur?
je comprends que le multiplicateur devrait être un nombre premier relativement important. Alors pourquoi pas 29, ou 37, ou même 97?
10 réponses
selon Joshua Bloch Effective Java (un livre qui ne peut pas être recommandé assez, et que j'ai acheté grâce à des mentions continuelles sur stackoverflow):
la valeur 31 a été choisie parce qu'il s'agit d'un nombre premier Impair. Si elle était égale et la multiplication débordée, l'information serait perdue, puisque la multiplication par 2 équivaut à un déplacement. L'avantage d'utiliser un prime est moins évident, mais il est traditionnel. Beau la propriété de 31 est que la multiplication peut être remplacée par un décalage et une soustraction pour une meilleure performance:
31 * i == (i << 5) - i. Les Vm modernes font ce genre d'optimisation automatiquement.
(du Chapitre 3, Point 9: toujours Outrepasser le hashcode lorsque vous outrepassez égal, page 48)
comme Goodrich et Tamassia faire remarquer, si vous prenez plus de 50.000 mots anglais (formé comme l'union des listes de mots fournis dans deux variantes D'Unix), en utilisant les 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 au milieu de la lecture de la section " Codes de hachage polynomial" quand j'ai vu cette question.
EDIT: voici le lien vers le ~10MB PDF book je me réfère à ci-dessus. Voir section 10.2 tableaux de hachage (page 413) de Structures de données et algorithmes en Java
(essentiellement) de vieux processeurs, en multipliant par 31 peuvent être relativement bon marché. Sur un bras, par exemple, il n'y a qu'une instruction:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
la plupart des autres processeurs auraient besoin d'une instruction de déplacement et de soustraction distincte. Toutefois, si votre multiplicateur est lent, c'est toujours une victoire. Les processeurs modernes ont tendance à avoir des multiplicateurs rapides de sorte qu'il ne fait pas beaucoup de différence, tant que 32 va du bon côté.
ce n'est pas un grand hash algorithme, mais il est assez bon et meilleur que le code 1.0 (et beaucoup mieux que la spécification 1.0!).
en se multipliant, les bits sont déplacés vers la gauche. Cela utilise plus d'espace disponible de codes de hachage, réduisant les collisions.
en n'utilisant pas une puissance de deux, les bits d'ordre inférieur, les bits les plus à droite sont aussi peuplés, pour être mélangés avec le prochain morceau de données allant dans le hachage.
l'expression n * 31 est é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é la performance de différentes fonctions de hachage en ce qui concerne la "taille moyenne de chaîne" résultant dans une table de hachage. P(31) était l'une des fonctions communes pendant cette période qu'il a trouvé dans le livre de K&R (mais même Kernighan et Ritchie ne pouvait pas se rappeler d'où il venait). En fin de compte, il a dû en choisir un et donc il a pris P(31) car il semblait fonctionner assez bien. Même si P(33) n'était pas vraiment pire et la multiplication par 33 est tout aussi rapide à calculer (juste un décalage par 5 et un ajout), il a opté pour 31 Car 33 n'est pas un prime:
des autres quatre, je choisirais probablement P (31), Car c'est le moins cher à calculer sur un RISC machine (parce que 31 est la différence de deux puissances de deux). P (33) is tout aussi bon marché à calculer, mais c'est le rendement est légèrement pire, et 33 est composite, ce qui me rend un peu nerveux.
ainsi le raisonnement n'était pas aussi rationnel que beaucoup de réponses ici semblent impliquer. Mais nous sommes tous bons à trouver des raisons rationnelles après des décisions intestinales (et même Bloch pourrait être enclin à cela).
en fait, 37 ça marcherait 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, donc c'est extrêmement rapide.
en fait, la multiplication avec le prime encore plus grand 73 pourrait être faite à la même vitesse en réglant y := x + 8 * x; z := x + 8 * y .
en utilisant 73 ou 37 (au lieu de 31) pourrait être mieux, parce qu'il conduit à code plus dense : les deux LEA les instructions ne prennent que 6 bytes contre 7 bytes pour move+shift+soustract 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.
de plus, 73 est le numéro préféré de Sheldon Cooper.
Je ne suis pas sûr, mais je suppose qu'ils ont testé un échantillon de nombres premiers et ont trouvé que 31 a donné la meilleure distribution sur un échantillon de chaînes possibles.
Bloch ne va pas tout à fait dans ce, mais la raison que j'ai toujours entendu/cru est que c'est l'algèbre de base. 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 l'aider. En d'autres termes, les nombres relativement premiers fournissent une distribution uniforme des réponses.
les nombres qui composent en utilisant un hash sont typiquement:
- module du type de données vous la mettez dans (2^32 ou 2^64)
- module du nombre de godets dans votre hashtable (varie. En java, c'était prime, maintenant 2^n)
- multiplier ou déplacer par un nombre magique dans votre fonction de mélange
- la valeur d'entrée
vous ne pouvez vraiment contrôler que quelques-unes de ces valeurs, donc un peu plus de soin est due.
à Partir de JDK-4045622 , où Joshua Bloch décrit les raisons pour lesquelles cette (nouvelle) String.hashCode() la mise en œuvre a été choisie
le tableau ci-dessous résume les performances des divers fonctions décrites ci-dessus, pour trois ensembles de données:
1) Tous les mots et toutes les phrases avec les entrées dans Merriam-Webster's 2ème Int'l Dictionnaire Intégral (311,141 chaînes, avg longueur de 10 caractères).
2) Toutes les chaînes dans /bin/ , /usr/bin/ , /usr/lib/ , /usr/ucb/ et /usr/openwin/bin/* (66,304 chaînes, avg longueur de 21 caractères).
3) une liste d'URLs recueillies par un web-crawler qui a fonctionné pendant plusieurs heures last night (28,372 cordes, longueur moyenne 49 caractères).
la métrique 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.-à-d. la valeur attendue de la nombre de clés 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.2439en regardant cette table, il est clair que toutes les fonctions sauf la fonction Java actuelle et les deux versions cassées de Weinberger fonction offrent des performances excellentes, presque indiscernables. Je la conjecture forte que cette performance est essentiellement "idéal théorique", ce que vous obtiendriez si vous utilisiez un vrai aléatoire générateur de nombres en place d'une fonction de hachage.
j'écarterais la fonction WAIS car sa spécification contient des pages de nombres aléatoires, et sa performance n'est pas meilleure que l'un des fonctions beaucoup plus simples. L'une des six fonctions restantes semble être excellent choix, mais nous devons en choisir un. Je suppose que j'avais écarter La variante de Vo et la fonction de Weinberger en raison de leur la complexité, quoique mineur. Des quatre autres, je serais probablement sélectionner P (31), Car c'est le moins cher à calculer sur une machine RISC (parce que 31 est la différence de deux puissances de deux). P (33) est également bon marché pour calculez, mais sa performance est légèrement pire, et 33 est composite, ce qui me rend un peu nerveux.
Josh