Quelle est une prime raisonnable pour le calcul du hashcode ?

Question

Eclipse 3.5 dispose d'une fonctionnalité très intéressante permettant de générer des fonctions Java hashCode(). Il génère 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 les ints, .hashCode() peut être omis).

Cela semble bien mais pour le choix 31 pour la prime. Il est probablement tiré du implémentation de hashCode de Java String qui était utilisé pour des raisons de performances qui ont disparu depuis l'introduction des multiplicateurs matériels. Ici, il y a de nombreuses collisions de codes de hachage pour de 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), puisque les petites valeurs se produisent souvent. Pour String.hashCode, vous trouverez également de nombreuses chaînes courtes avec le même hashcode, par exemple "Ca" et "DB". Si vous prenez un grand nombre de valeurs premières, ce problème disparaît si vous choisissez bien la valeur première.

Ma question est donc la suivante : quel est le bon prime à choisir ? Quels critères appliquez-vous pour le trouver ?

Il s'agit d'une question d'ordre général - je ne souhaite donc pas donner une fourchette pour i et j. Mais je suppose que dans la plupart des applications, les valeurs relativement petites sont plus fréquentes que les grandes. () Cela ne fait peut-être pas une grande différence, mais un meilleur choix est un moyen facile et évident d'améliorer la situation - alors pourquoi ne pas le faire ? Lang Commons HashCodeBuilder suggère également des valeurs curieusement petites.

( Clarification C'est pas un duplicata de Pourquoi la fonction hashCode() de Java dans String utilise-t-elle 31 comme multiplicateur ? puisque ma question ne porte pas sur l'historique de la 31 dans le JDK, mais sur ce qui serait une meilleure valeur dans un nouveau code utilisant le même modèle de base. Aucune des réponses qui s'y trouvent ne tente de répondre à cela).

Answer 1

Je recommande d'utiliser 92821 . Voici pourquoi.

Pour donner une réponse significative à cette question, il faut savoir quelles sont les valeurs possibles de i y 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. (Les chances que 15 apparaisse comme une valeur dans votre programme sont bien meilleures que, disons, 438281923). Il semble donc judicieux de rendre la plus petite collision de code de hachage aussi grande que possible en choisissant un nombre premier approprié. Pour 31, c'est plutôt mauvais - déjà pour i=-1 y j=31 vous avez la même valeur de hachage que pour i=0 y j=0 .

Puisque c'est intéressant, j'ai écrit un petit programme qui recherche dans toute la gamme des int la meilleure prime dans ce sens. C'est-à-dire que pour chaque nombre 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 code de hachage que 0,0 puis on prend la prime où cette valeur minimale est la plus grande possible.

Roulements de tambour le meilleur nombre premier dans 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 un autre sens à "petit" 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é est le 92821 (plus petite collision). -46272,46016 ) est à nouveau presque aussi bon que la meilleure valeur.

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

Answer 2

En fait, si vous prenez une prime si grande qu'elle se rapproche de INT_MAX vous avez le même problème à cause de l'arithmétique modulo. Si vous pensez hacher principalement des chaînes de longueur 2, peut-être un nombre premier proche de la racine carrée de INT_MAX serait le mieux, si les chaînes que vous hachurez sont plus longues, ce n'est pas si important et les collisions sont de toute façon inévitables...

Answer 3

Les collisions ne sont peut-être pas un problème si important... Le but premier du hachage est d'éviter d'utiliser les é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 ont des hashs en collision, alors ce n'est pas un problème (du tout).

En fin de compte, la meilleure méthode de hachage dépend de ce que vous comparez. Dans le cas d'une paire d'int (comme dans votre exemple), l'utilisation d'opérateurs binaires de base pourrait être suffisante (comme l'utilisation de & ou ^).

Answer 4

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

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

Answer 5

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