Ce qui est un bon premier pour hashcode de calcul?

Eclipse 3.5 a une caractéristique très intéressante pour générer Java hashCode() de fonctions. Il pourrait générer, par exemple (légèrement raccourcie:)

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. C'est probablement à partir de la hashCode de la mise en œuvre de Java String, qui a été utilisé pour des raisons de performances qui ont disparu depuis longtemps après l'introduction de matériel de multiplication. Ici, vous avez beaucoup de hashcode collisions pour les petites valeurs de i et de j: par exemple (0,0) et (-1,31) ont la même valeur. Je pense que c'est une Mauvaise Chose(TM), depuis les petites valeurs se produisent souvent. Pour La Chaîne.hashCode vous trouverez également de nombreuses chaînes courtes avec le même hashcode, par exemple "Ca" et "DB". Si vous prenez une grande le premier, ce problème disparaît si vous choisissez le premier à droite.

Donc ma question: qu'est ce qu'un bon premier choisir? Quels critères avez-vous d'appliquer pour le trouver?

Il ne s'agit que d'une question d'ordre général - donc, je ne veux pas donner une gamme de i et j. Mais je suppose que, dans la plupart des applications relativement petites valeurs se produisent plus souvent que les grandes valeurs. (Si vous avez de grandes valeurs, le choix de la prime 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 aussi curieusement petites valeurs.

