Qu'est-ce qu'un prime sensible pour le calcul de hashcode? [dupliquer]
Cette question a déjà une réponse ici:
Eclipse 3.5 a une fonctionnalité très intéressante pour générer des fonctions Java hashCode (). Il 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'attributs dans la classe, result = prime * result + attribute.hashCode(); est répété pour chaque attribut supplémentaire. Pour ints .hashCode() peut être omis.)
Cela semble bien, mais pour le choix 31 pour le premier. Il est probablement tiré de l'implémentation de hashCode de Java String , qui a été utilisée pour des raisons de performance qui ont disparu depuis longtemps après l'introduction des 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 les petites valeurs se produisent souvent. Pour Chaîne.hashCode vous trouverez également de nombreuses chaînes courtes avec le même hashcode, par exemple "Ca" et "DB". Si vous prenez un grand premier, ce problème disparaît si vous choisissez le premier droit.
Donc ma question: qu'est ce qu'un bon premier choisir? Quels critères appliquez-vous pour le trouver?
Cela se veut comme une question générale-donc je ne veux pas donner une plage pour i et J. Mais je suppose que dans la plupart des applications, des valeurs relativement petites se produisent plus souvent que de grandes valeurs. (Si vous avez de gros valeurs le choix du premier est probablement sans importance.) Il ne pourrait pas faire beaucoup de différence, mais un meilleur choix est un moyen facile et évident pour améliorer cette - alors, pourquoi ne pas le faire? Commons lang HashCodeBuilder suggère également des valeurs curieusement petites.
(Clarification : ceci est pas un doublon de pourquoi le hashcode () de Java dans String utilise-t-il 31 comme multiplicateur? puisque ma question ne concerne pas l'histoire du 31 dans le JDK, mais sur quoi serait une meilleure valeur dans le nouveau code en utilisant le même modèle de base. Aucune des réponses n'essaie de répondre à cela.)
6 réponses
Je vous recommande d'utiliser 92821. Voici pourquoi.
Pour donner une réponse significative à cela, vous devez savoir quelque chose sur 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 chances de 15 apparaissant comme une valeur dans votre programme sont beaucoup mieux que, disons, 438281923.) Il semble donc une bonne idée de rendre la plus petite collision de hashcode aussi grande que possible en choisissant une premier. Pour 31 ce plutôt mauvais - déjà pour i=-1 et j=31, vous avez la même valeur de hachage comme pour i=0 et j=0.
Comme c'est intéressant, j'ai écrit un petit programme qui a cherché dans toute la gamme int le meilleur premier dans ce sens. C'est-à-dire, pour chaque premier, j'ai cherché 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 j'ai pris le premier où cette valeur minimale est aussi grande que possible.
roulement de tambour: c'est le meilleur prime en ce sens est 486187739 (avec la plus petite collision étant i=-25486, j=67194). Presque aussi bon et beaucoup plus facile à retenir est 92821 avec la plus petite collision étant i=-46272 and j=46016.
Si vous donnez "petit" un autre sens et que vous voulez être le minimum de Math.sqrt(i*i+j*j) pour la collision aussi grande que possible, les résultats sont un peu différents: le meilleur serait 1322837333 avec i=-6815 and j=70091, mais mon 92821 préféré (plus petite collision -46272,46016) est à nouveau presque aussi bon que la meilleure valeur.
Je reconnais qu'il est tout à fait discutable si ces calculs ont beaucoup de sens dans la pratique. Mais je pense que prendre 92821 comme premier a beaucoup plus de sens que 31, sauf si vous avez de bonnes raisons de ne pas le faire.
En fait, si vous prenez un premier si grand qu'il se rapproche de INT_MAX, Vous avez le même problème à cause de l'arithmétique modulo. Si vous vous attendez à hacher principalement des chaînes de longueur 2, peut-être un premier près de la racine carrée de INT_MAX serait le meilleur, si les chaînes que vous Hachez sont plus longues, cela n'a pas tellement d'importance et les collisions sont inévitables de toute façon...
Les Collisions peuvent ne pas être un gros problème... L'objectif principal du hachage est d'éviter d'utiliser des égaux pour les comparaisons 1: 1. Si vous avez une implémentation où equals est" généralement " extrêmement bon marché pour les objets qui sont entrés en collision hashs, alors ce n'est pas un problème (du tout).
En fin de compte, quelle est la meilleure façon de hachage dépend de ce que vous comparez. Dans le cas d'une paire int (comme dans votre exemple), l'utilisation d'opérateurs binaires de base pourrait être suffisante (comme l'utilisation de & ou^).
Vous devez définir votre plage 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 collissions avec de petits nombres. Ne déborde pas à de petits nombres rapidement.
Je veux juste souligner que hashcode n'a rien à voir avec prime. Dans la mise en œuvre JDK
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
J'ai découvert que si vous remplacez 31 avec 27, les résultats sont très similaires.