Pourquoi utiliser un nombre premier dans le hashCode?
je me demandais juste pourquoi ces nombres premiers sont utilisés dans la méthode hashCode() d'une classe? Par exemple, lorsque vous utilisez Eclipse pour générer ma méthode hashCode() il y a toujours le nombre premier 31 utilisé:
public int hashCode() {
final int prime = 31;
//...
}
, les Références:
Voici une bonne introduction sur le Hashcode et l'article sur la façon dont le hachage fonctionne que j'ai trouvé (C# mais les concepts sont transférables): Eric Lippert les lignes Directrices et les règles pour GetHashCode ()
8 réponses
parce que vous voulez le nombre que vous multipliez par et le nombre de seaux que vous insérez pour avoir des factorisations de prime orthogonales.
supposons qu'il y ait 8 seaux à insérer. Si le nombre que vous utilisez pour multiplier par est un certain multiple de 8, alors le seau inséré dans ne sera déterminé que par l'entrée la moins significative (celle qui n'a pas été multipliée du tout). Similaire entrées en collision. Pas bon pour une fonction de hachage.
31 est un premier assez grand que le nombre de seaux est peu probable d'être divisible par elle (et en fait, les implémentations modernes de java HashMap gardent le nombre de seaux à une puissance de 2).
sont choisis pour distribuer le mieux les données parmi les seaux 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. Elle n'a d'impact que lorsqu'il y a un certain schéma dans les entrées.
C'est souvent le cas lorsqu'il s'agit de lieux de mémoire. Par exemple, tous les entiers de 32 bits sont alignés à des adresses divisibles par 4. Consultez le tableau ci-dessous pour visualiser les effets de l'utilisation d'un premier rapport au premier module:
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 lors de l'utilisation d'un module prime par rapport à un module non prime.
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 pattern of inputs , en utilisant un module de nombre premier donnera la meilleure distribution.
Pour ce que ça vaut, Effective Java 2nd Edition à la main renonce à travers le problème de mathématiques et de dire que la raison de choisir 31 est:
- parce que c'est un prime Impair, et c'est "traditionnel" d'utiliser des primes
- c'est aussi un de moins qu'une puissance de deux, ce qui permet une optimisation en bits
Voici la citation complète de Item 9: always override hashCode lorsque vous outrepassez equals :
la valeur 31 a été choisie parce que c'est 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.
une belle propriété de 31 est que la multiplication peut être remplacée par un décalage ( §15.19 ) et soustraction pour une meilleure performance:
31 * i == (i << 5) - iVMs modernes font ce genre d'optimisation automatiquement.
bien que la recette de cet article fournisse des fonctions de hachage raisonnablement bonnes, elle ne fournit pas de fonctions de hachage à la fine pointe de la technologie, 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, mieux à gauche pour les mathématiciens et l'ordinateur théorique scientifique.
peut-être une version ultérieure de la plate-forme fournira des fonctions de hachage de pointe pour ses classes et méthodes d'utilité pour permettre aux programmeurs moyens de construire de telles fonctions de hachage. Entre-temps, les techniques décrites dans ce point devraient être adéquates pour la plupart des applications.
plutôt simpliste, on peut dire que l'utilisation d'un multiplicateur avec de nombreux diviseurs se traduira par Plus de hachage collisions . 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 distincts, diviseurs positifs.
questions connexes
- hashCode Java d'un champ - la recette, plus un exemple d'utilisation des constructeurs D'Apache Commons Lang
- est-il incorrect de définir un hashcode d'un objet comme la somme, la multiplication, n'importe quoi, de toutes les variables de classe hashcodes?
- Absolue Guide du Débutant pour le Décalage de Bits?
j'ai entendu dire que 31 a été choisi de sorte que le compilateur peut optimiser la multiplication à gauche décalage de 5 bits puis soustraire la valeur.
tout d'abord, vous calculez la valeur de hachage modulo 2^32 (la taille d'un 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 pour que.
alors pour une table de hash donnée l'indice est généralement calculé à partir de la valeur de hash modulo la taille de la table de hash, donc vous voulez quelque chose qui est relativement premier à la taille de la table de hash. Souvent les tailles des tables de hachage sont choisies comme nombres premiers pour cette raison. Dans le cas de Java, L'implémentation Sun s'assure que la taille est toujours une puissance de deux, donc un nombre impair suffirait ici aussi. Il y a aussi quelques massages supplémentaires des touches 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 seulement 1/N entrées dans la table de hachage seraient utilisés.
il aide généralement à obtenir une répartition plus uniforme de vos données parmi les seaux de hachage, en particulier pour les touches de faible entropie.
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 ne sert à rien d'utiliser de plus grands nombres premiers de Fermat ou de Mersenne.