(Clarification: c'est pas un double de Pourquoi Java est hashCode() en Chaîne de caractères utilisez 31 comme un multiplicateur? depuis que ma question n'est pas concerné par l'histoire de la 31 dans le JDK, mais sur ce que serait une meilleure valeur dans le nouveau code en utilisant le même modèle de base. Aucune des réponses, essayer de répondre à cela.)

31 est toujours bon qu'il ne s'agit pas nécessairement de chargement d'une constante. Sur un processeur ARM (au moins celle qui est utilisée par environ 99.9997% des téléphones mobiles) *31 ne peut être en une seule instruction. Dans la réalité, n'importe quel nombre impair si le premier ou qui n'est pas bonne suffisant.
Je pensais à des programmes de bureau, où il n'a pas d'importance si vous choisissez 31 ou 1327144003. Curieusement, sur ma machine multipliant avec 31 est en fait un peu plus lent - sans doute une optimisation est mal passé. 😎
Les nombres premiers de la forme p = (2^n-1) se prêtent à l'optimisation de x * p = (p << n) - p qui le compilateur le fait habituellement. De Joshua Bloch, Efficace Java, Chapitre 3, Article 9. DONC, la question stackoverflow.com/questions/299304/...
et de se multiplier avec les integer <128 ont un élan supplémentaire à la jvm.. 2^n-1, le premier, petite .. ce qui donne à 31.
Comme je l'ai dit, pour le courant des machines de bureau, cela ne semble pas être une optimisation plus - le temps est le même. Pire encore: sur ma machine multipliant avec 31 a été un peu plus lente, peut-être que la JVM essayé pour "optimiser" par le calcul de x << 5 - x, et c'est effectivement plus lent que d'utiliser le matériel multiplicateur.
Sur i86, il y a une différence, car il y a un mode pour un seul octet immédiate opérande. Vous obtenez une courte instruction et d'un indice de référence que j'ai écrit il y a des années, il a été un peu plus rapide.
Veuillez noter que ceci est très différent de [Pourquoi Java est hashCode() en Chaîne de caractères utilisez 31 comme un multiplicateur?][1] puisque ce n'est pas à propos de l'histoire de l'31, mais sur ce que serait un meilleur choix au lieu d'utiliser 31, sans l'aide d'autres bibliothèques ou entièrement différentes méthodes de calcul de tables de hachage. Aucune des réponses adresses. [1]: stackoverflow.com/questions/299304/...

InformationsquelleAutor Hans-Peter Störr | 2009-12-02

71

Je recommande d'utiliser 92821. Voici pourquoi.

Pour donner une vraie réponse à cette question, vous devez savoir quelque chose sur les valeurs possibles de i et j. La seule chose à laquelle je pense, en général, est, dans de nombreux cas, les petites valeurs sera plus commune 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 faire le moindre hashcode de la collision la plus grande possible par choisir un nombre 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.

Depuis ce qui est intéressant, j'ai écrit un petit programme qui recherche l'ensemble de l'int gamme pour le meilleur premier dans ce sens. C'est, pour chacun, le premier j'ai cherché pour la valeur minimale de Math.abs(i) + Math.abs(j) sur toutes les valeurs de i,j qui ont le même hashcode comme 0,0, puis a pris le premier où cette valeur minimale est la plus grande possible.

Roulement de tambour: le meilleur premier dans ce sens est 486187739 (avec le plus petit collision i=-25486, j=67194). Presque aussi bon et beaucoup plus facile à retenir est 92821 avec la plus petite collision i=-46272 and j=46016.

Si vous donnez des "petits" un autre sens et que vous voulez être au minimum de Math.sqrt(i*i+j*j) pour la collision la plus grande possible, les résultats sont un peu différents: le mieux serait 1322837333 avec i=-6815 and j=70091, mais mon préféré 92821 (la plus petite collision -46272,46016) est à nouveau presque aussi bonne que la meilleure valeur.

Je dois reconnaître que c'est tout à fait discutable de savoir si ces calcul beaucoup de sens dans la pratique. Mais je pense que la prise de 92821 en tant que premier fait beaucoup plus de sens que 31, sauf si vous avez de bonnes raisons de ne pas.
- Vous êtes à la recherche pour un nombre magique pour un de hachage parfait ou presque parfait à n'importe quel taux. Je serais plus intéressé à voir une solution pour arbitraire des intrants jusqu'à la valeur de hachage de taille (par exemple, 4 valeurs de 2 octets 8 octets hashcode), que ce cas particulier de la simple transposition.
- 8 octets hashcode? Au moins en Java c'est 4 octets. De toute façon: vous pouvez continuer le schéma utilisé dans eclipse hashCode génération: résultat = premier * résultat + i; result = premier * résultat + j; et ainsi de suite. Pour ce 92821 est probablement un bon choix comme premier - au moins beaucoup mieux que l'éclipse par défaut 31.
- Non seulement est à l'aide d'une petite constante de mal, de ré-utilisation, il est également faux, que vous obtenez les collisions comme newArrayList("a", "bc").hashCode() == newArrayList("ab", "c").hashCode() (mon exemple mayn fonctionne pas, mais quelque chose de similaire n').
- Vous avez raison, il y a beaucoup beaucoup mieux algorithmes de hachage là-bas. J'essayais simplement d'un point facile, mais qui en vaut amélioration d'un système souvent utilisé un algorithme simple. Si vous voulez vraiment de bonnes propriétés, il existe des bibliothèques qui sont beaucoup mieux, mais c'est souvent exagéré.
- Ce que je veux dire: Même si nous appelons n une bonne constante, de l'utiliser partout dans le monde peuvent pas être de droite car elle génère des conflits inutiles de façon systématique. À l'aide d'une constante pour cordes et un autre pour des listes est à mon humble avis mieux.
- Hmm, hypothèse intéressante. Cependant, mon instinct, c'est que la nature de la distribution pour les différents types sont tellement différents que le problème que vous mentionnez n'est pas ce qui domine. Je suis plus intéressé par ce que j'ai pensé que vous étiez éducation: est-il douteux à l'utilisation répétée de la même prime, pour chaque valeur d'entrée? Je pense qu'on devrait utiliser différent nombres premiers à chaque multiply-add étape.
- Les nombres premiers ne sont pas vraiment mieux que les autres nombres impairs (sauf si vous utilisez à la fois les petites touches et d'un premier de la taille de la table de hachage, qui vous a le plus probablement ne le font pas). Si vous souhaitez utiliser plus constantes, alors vous pouvez aussi remplacer le multiply-add étape par somme de multiples et de obtenir un facteur de près de trois speedup comme un bonus. Si je devais écrire un générateur, j'avais dériver les multiplicateurs de fois le nom de la classe et le nom du champ (ou l'index). Le problème est de savoir comment détecter un bon multiplicateur. Il doit être impair, grandes et ont de drôles de motifs de bits. 😉
- il me surprendrait si à l'aide de constantes différentes pour les différentes classes avaient une augmentation significative (> 10%) pour les prestations, sauf dans de très rares situations. Mais si vous alliez le faire, ne pas essayer de "détecter" un bon multiplicateur: il suffit de faire un tableau de 256, et XOR les octets de la table de hachage du nom de la classe pour obtenir l'indice.
- Je doute aussi, 10%, c'est faisable. Pour une application, il est incroyablement en valeur l'effort. Si nous pouvions redessiner l'ensemble de la Java de hachage, puis 10% pourrait être possible (en évitant stupide collisions comme le hashCode zéro pour toute nouvelle Carte.Entrée avec égalité de clés et de valeurs, etc.) alors même que de 0,1% étant sans doute digne d'amélioration.
- L'idée d'utiliser plusieurs nombres premiers est sûrement un bon qui ne coûte rien, même si je suis un peu à la perte de la façon de dire qui sont les bons. Mais peut-être avec plus de 16 bits fera l'amende juste. Par ailleurs, depuis que vous vous souciez de ce sujet: pourriez-vous peut-être voter pour rouvrir la question? Quelqu'un à tort marqué ce en tant que double, inutilement pour éviter toute nouvelle intéressante réponses, si il y a quelques.
InformationsquelleAutor Hans-Peter Störr
5

En fait, si vous prenez un premier tellement grand qu'elle touche de près à la INT_MAX, vous avez le même problème à cause de l'arithmétique modulo. Si vous vous attendez à 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 vous de hachage sont de plus il n'a pas tellement d'importance et les collisions sont inévitables de toute façon...
- À droite, l'arithmétique modulo rend le problème difficile et intéressant. Je pense que je vais écrire un petit programme pour la recherche d'une bonne solution. 🙂
InformationsquelleAutor Pascal Cuoq
5

Collisions peut-être pas un gros problème... L'objectif principal de la table de hachage est d'éviter de l'aide est égal à 1:1 comparaisons.
Si vous avez une implémentation où égale est "généralement" très bon marché pour les objets qui ont percuté hashs, alors ce n'est pas un problème (à tous).

En fin de compte, quelle est la meilleure façon de hachage dépend de ce que vous comparez. Dans le cas d'un int paire (comme dans votre exemple), en utilisant les opérateurs au niveau du bit pourrait être suffisante (comme à l'aide de & ou ^).
- Bien sûr, il n'a pas beaucoup d'importance, mais en changeant le premier, il est évident et facile à améliorer les choses. Alors pourquoi ne pas le faire?
- D'accord. J'ai principalement destinée à mettre un peu l'accent sur le fait à l'aide de nombres premiers n'est pas le que façon de faire les choses, comme la question a finalement un très "générique" de la portée.
InformationsquelleAutor Romain
3

Vous devez définir votre gamme de 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;
}
```
InformationsquelleAutor Peter Lawrey
3

Moi je préfère 7243. Suffisamment grande pour éviter collissions avec de petits nombres. Ne déborde pas des petits nombres rapidement.
- J'utilise les 1000 premiers nombres premiers comme une pratique source pour les petits nombres premiers primes.utm.edu/lists/small/1000.txt
- Je ne pense pas que débordant de questions - si le premier est assez grand, le résultat sera grande, même après le débordement. Je pensais à quelque chose comme 1327144003.
InformationsquelleAutor Erich Kitzmueller
1

Je veux juste souligner que le hashcode n'a rien à voir avec le premier.
Dans le JDK de mise en œuvre
```
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.
- Les nombres premiers sont un moyen facile de s'assurer que tous les hashcode se produit réellement, de sorte que vous ne perdez pas peu si l'entier espace de les diffuser largement. Je ne suis pas tout à fait sûr si il ya d'autres advandages. Mais vous avez raison, la 27 ne doute que ainsi. C'est donc tout aussi mauvais que le choix initial de 31 vous aurez de très petites code de hachage colissions, trop. 😉
- Pour les tables de hachage de tailles qui sont des puissances de deux, tous vous avez besoin est un étrange multiplicateur, premier ou non. Le premier multiplicateurs sont importants pour le prime de la taille des tables comme ils n'ont pas de facteur commun (sauf si vous êtes assez malchanceux pour utiliser le même premier :D). Autant que je sache, la seule utilisation d'un premier de la taille de la table dans le JDK est en String#intern.
- Un étrange multiplicateur est nécessaires et / ou suffisantes pour quoi exactement? Comme je l'ai expliqué, hashcode les collisions sont mauvais pour la performance et la petite multiplicateurs de générer plus de hashcode collisions, depuis les petites valeurs pour les attributs qui sont plus susceptibles que les grandes valeurs.
- Un étrange multiplicateur est nécessaire afin de ne pas perdre de l'information (le pire des multiplicateurs sont ceux se terminant avec le nombre de zéros binaires). La perte d'information est évidemment mauvais et trivial à éviter. +++ Nous sommes d'accord que les petits multiplicateurs sont également mauvais. +++ Mon point était primarity. Un multiplicateur comme m = 101*103*107*109 est une catastrophe pour une table de hachage de taille 103 (mais personne ne l'utilise à de telles tailles). Pour une puissance de deux de la taille de la table elle est probablement beaucoup mieux que 31. Est-il donc probablement pour un tableau de la taille de la co-prime à m.
- Oui, c'est l'évidence de la propriété, le multiplicateur doit satisfaire. J'essayais de point que vous pouvez facilement faire mieux si vous regardez un peu plus loin, et de réduire le code de hachage de collisions en mettant juste un peu plus de la pensée en elle. Et ces nuire à la performance quelle que soit la taille de la table est.
InformationsquelleAutor neoedmund

Vous devez vous connecter pour publier un commentaire.