Qu'est-ce qu'un premier raisonnable pour le calcul de hashcode?

Question

Eclipse 3.5 a une fonctionnalité très pratique 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ée pour chaque attribut supplémentaire. Pour ints .hashCode () peut être omise.)

Cela semble bien, mais pour le choix 31 pour le premier. Il est probablement tiré de la hashCode mise en œuvre de Java chaîne , qui a été utilisé pour des raisons de performance qui ont disparu depuis longtemps après l'introduction de multiplicateurs matériels. Vous trouverez de nombreux collisions 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), étant donné que 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 premier, ce problème disparaît si vous choisissez le premier droit.

Alors, ma question: qu'est-ce qu'un bon premier choix? Quels sont les critères que vous le trouver?

Ceci est conçu comme une question générale - donc je ne veux pas donner une fourchette pour i et j. Mais je suppose que dans la plupart des applications des valeurs relativement petites sont plus souvent que les grandes valeurs. (Si vous avez de grandes le choix du premier est probablement sans importance.) Il pourrait ne pas faire beaucoup de différence, mais un meilleur choix est un moyen facile et évident pour améliorer cela - alors pourquoi ne pas le faire? Commons lang HashCodeBuilder suggère aussi curieusement les petites valeurs.

( Précision : c'est pas un double de Pourquoi le hashCode de Java () dans la chaîne utiliser 31 comme un multiplicateur? puisque ma question ne porte pas sur l'histoire du 31 dans le JDK, mais ce serait une meilleure valeur dans le code nouveau en utilisant le même modèle de base. Aucun des réponses essayer là pour répondre.)

Answer 1

Je recommande d'utiliser 92821 . Voici pourquoi.

Pour donner une réponse significative à ce que vous devez savoir quelque chose sur les valeurs possibles de i et j. La seule chose que je peux penser en général, que dans de nombreux cas, les petites valeurs seront plus fréquentes que les grandes valeurs. (Les chances de 15 apparaissant comme valeur dans votre programme sont beaucoup mieux que, disons, 438281923.) Il semble donc une bonne idée de faire la collision hashcode plus petit aussi grand que possible en choisissant une prime appropriée. Pour 31 ce assez mauvais - déjà i=-1 et j=31 vous avez la même valeur de hachage que pour i=0 et j=0

.

Depuis ce qui est intéressant, j'ai écrit un petit programme qui recherche toute la gamme int pour le meilleur choix dans ce sens. C'est, pour chaque premier que je recherchais 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 pris le premier où cette valeur minimale est aussi grande que possible.

Drumroll : le meilleur choix dans ce sens est 486187739 (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érentes: le mieux serait 1322837333 avec i=-6815 and j=70091, mais mon 92821 préféré (la plus petite collision -46272,46016 ) est à nouveau presque aussi bon que la meilleure valeur.

Je reconnais qu'il est tout à fait discutable si ce calcul beaucoup de sens dans la pratique. Mais je pense que la prise de 92821 en tant que premier est beaucoup plus sensé que 31, à moins que vous avez de bonnes raisons de ne pas.

Answer 2

En fait, si vous prenez un premier si grand qu'il se rapproche de INT_MAX, vous avez le même problème en raison de l'arithmétique modulo. Si vous prévoyez de hachage pour la plupart des chaînes de longueur 2, peut-être un premier près de la racine carrée de INT_MAX serait mieux, si les chaînes que vous hachage sont plus il n'a pas d'importance tant et collisions sont inévitables quand même ...

Answer 3

Collisions ne peut pas être un gros problème ... L'objectif principal du hachage est d'éviter d'utiliser égaux pour 1: 1 comparaisons. Si vous avez une implémentation où est égal à « généralement » extrêmement pas cher pour des objets qui sont entrés en collision hashs, alors ce n'est pas un problème (du tout).

En fin de compte, ce qui 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), en utilisant les opérateurs de base au niveau du bit pourrait être suffisante (en utilisant & ou ^).

Answer 4

Vous devez définir votre gamme 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;
}

Answer 5

Je choisirais 7243. Assez grand pour éviter les collisions avec un petit nombre. Ne déborde pas à un petit nombre rapidement.

Answer 6

Je veux juste souligner que hashcode n'a rien à voir avec le premier. Dans la mise en œuvre JDK

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

J'ai trouvé si vous remplacez 31 27 , le résultat sont très similaires.