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.

[adiGuba]

Salut,

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

[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

[raphchar]

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

[kolodz]

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.

[eulbobo]

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