Pourquoi utiliser un nombre premier dans hashCode?

174

Je me demandais simplement pourquoi les nombres premiers sont utilisés dans la hashCode()méthode d' une classe ? Par exemple, lorsque vous utilisez Eclipse pour générer ma hashCode()méthode, le nombre premier est toujours 31utilisé:

public int hashCode() {
     final int prime = 31;
     //...
}

Références:

Voici une bonne introduction sur Hashcode et un article sur le fonctionnement du hachage que j'ai trouvé (C # mais les concepts sont transférables): Directives et règles d'Eric Lippert pour GetHashCode ()

Ian Dallas
la source
C'est plus ou moins un double de la question stackoverflow.com/questions/1145217/… .
Hans-Peter Störr
1
Veuillez vérifier ma réponse sur stackoverflow.com/questions/1145217/ ... Elle est liée aux propriétés des polynômes sur un champ (pas un anneau!), D'où les nombres premiers.
TT_

Réponses:

104

Parce que vous voulez que le nombre par lequel vous multipliez et le nombre de seaux dans lesquels vous insérez aient des factorisations premier orthogonales.

Supposons qu'il y ait 8 seaux dans lesquels insérer. Si le nombre que vous utilisez pour multiplier par est un multiple de 8, le seau inséré dans sera uniquement déterminé par l'entrée la moins significative (celle qui n'est pas du tout multipliée). Des entrées similaires entreront en collision. Pas bon pour une fonction de hachage.

31 est un nombre premier suffisamment grand pour que le nombre de buckets ne soit probablement pas divisible par lui (et en fait, les implémentations java modernes de HashMap maintiennent le nombre de buckets à une puissance de 2).

ILMTitan
la source
9
Ensuite, une fonction de hachage multipliée par 31 ne fonctionnera pas de manière optimale. Cependant, je considérerais une telle implémentation de table de hachage mal conçue, étant donné la fréquence de 31 en tant que multiplicateur.
ILMTitan
11
Donc 31 est choisi sur la base de l'hypothèse que les implémenteurs de table de hachage savent que 31 est couramment utilisé dans les codes de hachage?
Steve Kuo
3
31 est choisi sur la base de l'idée que la plupart des implémentations ont des factorisations de nombres premiers relativement petits. 2s, 3s et 5s généralement. Il peut commencer à 10 et croître 3X lorsqu'il est trop plein. La taille est rarement entièrement aléatoire. Et même si c'était le cas, 30/31 ne sont pas de mauvaises chances d'avoir des algorithmes de hachage bien synchronisés. Il peut également être facile à calculer comme d'autres l'ont indiqué.
ILMTitan
8
En d'autres termes ... nous devons savoir quelque chose sur l'ensemble des valeurs d'entrée et les régularités de l'ensemble, afin d'écrire une fonction conçue pour les dépouiller de ces régularités, afin que les valeurs de l'ensemble ne se heurtent pas de la même manière seaux de hachage. Multiplier / diviser / moduler par un nombre premier réalise cet effet, car si vous avez une boucle avec des éléments X et que vous sautez des espaces Y dans la boucle, vous ne reviendrez jamais au même endroit jusqu'à ce que X devienne un facteur de Y Puisque X est souvent un nombre pair ou une puissance de 2, alors vous avez besoin de Y pour être premier donc X + X + X ... n'est pas un facteur de Y, donc 31 yay! : /
Triynko
3
@FrankQ. C'est la nature de l'arithmétique modulaire. (x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
ILMTitan
136

Les nombres premiers sont choisis pour répartir au mieux les données entre les buckets de hachage. Si la distribution des entrées est aléatoire et uniformément répartie, alors le choix du code / module de hachage n'a pas d'importance. Cela n'a un impact que lorsqu'il existe un certain modèle sur les entrées.

C'est souvent le cas lorsqu'il s'agit d'emplacements de mémoire. Par exemple, tous les entiers de 32 bits sont alignés sur des adresses divisibles par 4. Consultez le tableau ci-dessous pour visualiser les effets de l'utilisation d'un module premier par rapport à un module non premier:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Remarquez la distribution presque parfaite lorsque vous utilisez un module premier par rapport à un module non premier.

Cependant, bien que l'exemple ci-dessus soit en grande partie artificiel, le principe général est que lorsqu'il s'agit d'un modèle d'entrées , l'utilisation d'un module de nombre premier donnera la meilleure distribution.

avouer
la source
17
Ne parlons-nous pas du multiplicateur utilisé pour générer le code de hachage, pas du modulo utilisé pour trier ces codes de hachage dans des seaux?
ILMTitan
3
Même principe. En termes d'E / S, le hachage alimente l'opération modulo de la table de hachage. Je pense que le fait est que si vous multipliez par des nombres premiers, vous obtiendrez plus d'entrées distribuées de manière aléatoire au point où le modulo n'aura même pas d'importance. Étant donné que la fonction de hachage prend le temps de mieux distribuer les entrées, les rendant moins régulières, elles sont moins susceptibles de se heurter, quel que soit le modulo utilisé pour les placer dans un seau.
Triynko
9
Ce genre de réponse est très utile car c'est comme apprendre à quelqu'un à pêcher, plutôt que d'en attraper un pour lui. Cela aide les gens à voir et à comprendre le principe sous-jacent à l'utilisation de nombres premiers pour les hachages ... qui est de distribuer les entrées de manière irrégulière afin qu'elles tombent uniformément dans des buckets une fois modulées :).
Triynko
29

Pour ce que ça vaut, Effective Java 2nd Edition renonce à la question des mathématiques et dit simplement que la raison de choisir 31 est:

  • Parce que c'est un nombre premier impair, et qu'il est "traditionnel" d'utiliser des nombres premiers
  • C'est aussi un de moins qu'une puissance de deux, ce qui permet une optimisation au niveau du bit

Voici le devis complet, à partir de l' article 9: Toujours remplacer hashCodelorsque vous remplacezequals :

La valeur 31 a été choisie parce que c'est un nombre premier 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 prime est moins clair, mais il est traditionnel.

Une belle propriété de 31 est que la multiplication peut être remplacée par un décalage ( §15.19 ) et une soustraction pour de meilleures performances:

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

Les machines virtuelles modernes effectuent ce type d'optimisation automatiquement.


Bien que la recette de cet élément donne des fonctions de hachage raisonnablement bonnes, elle ne fournit pas de fonctions de hachage de pointe, et les bibliothèques de plate-forme Java ne fournissent pas de telles fonctions de hachage à partir de la version 1.6. L'écriture de telles fonctions de hachage est un sujet de recherche, qu'il vaut mieux laisser aux mathématiciens et aux informaticiens théoriciens.

Peut-être qu'une version ultérieure de la plate-forme fournira des fonctions de hachage de pointe pour ses classes et ses méthodes utilitaires pour permettre aux programmeurs moyens de construire de telles fonctions de hachage. En attendant, les techniques décrites dans cet article devraient convenir à la plupart des applications.

De manière assez simpliste, on peut dire que l'utilisation d'un multiplicateur avec de nombreux diviseurs entraînera plus de collisions de hachage . Puisque pour un hachage efficace, nous voulons minimiser le nombre de collisions, nous essayons d'utiliser un multiplicateur qui a moins de diviseurs. Un nombre premier par définition a exactement deux diviseurs positifs distincts.

Questions connexes

lubrifiants polygènes
la source
4
Eh, mais il sont nombreux appropriés nombres premiers qui sont soit 2 ^ n + 1 (appelés nombres premiers Fermat ), à savoir 3, 5, 17, 257, 65537ou 2 ^ n - 1 ( nombres premiers de Mersenne ): 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. Cependant 31(et non, par exemple 127) est opté.
Dmitry Bychenko
4
"parce que c'est un premier impair" ... il n'y a qu'un seul premier pair: P
Martin Schneider
Je n'aime pas le libellé «est moins clair, mais c'est traditionnel» dans «Effective Java». S'il ne veut pas entrer dans les détails mathématiques, il devrait plutôt écrire quelque chose comme «a des raisons mathématiques [similaires]». La façon dont il écrit sonne comme si elle n'avait que des antécédents historiques :(
Qw3ry
5

J'ai entendu dire que 31 a été choisi pour que le compilateur puisse optimiser la multiplication au décalage gauche de 5 bits, puis soustraire la valeur.

Steve Kuo
la source
comment le compilateur pourrait-il optimiser de cette façon? x * 31 == x * 32-1 n'est pas vrai pour tous les x après tout. Ce que vous vouliez dire, c'était le décalage gauche 5 (multiplier par 32), puis soustraire la valeur d'origine (x dans mon exemple). Bien que cela puisse être plus rapide qu'une multiplication (ce n'est probablement pas pour les processeurs cpu modernes d'ailleurs), il y a des facteurs plus importants à prendre en compte lors du choix d'une multiplication pour un haschcode (une distribution égale des valeurs d'entrée aux buckets vient à l'esprit)
Grizzly
Faites un peu de recherche, c'est une opinion assez courante.
Steve Kuo
4
L'opinion commune n'est pas pertinente.
fractor
1
@Grizzly, il est plus rapide que la multiplication. IMul ​​a une latence minimale de 3 cycles sur n'importe quel processeur moderne. (voir les manuels d'agner fog) mov reg1, reg2-shl reg1,5-sub reg1,reg2peut s'exécuter en 2 cycles. (le mov est juste un changement de nom et prend 0 cycles).
Johan
3

Voici une citation un peu plus proche de la source.

Cela se résume à:

  • 31 est premier, ce qui réduit les collisions
  • 31 produit une bonne distribution, avec
  • un compromis raisonnable en vitesse
John
la source
3

Commencez par calculer la valeur de hachage modulo 2 ^ 32 (la taille de an int), donc vous voulez quelque chose de relativement premier à 2 ^ 32 (relativement premier signifie qu'il n'y a pas de diviseurs communs). N'importe quel nombre impair ferait l'affaire.

Ensuite, pour une table de hachage donnée, l'index est généralement calculé à partir de la valeur de hachage modulo la taille de la table de hachage, vous voulez donc quelque chose qui soit relativement premier par rapport à la taille de la table de hachage. Souvent, les tailles des tables de hachage sont choisies comme nombres premiers pour cette raison. Dans le cas de Java, l'implémentation de Sun garantit que la taille est toujours une puissance de deux, donc un nombre impair suffirait ici aussi. Il existe également un massage supplémentaire des clés de hachage pour limiter davantage les collisions.

Le mauvais effet si la table de hachage et le multiplicateur avaient un facteur commun npourrait être que dans certaines circonstances, seules 1 / n entrées dans la table de hachage seraient utilisées.

starblue
la source
2

La raison pour laquelle les nombres premiers sont utilisés est de minimiser les collisions lorsque les données présentent des modèles particuliers.

Tout d'abord: si les données sont aléatoires, il n'y a pas besoin d'un nombre premier, vous pouvez faire une opération de mod contre n'importe quel nombre et vous aurez le même nombre de collisions pour chaque valeur possible du module.

Mais lorsque les données ne sont pas aléatoires, des choses étranges se produisent. Par exemple, considérez les données numériques qui sont toujours un multiple de 10.

Si nous utilisons le mod 4, nous trouvons:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Donc à partir des 3 valeurs possibles du module (0,1,2,3), seuls 0 et 2 auront des collisions, ce qui est mauvais.

Si nous utilisons un nombre premier comme 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc

Nous notons également que 5 n'est pas un bon choix mais 5 est premier la raison en est que toutes nos clés sont un multiple de 5. Cela signifie que nous devons choisir un nombre premier qui ne divise pas nos clés, choisir un grand nombre premier est généralement assez.

Donc, si l'on se trompe du côté de la répétition, la raison pour laquelle les nombres premiers sont utilisés est de neutraliser l'effet des motifs dans les clés dans la distribution des collisions d'une fonction de hachage.

Amar Magar
la source
1

31 est également spécifique à Java HashMap qui utilise un int comme type de données de hachage. Ainsi, la capacité maximale de 2 ^ 32. Il est inutile d'utiliser des nombres premiers de Fermat ou de Mersenne plus grands.

DED
la source
0

Cela permet généralement d'obtenir une répartition plus uniforme de vos données entre les seaux de hachage, en particulier pour les clés à faible entropie.


la source