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 31
utilisé:
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 ()
Réponses:
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).
la source
(x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
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:
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.
la source
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:
Voici le devis complet, à partir de l' article 9: Toujours remplacer
hashCode
lorsque vous remplacezequals
: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
la source
3, 5, 17, 257, 65537
ou 2 ^ n - 1 ( nombres premiers de Mersenne ):3, 7, 31, 127, 8191, 131071, 524287, 2147483647
. Cependant31
(et non, par exemple127
) est opté.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.
la source
mov reg1, reg2-shl reg1,5-sub reg1,reg2
peut s'exécuter en 2 cycles. (le mov est juste un changement de nom et prend 0 cycles).Voici une citation un peu plus proche de la source.
Cela se résume à:
la source
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
n
pourrait être que dans certaines circonstances, seules 1 / n entrées dans la table de hachage seraient utilisées.la source
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.
la source
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.
la source
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