Discussion :

[deebou]

Bonjour,

J'ai un problème avec le valeurs hash stockées dans la table d'une hashmap...

j'ai par exemple une classe :

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
 
class Position {
	public int X, Y;
	public Position(int x, int y) {
		X = x; Y = y;
	}
	@Override
	public boolean equals(Object O) {
		return (X==((Position)O).X && Y==((Position)O).Y) ? true : false;
	}
	@Override
	public int hashCode() {
		return X + (Y<<16);
	}		
}

et une map avec son utilisation:

Code :

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

1
2
3
	public Map<Position, Long> 	mp1 = new HashMap<Position, Long>();
		Position  P1 = new Position(1, 4);
		mp1.put(P1, 0L);

La valeur de hashage est d'après ma classe 0x40001 or je retrouve dans la table de la map (en utilisant le debugger de Eclipse) une valeur de hash 0x40005, comme si la valeur de hash stockée dans la map était faite par un XOR entre les 16 bits de poids forts et les 16 bits de poids faibles.

Pour confirmation P2 = new Position(1,5) qui devrait donner 0x50001 donne en réalité 0x50004.

Ai-je loupé quelque chose dans la théorie des maps, dans l'implémentation de HashMap? Je lis partout que la valeur de hashage est sur 32 bits sans plus de détails.
Toutes les remarques sont bienvenues.

Merci à tous...

[joel.drigo]

Salut,

La HashMap utilise son propre système de hashage et tu n'as pas à t'en préoccuper. La seule chose à garantir c'est que dans l'objet servant de clef, il soit immuable, et que equals() soit bien implémentée ( a.equals(b) == b.equals(a) ) et que hashcode soit bien implémentée, soit que si a.equals(b), alors a.hashCode() == b.hashCode().

[tchize_]

le code utilisé par java 8 pour calculer les hash dans la map

Code :

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

1
2
3
4
static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }

le code de java 7

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
         int h = hashSeed;
         if (0 != h && k instanceof String) {
             return sun.misc.Hashing.stringHash32((String) k);
         }
 
         h ^= k.hashCode();
 
         // This function ensures that hashCodes that differ only by
         // constant multiples at each bit position have a bounded
         // number of collisions (approximately 8 at default load factor).
         h ^= (h >>> 20) ^ (h >>> 12);
         return h ^ (h >>> 7) ^ (h >>> 4);
     }

le code de java 6

Code :

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

1
2
3
4
5
6
7
     static int hash(int h) {
         // This function ensures that hashCodes that differ only by
         // constant multiples at each bit position have a bounded
         // number of collisions (approximately 8 at default load factor).
         h ^= (h >>> 20) ^ (h >>> 12);
         return h ^ (h >>> 7) ^ (h >>> 4);
     }

Bref comme mentionné, c'est la tambouille interne de hashmap.

[deebou]

Merci de vos réponses et en particulier la réponse de tchize_, claire et précise.
Effectivement au vu du code, on n'a pas à s'en préoccuper...
Merci encore, je passe la discussion sur "Résolu".