Discussion :

[Johann7751]

Bonjour,

Afin d'utiliser entre autre, les méthodes Distinct, Except, Intersect de LINQ to Object, j'ai besoin d'utiliser les Comparer.

J'ai besoin d'éclaircissement sur les comparer.
Avant, j'utilisais des comparer simples en utilisant la clé primaire d'un objet.
J'ai pas trop cherché à comprendre le fonctionnement.

Ma classe 'CriteriaComparerPK' , permettant de comparer des objets 'Criteria' avec leur clé primaire 'idCriteria'

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    public class CriteriaComparerPK : IEqualityComparer<Criteria>
    {
        bool IEqualityComparer<Criteria>.Equals(Criteria x, Criteria y)
        {
            if (x == null || y == null) return false;
            return (x.idCriteria == y.idCriteria);
        }
 
        int IEqualityComparer<Criteria>.GetHashCode(Criteria obj)
        {
 
            return obj.idCriteria.GetHashCode();
        }
    }

Exemple d'utilisation du Comparer : exemple d'Intersect :

Code :

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

	var listFinal = listCriteria1.Intersect(listCriteria2, new CriteriaComparerPK());

Jusqu'ici, en utilisant des comparer sur clé primaire, ça fonctionnait bien.
Mais récemment j'ai eu plus de difficultés à faire un comparer sur un objet n'ayant pas de PK (clé primaire).
Du coup j'aimerais bien comprendre un peu plus en détails le fonctionnement des comparers.

Mon objet à 3 propriétés.
pte1, pte2 et pte3.
Cet objet n'a pas de clé primaire dans mon scénario, donc je suis obligé de comparer les champs un à un pour différencier deux objets de ce type.
En sachant en plus que pte3 peut soit être renseignée, soit null.

Ex :
Un objet o1 { pte1 = "toto", pte2="tata", pte3=3 }
doit être différent d'un objet o2 { pte1 = "toto", pte2="tata", pte3=null }

Après plusieurs essais non concluants, j'ai fini par écrire mon comparer pour cet objet comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	    public class MyObjectComparerThreeProperties : IEqualityComparer<MyObject>
    {
        bool IEqualityComparer<MyObject>.Equals(MyObject x, MyObject y)
        {
            if (x == null || y == null) return false;
 
            return Equals(x.pte1, y.pte1) && Equals(x.pte2, y.pte2) && Equals(x.pte3, y.pte3);
        }
 
        int IEqualityComparer<MyObject>.GetHashCode(MyObject obj)
        {
            return obj.pte1.GetHashCode();
        }
    }

Mes questions sont les suivantes :

1)J'ai toujours pensé que le GetHashCode devait renvoyer un résultat différent pour des objets différents.
On m'a appris il y a pas lgtps que ce n'est pas vrai : 2 objets différents pourraient renvoyer le même résultat pour GetHashCode.
=> C'est ce point en particulier qui me posait problème car j'essayer de gérer la propriété nullable dans GetHashCode.
J'avais déjà rencontré des cas où, quand je mettais un GetHascode renvoyant un resultat identique pour des objet différents, mon comparer ne fonctionnait pas bien. J'en ai donc déduit que pour fonctionner correctement, la fonction GetHashCode d'un comparer devait renvoyer, une valeur différente pour des objets différents. Mais apparemment, cette supposition est fausse.
Est ce que c'est vrai ?

2) Est ce que mon Comparer vous semble correct ?
Est ce qu'il gère bien ma propriété3 qui peut être null ? Pas d'exception ?

[tomlev]

1)J'ai toujours pensé que le GetHashCode devait renvoyer un résultat différent pour des objets différents.
On m'a appris il y a pas lgtps que ce n'est pas vrai : 2 objets différents pourraient renvoyer le même résultat pour GetHashCode.
=> C'est ce point en particulier qui me posait problème car j'essayer de gérer la propriété nullable dans GetHashCode.
J'avais déjà rencontré des cas où, quand je mettais un GetHascode renvoyant un resultat identique pour des objet différents, mon comparer ne fonctionnait pas bien. J'en ai donc déduit que pour fonctionner correctement, la fonction GetHashCode d'un comparer devait renvoyer, une valeur différente pour des objets différents. Mais apparemment, cette supposition est fausse.
Est ce que c'est vrai ?

GetHashCode doit renvoyer la même valeur pour 2 objets considérés comme égaux, c'est la seule contrainte. Il peut tout à fait renvoyer la même valeur pour 2 objets différents... et heureusement d'ailleurs ! Vu que le hashcode est un Int32, il n'y a "que" 2^32 valeurs possibles, donc si chaque objet distinct devait avoir un hashcode différent, il ne serait pas possible d'avoir plus de 2^32 objets distincts, alors qu'il y en a potentiellement une infinité...

