Comment HashSet compare-t-il les éléments pour l'égalité?

127

J'ai une classe qui est IComparable:

public class a : IComparable
{
    public int Id { get; set; }
    public string Name { get; set; }

    public a(int id)
    {
        this.Id = id;
    }

    public int CompareTo(object obj)
    {
        return this.Id.CompareTo(((a)obj).Id);
    }
}

Lorsque j'ajoute une liste d'objets de cette classe à un ensemble de hachage:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(a1);

Tout va bien et l' ha.countest 2, mais:

a a1 = new a(1);
a a2 = new a(2);
HashSet<a> ha = new HashSet<a>();
ha.add(a1);
ha.add(a2);
ha.add(new a(1));

Maintenant ha.countest 3.

  1. Pourquoi ne HashSetrespecte pas ala CompareTométhode de.
  2. Est-ce HashSetla meilleure façon d'avoir une liste d'objets uniques?
nima
la source
Ajoutez une implémentation de IEqualityComparer<T>dans le constructeur ou implémentez-la dans la classe a. msdn.microsoft.com/en-us/library/bb301504(v=vs.110).aspx
Jaider

Réponses:

137

Il utilise un IEqualityComparer<T>( EqualityComparer<T>.Defaultsauf si vous en spécifiez un différent lors de la construction).

Lorsque vous ajoutez un élément à l'ensemble, il trouvera le code de hachage à l'aide de IEqualityComparer<T>.GetHashCode, et stockera à la fois le code de hachage et l'élément (après avoir vérifié si l'élément est déjà dans l'ensemble, bien sûr).

Pour rechercher un élément, il utilisera d'abord le IEqualityComparer<T>.GetHashCodepour trouver le code de hachage, puis pour tous les éléments avec le même code de hachage, il utilisera IEqualityComparer<T>.Equalspour comparer l'égalité réelle.

Cela signifie que vous avez deux options:

  • Passez une personnalisation IEqualityComparer<T>dans le constructeur. C'est la meilleure option si vous ne pouvez pas modifier le Tlui - même, ou si vous voulez une relation d'égalité autre que celle par défaut (par exemple, "tous les utilisateurs avec un ID utilisateur négatif sont considérés comme égaux"). Ceci n'est presque jamais implémenté sur le type lui-même (c'est-à Foo- dire ne l'implémente pas IEqualityComparer<Foo>) mais dans un type séparé qui n'est utilisé que pour les comparaisons.
  • Implémentez l'égalité dans le type lui-même, en remplaçant GetHashCodeet Equals(object). Idéalement, implémentez également IEquatable<T>le type, en particulier s'il s'agit d'un type valeur. Ces méthodes seront appelées par le comparateur d'égalité par défaut.

Notez que rien de tout cela n'est en termes de comparaison ordonnée - ce qui a du sens, car il y a certainement des situations où vous pouvez facilement spécifier l'égalité mais pas un ordre total. C'est tout de même Dictionary<TKey, TValue>fondamentalement.

Si vous voulez un ensemble qui utilise l' ordre au lieu de simples comparaisons d'égalité, vous devez utiliser à SortedSet<T>partir de .NET 4 - qui vous permet de spécifier un IComparer<T>au lieu d'un IEqualityComparer<T>. Cela utilisera IComparer<T>.Compare- qui déléguera à IComparable<T>.CompareToou IComparable.CompareTosi vous utilisez Comparer<T>.Default.

