Wie vergleicht HashSet Elemente auf Gleichheit?

127

Ich habe eine Klasse, die ist 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);
    }
}

Wenn ich eine Liste von Objekten dieser Klasse zu einem Hash-Set hinzufüge:

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

Alles ist gut und ha.countist 2, aber:

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

Jetzt ha.countist 3.

  1. Warum HashSetrespektiert man nicht adie CompareToMethode?
  2. Ist HashSetder beste Weg, um eine Liste einzigartiger Objekte zu haben?
Nima
quelle
Fügen Sie eine Implementierung von IEqualityComparer<T>im Konstruktor hinzu oder implementieren Sie sie in der Klasse a. msdn.microsoft.com/en-us/library/bb301504(v=vs.110).aspx
Jaider

Antworten:

137

Es wird ein verwendet IEqualityComparer<T>(es EqualityComparer<T>.Defaultsei denn, Sie geben bei der Konstruktion ein anderes an).

Wenn Sie der Menge ein Element hinzufügen, findet es den Hash-Code mithilfe von IEqualityComparer<T>.GetHashCodeund speichert sowohl den Hash-Code als auch das Element (nachdem Sie natürlich überprüft haben, ob sich das Element bereits in der Menge befindet).

Um ein Element nachzuschlagen, wird zuerst der verwendet IEqualityComparer<T>.GetHashCode, um den Hash-Code zu finden, und dann wird für alle Elemente mit demselben Hash-Code IEqualityComparer<T>.Equalsder Vergleich für die tatsächliche Gleichheit verwendet.

Das heißt, Sie haben zwei Möglichkeiten:

  • Übergeben Sie einen Custom IEqualityComparer<T>an den Konstruktor. Dies ist die beste Option, wenn Sie das Tselbst nicht ändern können oder wenn Sie eine nicht standardmäßige Gleichheitsrelation wünschen (z. B. "Alle Benutzer mit einer negativen Benutzer-ID werden als gleich angesehen"). Dies wird fast nie auf dem Typ selbst implementiert (dh Foonicht implementiert IEqualityComparer<Foo>), sondern in einem separaten Typ, der nur für Vergleiche verwendet wird.
  • Implementieren Sie die Gleichheit im Typ selbst, indem Sie GetHashCodeund überschreiben Equals(object). Im Idealfall auch IEquatable<T>im Typ implementieren , insbesondere wenn es sich um einen Werttyp handelt. Diese Methoden werden vom Standardgleichheitsvergleich aufgerufen.

Beachten Sie, dass dies im Hinblick auf einen geordneten Vergleich nichts ist - was sinnvoll ist, da es sicherlich Situationen gibt, in denen Sie leicht die Gleichheit angeben können, aber keine Gesamtreihenfolge. Dies ist im Dictionary<TKey, TValue>Grunde alles das Gleiche wie .

Wenn Sie eine Menge möchten, die die Reihenfolge anstelle von Gleichheitsvergleichen verwendet, sollten Sie sie SortedSet<T>aus .NET 4 verwenden, mit der Sie eine IComparer<T>anstelle einer angeben können IEqualityComparer<T>. Dies wird verwendet IComparer<T>.Compare- was an IComparable<T>.CompareTooder IComparable.CompareTowenn Sie verwenden delegieren Comparer<T>.Default.

