Discussion :

[LittleBean]

Bonjour,

cela fait plusieurs fois que je tombe sur ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[adiGuba]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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());

On obtient les mêmes hashCode (6) !!!


Maintenant en utilisant un multiplicateur à chaque étape :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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++

[LittleBean]

Merci pour cette réponse

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 ? Est il extrait d'un savant dosage de nombre le premier le plus grand sans exploser la taille du int ?

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[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.

[LittleBean]

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

* 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

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 ?