Pourquoi utiliser un nombre premier dans hashCode?

Je me demandais juste pourquoi les nombres premiers sont utilisés dans la hashCode() ? Par exemple, lorsque vous utilisez Eclipse pour générer ma 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 à 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 ()

    Parce que vous voulez que le nombre par lequel vous multipliez et le nombre de compartiments que vous insérez pour avoir des factorisations premières orthogonales.

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

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

    Les nombres premiers sont choisis pour mieux répartir les données entre les compartiments de hachage. Si la dissortingbution des entrées est aléatoire et uniformément répartie, le choix du code / module de hachage n’a pas d’importance. Cela a un impact uniquement sur les entrées.

    C’est souvent le cas pour les 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 contre 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 

    Notez la dissortingbution presque parfaite lorsque vous utilisez un module premier ou un module non-premier.

    Cependant, bien que l’exemple ci-dessus soit en grande partie artificiel, le principe général est que lorsque l’on traite d’un modèle d’entrées , l’utilisation d’un module de nombres premiers donnera la meilleure dissortingbution.

    Pour ce que ça vaut, Effective Java 2nd Edition renonce à la question des mathématiques et dit 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 une puissance inférieure à deux, ce qui permet une optimisation binary

    Voici la citation complète, à partir de l’ article 9: Toujours remplacer le hashCode lorsque vous remplacez equals :

    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 nombre premier est moins clair, mais c’est traditionnel.

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

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

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


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

    Peut-être une version ultérieure de la plate-forme fournira-t-elle des fonctions de hachage de pointe pour ses classes et ses méthodes d’utilité afin de 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 simpliste, on peut dire que l'utilisation d'un multiplicateur avec de nombreux diviseurs entraînera davantage de collisions de hachage . Puisque pour un hachage efficace nous voulons minimiser le nombre de collisions, nous essayons d'utiliser un multiplicateur qui comporte moins de diviseurs. Un nombre premier par définition a exactement deux diviseurs positifs distincts.

    Questions connexes

    • Java hashCode d'un champ - la recette, plus un exemple d'utilisation des générateurs d'Apache Commons Lang
    • est-il incorrect de définir un code de hachage d'un object en tant que sum, multiplication, peu importe, de toutes les variables de classe?
    • Guide du débutant absolu pour le transfert de bits?

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

    Voici une citation un peu plus proche de la source.

    Cela se résume à:

    • 31 est prime, ce qui réduit les collisions
    • 31 produit une bonne dissortingbution, avec
    • un compromis raisonnable en vitesse

    D’abord, vous calculez la valeur de hachage modulo 2 ^ 32 (la taille d’un int ), vous voulez donc quelque chose de premier à 2 ^ 32 (relativement premier signifie qu’il n’y a pas de diviseur commun). Tout nombre impair ferait pour cela.

    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, de sorte que vous voulez quelque chose qui soit relativement premier à la taille de la table de hachage. Les tailles des tables de hachage sont souvent choisies comme nombres premiers pour cette raison. Dans le cas de Java, l’implémentation de Sun s’assure 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 pouvait être que, dans certaines circonstances, seulement 1 / n entrées de la table de hachage seraient utilisées.

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

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