hashcode + 29

Version imprimable

hashcode + 29

Bonjour,

cela fait plusieurs fois que je tombe sur ce code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public int hashCode() {
234         int hashCode = (this.from == null ? 0 : this.from.hashCode());
235         hashCode = 29 * hashCode + (this.replyTo == null ? 0 : this.replyTo.hashCode());
236         for (int i = 0; this.to != null && i < this.to.length; i++) {
237             hashCode = 29 * hashCode + (this.to == null ? 0 : this.to[i].hashCode());
238         }
239         for (int i = 0; this.cc != null && i < this.cc.length; i++) {
240             hashCode = 29 * hashCode + (this.cc == null ? 0 : this.cc[i].hashCode());
241         }
242         for (int i = 0; this.bcc != null && i < this.bcc.length; i++) {
243             hashCode = 29 * hashCode + (this.bcc == null ? 0 : this.bcc[i].hashCode());
244         }
245         hashCode = 29 * hashCode + (this.sentDate == null ? 0 : this.sentDate.hashCode());
246         hashCode = 29 * hashCode + (this.subject == null ? 0 : this.subject.hashCode());
247         hashCode = 29 * hashCode + (this.text == null ? 0 : this.text.hashCode());
248         return hashCode;
249     }

source :
http://www.jdocs.com/page/AjaxSourceCode?oid=61772

Quelle est la signification de ce 29 ? :?

Merci

Salut,

Ce nombre permet de faire fortement varier le hashCode() selon les valeurs des différents hashCode() des attributs, et donc d'éviter que des objets propres aient le même hashCode().

Petit exemple avec une implémentation "basique" de hashCode() qui se contente d'ajouter les hashCode des différents attributs :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class HashCodeExample { final int hash1; final int hash2; final int hash3; public HashCodeExample(int hash1, int hash2, int hash3) { this.hash1 = hash1; this.hash2 = hash2; this.hash3 = hash3; } @Override public boolean equals(Object obj) { if (obj==this) return true; if (obj instanceof HashCodeExample) { HashCodeExample other = (HashCodeExample) obj; return this.hash1==other.hash1 && this.hash2==other.hash2 && this.hash3==other.hash3; } return false; } @Override public int hashCode() { return hash1 + hash2 + hash3; } }
Prenons un exemple avec des objets différents mais proche :
Code:

1 2 3 4 5 HashCodeExample h1 = new HashCodeExample(1, 2, 3); HashCodeExample h2 = new HashCodeExample(3, 1, 2); System.out.println(h1.hashCode()); System.out.println(h2.hashCode());
:arrow: On obtient les mêmes hashCode (6) !!!

Maintenant en utilisant un multiplicateur à chaque étape :
Code:

1 2 3 4 5 6 7 @Override public int hashCode() { int result = hash1; result = result * 29 + hash2; result = result * 29 + hash3; return result; }
Les valeurs vont changer plus rapidement et tu obtiens bien deux hashCodes très différents, ce qui permet d'éviter les "conflits" et donc d'optimiser le traitement des Map...

Le choix de ce multiplier importe peu, même si il est conseillé de prendre un nombre premier (mais je ne sais pas précisément pourquoi).

A noter également qu'en règle général il est également conseillé de prendre une valeur initial selon le même principe :
Code:

1 2 3 4 5 6 7 8 @Override public int hashCode() { int result = 7; result = result * 29 + hash1; result = result * 29 + hash2; result = result * 29 + hash3; return result; }
Plus d'info : Pourquoi et comment redéfinir la méthode hashCode() ?

a++

17/11/2009, 15h32
LittleBean

Merci pour cette réponse :ccool:

Je comprends bien maintenant les tenants et aboutissants mais ce 29 me perturbe encore un peu ...

Intuitivement j'aurais pris 10 ...
puis je l'aurais amélioré pour prendre un nombre premier : 13
on sait tous que 13 c'est la poisse ... donc va pour : 17

Mais pourquoi ce 29 8O ? Est il extrait d'un savant dosage de nombre le premier le plus grand sans exploser la taille du int :aie:?

:?
17/11/2009, 17h28
professeur shadoko
question à Adiguba: dans l'exemple les objets hash1, hash2, hash3 ne "distribuent" pas bien individuellement une valeur de hash.

maintenant soit trois objets hash1 d'un type Truc qui aie un bon hashCode ... (on peut réver)
est ce que:
Code:

1 2 hash1.hashCode()^ hash2.hashCode()^ hahs3.hahsCode()
donne une bonne distribution?
est-elle meilleure que le 29 * et ses parents ...?
un avis des matheux?
18/11/2009, 02h48
dingoth

Tout est une histoire de rotation de bits.

* 29 correspond à 11101

Donc, si je prends un nombre x, j'obtiens x << 4 + x << 3 + x << 2 + x. La rotation des bits est suffisante et change très bien le nombre.

Maintenant, pourquoi des nombres premiers ? Tout simplement parce que dans la plupart des tables de hashing, la longueur de la table est un multiple d'un nombre choisi. Et qu'est-ce qui n'est jamais multiple d'un nombre +/- traditionnel ? Les nombres premiers ! Les objets sont donc mieux répartis dans une telle table de hashing, et il ne faudra, en moyenne, pas aller trop en profondeur lorsqu'on cherche des valeurs dans les chaines de pointeurs d'une HashMap.
18/11/2009, 11h02
LittleBean

