HashSet et doublons

Version imprimable

HashSet et doublons

Bonjour,
Je constate dans mon code une chose bizarre,
J'ai crée une classe

Code:

Pair<U,V>

avec les membres hashCode et equals,
Ensuite j'ai une classe Instruction sans equals ou hashCode
Puis je définis

Code:

Set<Pair<String, Pair<Set<Integer>, Instruction>>> varWrite=new HashSet<...>()

Ensuite j'insert des élément dedans, et comme j'ai une boucle infinie je regarde le set avec le code suivant (en bref j'imprine les hashs et je compare les éléments 2 à 2)
Code:

1 2 3 4 5 6 7 8 9 10 for(Pair<String, Pair<Set<Integer>, Instruction>> entry:varWrite ) System.out.print("|"+entry.hashCode()); System.out.println(); Pair<String, Pair<Set<Integer>, Instruction>> preventry=null; for(Pair<String, Pair<Set<Integer>, Instruction>> entry:varWrite ) { System.out.print("|"+entry.equals(preventry)); preventry=entry; } System.out.println();
Si j'ai bien compris mon Set utilise equals, ne contient pas de doublons et donc ici je devrais voir false partout, seulement voilà non seulement les hashs sont pour la plupart égaux mais aussi les .equals renvoient true.
Code:

1 2 |-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|-495702225|...495702225|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|1086338479|...|1086338479 |false|true|true|true|true|true|true|true|true|true|true|...|true|true
D'où ma question, pourquoi ai-je des doublons dans mon set ?

Cordialement

10/06/2015, 15h26
eulbobo

Donne nous le code de equals et de hashSet, et on te dira ce qui ne va pas

Régle à connaitre :
deux objets égaux ont le même hashset
deux objets qui ont le même hashset ne sont pas forcement égaux
deux objets différents peuvent avoir le même hashset

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
30
31
public class Pair<U, V> {
    private U first;
    private V second;
 
    public Pair(U u,V v){first=u;second=v;}
 
    public U getFirst(){return first;}
    public V getSecond(){return second;}
 
    public String toString()
    {
        return "("+first+","+second+")";
    }
 
    public boolean equals(Object p2)
    {
        if(p2 instanceof Pair<?,?>)
        {
            Pair<U,V> p=(Pair<U,V>)p2;
            return first.equals(p.first)&&second.equals(p.second);
        }
        return false;
    }
 
    public int hashCode() {
        int hashFirst = first != null ? first.hashCode() : 0;
        int hashSecond = second != null ? second.hashCode() : 0;
 
        return (hashFirst + hashSecond) * hashSecond + hashFirst;
    }
}

10/06/2015, 16h49
eulbobo
Pourquoi un truc aussi compliqué que ça ?

Code:

return (hashFirst + hashSecond) * hashSecond + hashFirst;

Ici, si first est null, ca équivaut à renvoyer hashSecond², et si second est null, ça renvoie hashFirst.
Si les deux sont null ça renvoie 0

Un retour comme celui-là devrait suffire :

Code:

return (hashFirst + hashSecond);

Par contre, ton equals et ton hashcode ne sont pas cohérents : dans le hashcode, first et second peuvent tous les deux être null, mais le equals impose qu'ils ne le soient jamais (sinon PAF)

De plus, tu n'es pas obligé de typer Pair :
Code:

1 2 3 4 5 if(p2 instanceof Pair) { Pair p=(Pair)p2; return first.equals(p.first)&&second.equals(p.second); }
Tu as le hashCode et equals de ta classe Instruction?

Citation:

Envoyé par eulbobo

Pourquoi un truc aussi compliqué que ça ?

Code:

return (hashFirst + hashSecond) * hashSecond + hashFirst;

Ici, si first est null, ca équivaut à renvoyer hashSecond², et si second est null, ça renvoie hashFirst.
Si les deux sont null ça renvoie 0

Un retour comme celui-là devrait suffire :

Code:

return (hashFirst + hashSecond);

Cela est pour ne pas avoir de colision de hash trop facilement. Si tes classes retourne leur ID entant que hash (ce qui est totalement possible).
Si hash1 = 2 et Hash2 =3 alors, le hash est égale à hash1=1 et hash2=4.
Même si cela n'est pas un problème en soit. Il est préférable d'ajouter de l'entropie dans le Hash.

Pour information, il y a pas mal de fonction de hash dans le code de l'API standard qui ont cette forme :
Code:

1 2 3 4 5 6 // Class TreeMap public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; }
Code:

1 2 3 4 5 6 7 8 9 10 // Class LocalDateTime /** * A hash code for this date-time. * * @return a suitable hash code */ @Override public int hashCode() { return date.hashCode() ^ time.hashCode(); }
Cordialement,
Patrick Kolodziejczyk.

10/06/2015, 20h09
eulbobo

Je ne pense pas qu'il en soit à un niveau qui requiert de l'optimisation de la répartition des clés de hachage.
10/06/2015, 20h20
adiGuba

Salut,

Citation:

Envoyé par eulbobo

Je ne pense pas qu'il en soit à un niveau qui requiert de l'optimisation de la répartition des clés de hachage.

+1

Je pense que le problème vient plutôt du fait que sa classe "Pair" n'est pas immuable, du coup son hashCode peut changer après l'ajout ce qui "casse" complètement le fonctionnement du HashSet (et du HashMap).

a++
10/06/2015, 22h29
tchize_

+1 une clé doit être immutable. Ca n'explique pas la boucle infinie (et où elle est d'ailleurs?) mais en tout cas ça rends Pair inutilisable comme clé d'un Set ou d'une Map
11/06/2015, 08h13
raphchar

Citation:

Envoyé par adiGuba

Salut,

+1

Je pense que le problème vient plutôt du fait que sa classe "Pair" n'est pas immuable, du coup son hashCode peut changer après l'ajout ce qui "casse" complètement le fonctionnement du HashSet (et du HashMap).

a++

Effectivement, je pense que le problème vient de là, merci
11/06/2015, 10h21
kolodz

Citation:

Envoyé par eulbobo

Je ne pense pas qu'il en soit à un niveau qui requiert de l'optimisation de la répartition des clés de hachage.

Non, mais tu donne des conseils sur les Hash qui ne sont pas bon. Cela mériterai d'être souligner.
11/06/2015, 10h53
eulbobo

Citation:

Envoyé par kolodz

Non, mais tu donne des conseils sur les Hash qui ne sont pas bon. Cela mériterai d'être souligner.

Ma solution pour son hash était UNE solution qui n'était PAS MEILLEURE que la sienne : juste plus simple/lisible/compréhensible.
Après, je le répète, il n'existe pas une seule solution pour calculer une clé de hachage et il y a des experts qui s'étripent pour savoir quelle est "la bonne".
Utiliser un opérateur XOR n'est pas nécessairement une "bonne" solution non plus.

La réponse est qu'il n'y a pas de bonne solution, parce que CA DEPEND de ce qu'on est en train de manipuler ET de comment on veut que ça se répartisse dans un Set. Accessoirement, son objet manipule des types génériques, donc impossible dans ce cas de déterminer une bonne formule étant donné que ça dépendra surtout des objets manipulés

La seule mauvaise façon de coder un hashcode, c'est celle qui fait en sorte que le contrat entre hashCode et equals ne soit plus respecté.