Discussion :

[khaigo]

Bonjour,

je cherche à comprendre le principe utilisé par les HashMap(en quoi se basant pour déterminer l'unicité de la clé...) ainsi que leur utilisation de la methode equals() et hashcode(),

merci d'avance,
Cordialement

[ttttnht]

Bonjour,

Tu peux lire ceci http://java.developpez.com/faq/java/

[khaigo]

Voici le problème que j'ai rencontré et qui pourra interesser les prochains java certifié:

import java.util.*;
class MapEQ {
public static void main(String[] args) {
Map<ToDos, String> m = new HashMap<ToDos, String>();
ToDos t1 = new ToDos("Monday");
ToDos t2 = new ToDos("Monday");
ToDos t3 = new ToDos("Tuesday");
m.put(t1, "doLaundry");
m.put(t2, "payBills");
m.put(t3, "cleanAttic");
System.out.println(m.size());
} }
class ToDos{
String day;
ToDos(String d) { day = d; }
public boolean equals(Object o) {
return ((ToDos)o).day == this.day;
}
// public int hashCode() { return 9; }
}
Which is correct? (Choose all that apply.)
A. As the code stands it will not compile.
B. As the code stands the output will be 2.
C. As the code stands the output will be 3.
D. If the hashCode() method is uncommented the output will be 2.
E. If the hashCode() method is uncommented the output will be 3.
F. If the hashCode() method is uncommented the code will not compile.

moi j'au choisi la reponse B puisque les hashmap ne permet pas la duplication des clés alors que la réponse correcte est C et D!!!

[thelvin]

moi j'au choisi la reponse B puisque les hashmap ne permet pas la duplication des clés

Rappelons-nous que c'est une classe *Hash*Map. Le fait qu'il ne permette pas la duplication des clés dépend du hashCode() de ces clés. La méthode equals() pour différencier deux clés n'est appelée que si leurs hashCode() sont identiques.

Or, dans le programme donné, hashCode() est commenté, ce qui veut dire que leur méthode hashCode() est héritée de la classe Object, où chaque objet distinct a un hashCode distinct.
Il s'agit d'une violation de contrainte sur la redéfinition de equals() et hashCode(), qui dit que si on redéfinit equals() ou hashCode(), on doit faire en sorte que a.equals(b) == true implique que a.hashCode() == b.hashCode().

Bref, ce programme utilise 3 clés avec chacune son hashCode différent, donc le HashMap n'appelle pas equals() et il accepte les 3 entrées distinctes.

Si on décommente hashCode(), là les 3 clés ont un hashCode identique, elles sont donc différenciées en appelant equals() et deux d'entre elles sont déterminées égales par cette méthode. Donc le HashMap n'accepte que 2 entrées distinctes.

Ce n'est pas évident évident, je trouve.

Surtout qu'au fond, tout le monde ne sait pas que "Monday" == "Monday".

[Fmunch]

Par contre un piège traitre à propos des Maps, c'est que les TreeMap et HashMap utilisent d'autres critères d'égalités !!!

[adiGuba]

Salut,

moi j'au choisi la reponse B puisque les hashmap ne permet pas la duplication des clés alors que la réponse correcte est C et D!!!

Les réponses C & D sont normales.

Les Map utilisent des index basé sur le hashCode pour rechercher rapidement les clefs. Cela permet d'éviter de comparer un à un toutes les clefs de la Map.

C'est tout l'intérêt des Map sur de grosse quantité de données


Pour rechercher une clef, elle suit donc ces étapes :

• Elle récupère le hashCode de la clef, ce qui permet de récupérer un nombre limité de clef contenu dans la Map. En fait il faut considérer que les clef avec le même hashCode sont "rangé" ensemble...
• Elle utilise ensuite equals() pour vérifier réellement l'égalité des clefs, mais seulement sur les clefs ayant le même hashCode.

Cela permet une recherche rapide des clef même sur de grand ensemble !


Que se passe-il ici ?
La méthode hashCode() est commenté, et donc on hérite de l'implémentation de base qui tente au maximum de renvoyer un nombre différent pour chaque instance. Il y a de très forte chance que tes 3 instance ait donc un hashCode différent.

Du coup les différentes clefs sont "rangées" à des emplacements différents, et on ne passe pas par la comparaison.

En fait le problème vient du fait que la méthode hashCode() est incorrect. Lorsque tu redéfini equals() tu dois redéfinir hashCode() de manière cohérente (voir FAQ : equals() et hashCode()).



Ici la Map considère que les objets ne peuvent pas être égaux étant-donné qu'ils ont tous un hashCode différent, et du coup elle n'utilise pas equals().


En fait ce "problème" vient du fait que la classe ToDos ne respecte pas la règle de base entre equals() et hashCode() :

• Si A.equals(B) alors A.hashCode() == B.hashCode()
• Si A.hashCode()!=B.hashCode() alors A.equals(B)==false

(attention les réciproques ne sont pas vrai)



Que se passe-t-il lorsqu'on décommente la méthode hashCode() qui se contente de retourner 9 ?
On respecte désormais ces règles, et la Map va donc comparer les clefs entre elle afin de réellement vérifier l'identité des clefs, et donc éviter le doublons.


Toutefois cette implémentation de hashCode() n'est pas du tout optimisé car cela va placer toutes les clefs ensemble, ce qui fait perdre tout l'intérêt des Map...




Dans le même genre, il faut éviter d'utiliser des objets muables comme clef, car on risque alors de ne plus pouvoir y accéder...


a++

[khaigo]

merci les amis,
c'est très riche comme réponses,
bonne journée