Qu’est-ce qu’un premier choix judicieux pour le calcul du hashcode?

Eclipse 3.5 a une fonctionnalité très intéressante pour générer des fonctions Java hashCode (). Cela générerait par exemple (légèrement raccourci 🙂

class HashTest { int i; int j; public int hashCode() { final int prime = 31; int result = prime + i; result = prime * result + j; return result; } } 

(Si vous avez plus d’atsortingbuts dans la classe, result = prime * result + atsortingbute.hashCode(); est répété pour chaque atsortingbut supplémentaire. Pour ints .hashCode () peut être omis.)

Cela semble bien, mais pour le choix 31 pour le prime. Il est probablement tiré de l’ implémentation hashCode de Java Ssortingng , qui a été utilisée pour des raisons de performances depuis longtemps après l’introduction de multiplicateurs matériels. Ici, vous avez beaucoup de collisions de hashcode pour les petites valeurs de i et j: par exemple (0,0) et (-1,31) ont la même valeur. Je pense que c’est une mauvaise chose (TM), car de petites valeurs se produisent souvent. Pour Ssortingng.hashCode, vous trouverez également de nombreuses chaînes courtes avec le même code de hachage, par exemple “Ca” et “DB”. Si vous prenez un grand prime, ce problème disparaît si vous choisissez le droit premier.

Donc, ma question: qu’est-ce qu’un bon premier à choisir? Quels critères appliquez-vous pour le trouver?

Cela se veut une question générale – je ne veux donc pas donner une plage pour i et j. Mais je suppose que dans la plupart des applications, des valeurs relativement faibles se produisent plus souvent que des valeurs élevées. (Si vous avez de grandes valeurs, le choix du nombre premier n’est probablement pas important.) Cela ne fera peut-être pas beaucoup de différence, mais un meilleur choix est un moyen facile et évident d’améliorer cela – alors pourquoi ne pas le faire? Commons lang HashCodeBuilder suggère aussi curieusement de petites valeurs.

( Clarification : il ne s’agit pas d’ un doublon de Pourquoi hashCode () de Ssortingng dans Ssortingng utilise-t-il 31 comme multiplicateur? Ma question ne concerne pas l’historique des 31 du JDK, mais la valeur du nouveau code. en utilisant le même modèle de base. Aucune des réponses ne tente d’y répondre.)

Je recommande d’utiliser 92821 . Voici pourquoi.

Pour donner une réponse significative à cette question, vous devez connaître les valeurs possibles de i et j . La seule chose à laquelle je peux penser en général est que, dans de nombreux cas, les petites valeurs seront plus courantes que les grandes valeurs. (Les probabilités de 15 apparaissant comme une valeur dans votre programme sont bien meilleures que, disons, 438281923.) Il semble donc judicieux de faire la plus petite collision de hachage possible en choisissant un nombre premier approprié. Pour 31 cela est plutôt mauvais – déjà pour i=-1 et j=31 vous avez la même valeur de hachage que pour i=0 et j=0 .

Comme ceci est intéressant, j’ai écrit un petit programme qui cherchait le meilleur nombre entier dans ce sens. C’est-à-dire que pour chaque prime j’ai recherché la valeur minimale de Math.abs(i) + Math.abs(j) sur toutes les valeurs de i,j qui ont le même hashcode que 0,0 , puis ont pris le premier où cela la valeur minimale est la plus grande possible.

Drumroll : le meilleur résultat dans ce sens est 486187739 (la plus petite collision étant i=-25486, j=67194 ). 92821 est presque aussi bon et facile à retenir, la plus petite collision étant i=-46272 and j=46016 .

Si vous donnez à “small” une autre signification et que vous voulez être le minimum de Math.sqrt(i*i+j*j) pour la collision la plus grande possible, les résultats sont un peu différents: le meilleur serait 1322837333 avec i=-6815 and j=70091 , mais mon préféré 92821 (la plus petite collision -46272,46016 ) est encore presque aussi bon que le meilleur rapport qualité-prix.

Je reconnais qu’il est tout à fait discutable que ces calculs aient un sens dans la pratique. Mais je pense que prendre 92821 comme premier ministre est beaucoup plus sensé que 31, à moins que vous ayez de bonnes raisons de ne pas le faire.

En fait, si vous prenez un nombre si important qu’il est proche de INT_MAX , vous avez le même problème à cause de l’arithmétique modulo. Si vous prévoyez de hacher la plupart du temps des chaînes de longueur 2, peut-être qu’un premier près de la racine carrée d’ INT_MAX serait le mieux, si les chaînes que vous hachez sont plus longues, les collisions sont inévitables …

Les collisions ne sont peut-être pas un gros problème … Le but principal du hachage est d’éviter d’utiliser des équivalents pour des comparaisons 1: 1. Si vous avez une implémentation où égal à “généralement” extrêmement bon marché pour les objects qui ont des hashs entrés en collision, alors ce n’est pas un problème (du tout).

En fin de compte, le meilleur moyen de hacher dépend de ce que vous comparez. Dans le cas d’une paire int (comme dans votre exemple), l’utilisation d’opérateurs binarys de base pourrait suffire (en utilisant & ou ^).

Vous devez définir votre intervalle pour i et j. Vous pouvez utiliser un nombre premier pour les deux.

 public int hashCode() { http://primes.utm.edu/curios/ ;) return 97654321 * i ^ 12356789 * j; } 

Je choisirais 7243. Assez grand pour éviter les collisions avec de petits nombres. Ne déborde pas rapidement vers de petits nombres.

Je veux juste souligner que le hashcode n’a rien à voir avec prime. Dans l’implémentation JDK

 for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } 

J'ai trouvé si vous remplacez 31 par 27 , le résultat est très similaire.