Jon Skeet
quelle
7
+1 außerdem Kenntnis @ tyriker Antwort (das IMO sollte einen Kommentar hier sein) , die darauf hinweist, dass der einfachste Weg , sagte Hebel IEqualityComparer<T>.GetHashCode/Equals()zu implementieren Equalsund GetHashCodeauf Tsich selbst (und während Sie das tun, dann würden Sie auch die stark typisierte Gegenstück implementieren : - bool IEquatable<T>.Equals(T other))
Ruben Bartelink
5
Obwohl diese Antwort sehr genau ist, kann sie etwas verwirrend sein, insbesondere für neue Benutzer, da sie nicht eindeutig angibt, dass sie im einfachsten Fall überschrieben wird Equalsund GetHashCodeausreicht - wie in der Antwort von @ tyriker erwähnt.
BartoszKP
Imo sollten Sie nach der Implementierung IComparable(oder im IComparerÜbrigen) nicht aufgefordert werden, die Gleichstellung separat (sondern nur GetHashCode) zu implementieren . In gewissem Sinne sollten die Vergleichbarkeitsschnittstellen von Gleichheitsschnittstellen erben. Ich verstehe die Leistungsvorteile, wenn zwei separate Funktionen vorhanden sind (bei denen Sie die Gleichheit separat optimieren können, indem Sie einfach sagen, ob etwas gleich ist oder nicht), aber dennoch. Ansonsten sehr verwirrend, wenn Sie angegeben haben, wann die Instanzen in CompareToFunktion und Framework gleich sind, werden dies nicht berücksichtigt Das.
Nawfal
@nawfal nicht alles hat eine logische Reihenfolge. Wenn Sie zwei Dinge vergleichen, die eine bool-Eigenschaft enthalten, ist es einfach schrecklich, so etwas schreiben zu müssen a.boolProp == b.boolProp ? 1 : 0oder sollte es sein a.boolProp == b.boolProp ? 0 : -1oder a.boolProp == b.boolProp ? 1 : -1. Yuk!
Simon_Weaver
1
@ Simon_Weaver ist es. Ich möchte es in meinem hypothetischen Merkmal, das ich vorgeschlagen habe, irgendwie vermeiden.
Nawfal
77

Hier ist eine Klarstellung zu einem Teil der Antwort, der nicht gesagt wurde: Der Objekttyp von Ihnen HashSet<T>muss nicht implementiert werden, IEqualityComparer<T>sondern muss nur überschreiben Object.GetHashCode()und Object.Equals(Object obj).

An Stelle von:

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

Du machst das:

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

Es ist subtil, aber das hat mich fast einen ganzen Tag lang gestolpert, als ich versucht habe, HashSet so zu machen, wie es beabsichtigt ist. Und wie andere gesagt haben, HashSet<a>wird am Ende anrufen a.GetHashCode()und a.Equals(obj)nach Bedarf bei der Arbeit mit dem Set.

Tyriker
quelle
2
Guter Punkt. Übrigens, wie in meinem Kommentar zur Antwort von @ JonSkeet erwähnt, sollten Sie auch bool IEquatable<T>.Equals(T other)einen leichten Effizienzgewinn, aber vor allem den Vorteil der Klarheit implementieren . Für Vs. Gründen neben der Notwendigkeit zur Umsetzung GetHashCodeneben IEquatable<T>der doc für IEquatable <T> erwähnt , dass für Konsistenz Zwecke sollten Sie auch die außer Kraft setzen object.Equalsauf Konsistenz
Ruben Bartelink
Ich habe versucht, dies umzusetzen. Das ovveride getHashcodefunktioniert, override bool equalsbekommt aber den Fehler: Es wurde keine Methode zum Überschreiben gefunden. irgendeine Idee?
Stefanvds
Endlich die Infos, nach denen ich gesucht habe. Danke dir.
Mauro Sampietro
Aus meinen Kommentaren zur obigen Antwort - In Ihrem "Statt" -Fall könnten Sie public class a : IEqualityComparer<a> {und dann haben new HashSet<a>(a).
HankCa
Aber siehe Jon Skeets Kommentare oben.
HankCa
9

HashSetverwendet Equalsund GetHashCode().

CompareTo ist für bestellte Sets.

Wenn Sie eindeutige Objekte möchten, deren Iterationsreihenfolge jedoch nicht wichtig ist, HashSet<T>ist dies normalerweise die beste Wahl.

CodesInChaos
quelle
5

Konstruktor HashSet Empfangsobjekt, das IEqualityComparer zum Hinzufügen eines neuen Objekts implementiert. Wenn Sie die Methode in HashSet verwenden möchten, überschreiben Sie 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
quelle
Was ist, wenn der Name null ist? Was ist der Hashwert von null?
Joe