Citation:

Maintenant, pourquoi des nombres premiers ? Tout simplement parce que dans la plupart des tables de hashing, la longueur de la table est un multiple d'un nombre choisi. Et qu'est-ce qui n'est jamais multiple d'un nombre +/- traditionnel ? Les nombres premiers ! Les objets sont donc mieux répartis dans une telle table de hashing, et il ne faudra, en moyenne, pas aller trop en profondeur lorsqu'on cherche des valeurs dans les chaines de pointeurs d'une HashMap.

Je me doutais d'un truc comme ça mais avoir une confirmation est super
merci :ccool:

Citation:

* 29 correspond à 11101

Donc, si je prends un nombre x, j'obtiens x << 4 + x << 3 + x << 2 + x. La rotation des bits est suffisante et change très bien le nombre.

ah je me disais qu'il y avait une explication :)
Merci :mrgreen:

mais pourquoi ne pas prendre un nombre à 30 bit ( taille max du int je crois ?) pour avoir le plus grand motif non répété possible ?

Bah, pour être franc, c'est la première fois que j'entends parler de 29. D'habitude, les nombres sont compris entre 37 (premier nombre premier après 32) et 61 parce qu'ils bougent 6 bits. Toutefois 31 est un excellent candidat également parce que c'est un [ame=http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne]nombre premier de Mersenne[/ame] que la JVM optimise x * 31 en (x<< 5) - x.

Ces nombres sont de bons compromis entre rapidité du calcul du hash (de par leur petitesse) et efficience le bit-shuffling.

Choisir un nombre très grand a plusieurs inconvénients : les capacités d'int sont vite dépassées et la multiplication des nombres est moins évidentes en termes de performance. L'on peut noter toutefois que dans l'absolu, bouger 5 bits ne sera pas efficace très longtemps, puisqu'après 7 opérations maximum, on aura dépassé l'overflow d'un int.

Donc, en résumé, on choisit des nombres premiers relativement petits, mais pas trop pour :
1. leur capacité à bien shuffler les bits
2. leur capacité à bien se répartir dans des tables de hashing standard
3. leur capacité à hasher de manière plus rapide que d'autres
4. leur capacité à supporter peu de hashes sans se perdre trop de perfs

D'aucuns pourront objecter que les points 3 et 4 ne sont plus trop valides vu les perfs actuelles des machines et la manière dont les bits sont gérés au niveau du CPU, mais actuellement, la tradition fait conserver ces nombres.

N'oublions pas qu'il est toutefois recommandé, dans le contexte de la méthode de hashing de fournir d'emblée un nombre par défaut afin d'améliorer la répartition dans les tables de hashing. Dans ce cadre-là, on entend souvent le nombre 17.

Exemple d'une méthode de hashing complète :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class MyObject { int val1; String val2; double val3; public int hashCode() { int result = 17; result = 31 * result + val1; result = 31 * result + val2.hashCode(); long tmp = Double.doubleToLongBits(val3); result = 31 * result + (int)(tmp ^ (tmp >>> 32)); return result; } }
En outre, si la classe est immuable (tous les champs sont soit finaux, soit immuables), on peut même stocker le nombre hashé pour gagner en perfs :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class MyObject { final int val1; final String val2; final double val3; private volatile hashCode; public int hashCode () { int result = hashCode; if (result == 0) { result = 17; result = 31 * result + val1; result = 31 * result + val2.hashCode(); long tmp = Double.doubleToLongBits(val3); result = 31 * result + (int)(tmp ^ (tmp >>> 32)); hashCode = result; } return result; } }
Note, pour m'aider dans l'argumentation, j'ai utilisé le bouquin Effective Java, 2nd Edition où tout est expliqué avec bien plus de détails.

18/11/2009, 16h13
LittleBean

Un grand merci pour cette longue explication:)

Citation:

Note, pour m'aider dans l'argumentation, j'ai utilisé le bouquin Effective Java, 2nd Edition où tout est expliqué avec bien plus de détails.

Je vais aller voir ça
19/11/2009, 08h57
professeur shadoko

remarques sur le poste de Dingoth:
dans l'exemple on a deux hashCode qui sont (a priori) bien ventilés: ceux du String et ceux de Double (oui Double avec un grand "D" calcule le hash de la manière indiquée).
donc si on fait une opération de multiplication comme indiquée sur le champ int puis ensuite on fait des XOR entre les trois hashCodes est-ce qu'on n'a pas statistiquement une meilleure ventilation?
(je n'en sais rien! hé les matheux! Help!)
19/11/2009, 09h35
dingoth

Bien sûr que c'est bon !

L'idéal dans une génération de hashCode, c'est de tendre vers la dispersion. Mais il vaut toujours mieux conserver une méthode rapide et simple de classe en classe (en changeant quelques paramètres tels les deux entiers proposés).

Le bit-shuffling proposé par la multiplication et l'addition est déjà suffisante. D'ailleurs si l'on regarde bien, l'addition est une sorte de XOR avec report. Donc, XOR ou addition, pas tellement de différence.