Jon Skeet
la source
7
+1 Notez également la réponse de @ tyriker (que l'OMI devrait être un commentaire ici) qui souligne que le moyen le plus simple de tirer parti de celui-ci IEqualityComparer<T>.GetHashCode/Equals()est de mettre en œuvre Equalset GetHashCodesur Tlui-même (et pendant que vous le faites, vous implémenteriez également la contrepartie fortement typée : - bool IEquatable<T>.Equals(T other))
Ruben Bartelink
5
Bien que très précise, cette réponse peut être quelque peu déroutante, en particulier pour les nouveaux utilisateurs car elle n'indique pas clairement cela pour le cas le plus simple Equalset GetHashCodesuffit - comme mentionné dans la réponse de @ tyriker.
BartoszKP
Imo une fois que vous implémentez IComparable(ou IComparerd'ailleurs), vous ne devriez pas être invité à implémenter l'égalité séparément (mais juste GetHashCode). En un sens, les interfaces de comparabilité devraient hériter des interfaces d'égalité. Je comprends les avantages en termes de performances d'avoir deux fonctions distinctes (où vous pouvez optimiser l'égalité séparément simplement en disant si quelque chose est égal ou non) mais quand même .. Très déroutant sinon lorsque vous avez spécifié quand les instances sont égales en CompareTofonction et le cadre ne considérera pas cette.
nawfal le
@nawfal tout n'a pas un ordre logique. si vous comparez deux choses qui contiennent une propriété booléenne, il est tout simplement horrible d'avoir à écrire quelque chose comme a.boolProp == b.boolProp ? 1 : 0ou devrait-il être a.boolProp == b.boolProp ? 0 : -1ou a.boolProp == b.boolProp ? 1 : -1. Yuk!
Simon_Weaver
1
@Simon_Weaver ça l'est. Je veux en quelque sorte l'éviter dans ma fonction hypothétique que je proposais.
nawfal
77

Voici une clarification sur une partie de la réponse qui n'a pas été dite: le type d'objet de votre HashSet<T>n'a pas à être implémenté IEqualityComparer<T>mais doit simplement remplacer Object.GetHashCode()et Object.Equals(Object obj).

Au lieu de cela:

public class a : IEqualityComparer<a>
{
  public int GetHashCode(a obj) { /* Implementation */ }
  public bool Equals(a obj1, a obj2) { /* Implementation */ }
}

Tu fais cela:

public class a
{
  public override int GetHashCode() { /* Implementation */ }
  public override bool Equals(object obj) { /* Implementation */ }
}

C'est subtil, mais cela m'a fait trébucher pendant la majeure partie de la journée en essayant de faire fonctionner HashSet comme prévu. Et comme d'autres l'ont dit, HashSet<a>finira par appeler a.GetHashCode()et a.Equals(obj)si nécessaire lorsque vous travaillez avec l'ensemble.

Tyriker
la source
2
Bon point. BTW, comme mentionné dans mon commentaire sur la réponse de @ JonSkeet, vous devez également implémenter bool IEquatable<T>.Equals(T other)pour un léger gain d'efficacité mais plus important encore, l'avantage de la clarté. Pour des raisons évidentes, en plus de la nécessité d'implémenter GetHashCodeparallèlement IEquatable<T>, le document pour IEquatable <T> mentionne que pour des raisons de cohérence, vous devez également remplacer le object.Equalspour la cohérence
Ruben Bartelink
J'ai essayé de mettre en œuvre cela. Le ovveride getHashcodefonctionne, mais override bool equalsobtient l'erreur: aucune méthode trouvée pour remplacer. une idée?
Stefanvds
Enfin les informations que je recherchais. Je vous remercie.
Mauro Sampietro
D'après mes commentaires sur la réponse ci-dessus - Dans votre cas "Au lieu de", vous auriez pu public class a : IEqualityComparer<a> {, et ensuite new HashSet<a>(a).
HankCa
Mais voir les commentaires de Jon Skeets ci-dessus.
HankCa
9

HashSetutilise Equalset GetHashCode().

CompareTo est pour les ensembles commandés.

Si vous voulez des objets uniques, mais que vous ne vous souciez pas de leur ordre d'itération, HashSet<T>c'est généralement le meilleur choix.

CodesInChaos
la source
5

Le constructeur HashSet reçoit un objet qui implémente IEqualityComparer pour l'ajout d'un nouvel objet. si vous voulez utiliser la méthode dans HashSet, vous ne remplacez pas Equals, GetHashCode

namespace HashSet
{
    public class Employe
    {
        public Employe() {
        }

        public string Name { get; set; }

        public override string ToString()  {
            return Name;
        }

        public override bool Equals(object obj) {
            return this.Name.Equals(((Employe)obj).Name);
        }

        public override int GetHashCode() {
            return this.Name.GetHashCode();
        }
    }

    class EmployeComparer : IEqualityComparer<Employe>
    {
        public bool Equals(Employe x, Employe y)
        {
            return x.Name.Trim().ToLower().Equals(y.Name.Trim().ToLower());
        }

        public int GetHashCode(Employe obj)
        {
            return obj.Name.GetHashCode();
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<Employe> hashSet = new HashSet<Employe>(new EmployeComparer());
            hashSet.Add(new Employe() { Name = "Nik" });
            hashSet.Add(new Employe() { Name = "Rob" });
            hashSet.Add(new Employe() { Name = "Joe" });
            Display(hashSet);
            hashSet.Add(new Employe() { Name = "Rob" });
            Display(hashSet);

            HashSet<Employe> hashSetB = new HashSet<Employe>(new EmployeComparer());
            hashSetB.Add(new Employe() { Name = "Max" });
            hashSetB.Add(new Employe() { Name = "Solomon" });
            hashSetB.Add(new Employe() { Name = "Werter" });
            hashSetB.Add(new Employe() { Name = "Rob" });
            Display(hashSetB);

            var union = hashSet.Union<Employe>(hashSetB).ToList();
            Display(union);
            var inter = hashSet.Intersect<Employe>(hashSetB).ToList();
            Display(inter);
            var except = hashSet.Except<Employe>(hashSetB).ToList();
            Display(except);

            Console.ReadKey();
        }

        static void Display(HashSet<Employe> hashSet)
        {
            if (hashSet.Count == 0)
            {
                Console.Write("Collection is Empty");
                return;
            }
            foreach (var item in hashSet)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }

        static void Display(List<Employe> list)
        {
            if (list.Count == 0)
            {
                Console.WriteLine("Collection is Empty");
                return;
            }
            foreach (var item in list)
            {
                Console.Write("{0}, ", item);
            }
            Console.Write("\n");
        }
    }
}
Nikolai Nechai
la source
Que faire si le nom est nul? quelle est la valeur de hachage de null?
joe