Discussion :

[raphchar]

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

Code :

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

Pair<U,V>

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

Code :

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

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 :

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

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 :

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

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

[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

[raphchar]

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
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;
    }
}

[eulbobo]

Pourquoi un truc aussi compliqué que ça ?

Code :

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

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 :

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

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 :

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

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?

[kolodz]

Pourquoi un truc aussi compliqué que ça ?

Code :

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

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 :

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

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 :

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

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 :

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

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.

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