2) Est ce que mon Comparer vous semble correct ?
Est ce qu'il gère bien ma propriété3 qui peut être null ? Pas d'exception ?

Ton implémentation est correcte, dans le sens où elle donnera bien les résultats attendus, mais elle n'est pas optimale. Tous les objets qui ont la même valeur pour pte1 auront le même hashcode, donc la distribution des hashcodes n'est pas très bonne (i.e. les valeurs des hashcodes ne sont pas bien réparties). Cela peut causer des problèmes de performance dès que des dictionary ou hashtables sont impliqués, parce que tous les objets qui ont le même hashcode sont placés dans le même bucket ("case"), et il faut ensuite faire une recherche linéaire parmi ces objets pour trouver le bon.

(Pour info, la méthode Intersect utilise l'équivalent d'un HashSet<TKey> en interne, donc une mauvaise implémentation de GetHashcode impacte aussi les performances de cette méthode)

Normalement il faut prendre en compte dans GetHashcode tous les champs qui entrent en compte dans l'égalité, en les combinant avec des XOR et des nombres premiers. Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int GetHashcode(Criteria obj)
{
    unchecked
    {
        int hash = 983;
        if (obj.pte1 != null)
            hash = hash * 457 + obj.pte1.GetHashCode();
        if (obj.pte2 != null)
            hash = hash * 457 + obj.pte2.GetHashCode();
        if (obj.pte3 != null)
            hash = hash * 457 + obj.pte3.GetHashCode();
        return hash;
    }
}

Soit dit en passant, la lib Dvp.NET contient une méthode d'extension IntersectBy qui devrait faire ce que tu veux :

Code :

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

var listFinal = listCriteria1.IntersectBy(listCriteria2, c => new { c.pte1, c.pte2, c.pte3 });

(GetHashcode et Equals sont implémentés automatiquement pour les types anonymes, donc ça donne bien le résultat attendu)

[giova_fr]

Sujet tres interressant.

Concernant les nombres premiers, cette technique me fait un peu peur, comment bien les choisir? ne risquent t'ils pas de devenir inadaptés si on gonfle la classe concernée?

J'avais lu une autre méthode consistant à décaller des bits, qu'en pensez vous?

de mémoire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int hash =0;
if(obj.pte1 != null)
{
   hash+= obj.pte1.GetHashCode();
   hash = hash << 5 || hash >> 27;
}
if(obj.pte2 != null)
{
   hash += obj.pte2.GetHashCode();
   hash = hash << 5 || hash >> 27;
}
if(obj.pt3 != null)
   hash += obj.pte3.GetHashCode();
return hash;

EDIT : j'ai retrouvé l'article qui en parlait : http://jipe.developpez.com/articles/...age_1#LI-E-2-b

[tomlev]

A vrai dire je ne suis pas expert en génération de hashcode
Je n'ai pas inventé l'approche que j'ai postée là, c'est juste une façon de faire que j'ai souvent vue ailleurs. Je sais pas trop quel est le rôle exact des nombres premiers là-dedans, mais je crois que tu peux prendre à peu près n'importe lesquels du moment qu'ils sont premiers.

Après, d'autres approches, à base de décalages de bits ou autre, sont tout aussi valables ; l'important c'est que ça donne au final une bonne répartition des hashcodes

[GuruuMeditation]

On a remarqué qu'avec les nombres premiers, la distribution des hash etait plus équilibrée. Pourquoi exactement, je n'en sais rien, mais j'imagine que c'est du au fait que pas mal de hash sont divisibles par des nombres "simples" style 2,3,4,5 et donc si on prend un nombre premier suffisament grand, il ne sera pas un multiple de ces nombres ce qui fait que lors d'operations de modulo (par exemple) il y aura une meilleure distribution.

Si un mathématicien peu infirmer/confirmer ce serait sympa pour ma culture

[nah666]

Voila ce que j'ai pu trouver sur le net en ce qui concerne l'utilisation des nombres premiers pour les HashCode.

En gros les nombres premiers, de par leur unicité, multipliés a d'autres nombres rendent relativement uniques le résultat.

De ce fait la multiplication par des nombres premiers offre une meilleure répartition, voir tableau ici :

http://stackoverflow.com/questions/3...er-in-hashcode

L'exemple ici est sur un modulo mais la logique est la même.

Un post complet qui explique précisément le pourquoi du comment :
http://computinglife.wordpress.com/2...prime-numbers/

Enfin, il y a d'autres algorithmes pour générer des HashCode, mais il se trouve que l'utilisation des nombres premiers est un bon équilibre entre performance et taux de collission.