Ausführbare C#-Docs: HashSet

Q: Was ist ein HashSet in C#?

HashSet ist eine Collection eindeutiger Elemente ohne festgelegte Reihenfolge. Ein Element hinzuzufügen, das schon vorhanden ist, bewirkt nichts, und Contains antwortet in ungefähr konstanter Zeit, egal wie groß das Set ist, weil Elemente wie die Schlüssel eines Dictionary nach Hashcode gespeichert werden.

Q: Was gibt HashSet.Add zurück?

Add gibt true zurück, wenn das Element hinzugefügt wurde, und false, wenn es schon im Set war. Damit ist if (!seen.Add(x)) eine einzeilige Duplikatprüfung: Sie fügt neue Elemente hinzu und meldet wiederholte im selben Aufruf.

Q: Wie entferne ich in C# Duplikate aus einer List?

list.Distinct().ToList() gibt eine neue Liste ohne Duplikate zurück und behält das erste Vorkommen jedes Elements in seiner ursprünglichen Reihenfolge. new HashSet (list) entfernt ebenfalls Duplikate, aber ein Set hat keine garantierte Reihenfolge. Um an Ort und Stelle zu deduplizieren, nimm var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Wann sollte ich ein HashSet statt einer List verwenden?

Nimm ein HashSet , wenn du hauptsächlich fragst „ist dieses Element in der Collection?“ oder die Elemente eindeutig sein müssen. List .Contains durchsucht jedes Element und wird mit wachsender Liste langsamer, HashSet .Contains nicht. Nimm eine List , wenn Reihenfolge, Duplikate oder Indexzugriff zählen.

Q: Warum enthält mein HashSet doppelte Objekte?

Deine Klasse überschreibt Equals und GetHashCode nicht, also vergleicht das Set Referenzen, und zwei Objekte mit denselben Feldwerten gelten als verschieden. Überschreibe beide Methoden (immer zusammen) oder übergib dem Konstruktor des Sets einen IEqualityComparer .

Ein HashSet<T> ist eine Collection, in der jedes Element höchstens einmal vorkommt. Es hat keinen Index und keine garantierte Reihenfolge, und im Gegenzug prüft es die Zugehörigkeit in ungefähr konstanter Zeit: Ein Tag unter einer Million zu finden dauert etwa so lange wie unter zehn.

Elemente hinzufügen: Add gibt bool zurück

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

Ausgabe:

True
False
3
True
True
False
2

Ein Duplikat hinzuzufügen ist kein Fehler; Add gibt einfach false zurück, und das Set bleibt unverändert. Dieser Rückgabewert ist das Nützlichste an der Methode. Er verbindet „habe ich das schon gesehen?“ und „merk es dir“ in einem Aufruf:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

Ausgabe:

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Warum Contains schnell ist

List<T>.Contains vergleicht den Wert der Reihe nach mit jedem Element, die Kosten wachsen also mit der Liste. Ein HashSet<T> berechnet den Hashcode des Elements, springt zum Bucket für diesen Code und vergleicht nur die wenigen dort gespeicherten Elemente. Für einen Zugehörigkeitstest in einer Schleife wird so aus einem O(n)-Schritt ein O(1)-Schritt und aus einer verschachtelten Schleife über zwei Listen ein einziger Durchgang:

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

Das Set aufzubauen kostet einen Durchgang über die Liste, es lohnt sich also nur, wenn du mehr als eine Handvoll Mal nachschlägst.

Duplikate aus einer Liste entfernen

Es gibt drei übliche Wege, und sie unterscheiden sich darin, was mit der Reihenfolge passiert:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

Ausgabe:

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

Distinct ist der richtige Standard, wenn du eine Liste zurückbekommen willst. Die Version an Ort und Stelle funktioniert, weil RemoveAll das Prädikat der Reihe nach einmal pro Element aufruft: seen.Add gibt für die zweite und jede weitere Kopie false zurück, genau diese werden also entfernt.

Mengenoperationen: Vereinigung, Schnittmenge, Differenz

HashSet<T> hat die Operationen aus der Mengenlehre. Die Methoden auf ...With ändern das Set, auf dem sie aufgerufen werden, und geben nichts zurück.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

Ausgabe:

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

Das Argument kann jedes IEnumerable<T> sein: ein Array, eine Liste oder ein anderes Set. SetEquals ignoriert Reihenfolge und Duplikate im Argument. Die Hilfsmethode Show sortiert vor der Ausgabe, weil man sich auf die Reihenfolge beim Durchlaufen eines Sets nicht verlassen sollte.

LINQ hat passende Methoden, die eine neue Sequenz zurückgeben und die Eingaben unangetastet lassen: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Nimm diese, wenn du ein Set nicht verändern willst oder die Eingaben Listen sind.

Eigene Gleichheit für deine Klassen

Ein Set entscheidet mit GetHashCode und Equals, was „dasselbe Element“ ist. Bei einer Klasse, die sie nicht überschreibt, beruhen beide auf der Identität des Objekts, zwei Objekte mit gleichen Feldern sind also zwei verschiedene Elemente:

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

Ausgabe:

2
1
True

Die Regel: Objekte, die per Equals gleich sind, müssen denselben GetHashCode zurückgeben. Überschreibst du nur Equals, sucht das Set im falschen Bucket und meldet trotzdem Duplikate. Ab .NET Core 2.1 baut HashCode.Combine(X, Y) einen guten Hashcode ohne handgeschriebene Arithmetik.

Wenn du die Klasse nicht ändern kannst oder für ein Set einen anderen Begriff von „gleich“ brauchst, übergib dem Konstruktor einen IEqualityComparer<T>. Für Strings gibt es fertige Comparer:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

Ausgabe:

True
False
2

Ab C# 9 erzeugt ein record wertbasierte Equals und GetHashCode für dich, record Point(int X, int Y); funktioniert in einem Set also ohne zusätzlichen Code.

Ändere nie ein Feld, das in GetHashCode einfließt, solange das Objekt in einem Set ist. Das Objekt bleibt im Bucket seines alten Hashs, und Contains und Remove finden es nicht mehr.

Reihenfolge und SortedSet

Ein HashSet<T> durchläuft in einer Reihenfolge, die du als beliebig behandeln solltest. Wenn du die Elemente sortiert brauchst, sortiere bei der Ausgabe (set.OrderBy(x => x)) oder nimm SortedSet<T>, das die Elemente jederzeit geordnet hält und Min, Max und Bereichsabfragen mit O(log n) pro Operation bietet:

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet gegenüber List gegenüber Dictionary

Bedarf	Verwende
Eindeutige Elemente, schnelles „ist es da?“	`HashSet<T>`
Eindeutige Elemente, immer sortiert	`SortedSet<T>`
Reihenfolge, Duplikate, Indexzugriff	`List<T>`
Ein Wert unter jedem Schlüssel	`Dictionary<TKey, TValue>`

Ein Set ist ein Dictionary mit Schlüsseln und ohne Werte. Wenn du Dictionary<string, bool> schreibst, nur um die Zugehörigkeit festzuhalten, sagt ein HashSet<string> dasselbe klarer.

Häufige Fehler

Eine Reihenfolge erwarten. Ein Set hat keine, auf die du dich verlassen kannst; sortiere oder nimm SortedSet<T>.
Eigene Klassen ohne Equals und GetHashCode. Gleich aussehende Objekte werden zu separaten Elementen.
Nur Equals überschreiben. Überschreibe immer GetHashCode mit.
Ein Element nach dem Hinzufügen verändern. Das Set findet es nicht mehr.
Ein Set indizieren. set[0] kompiliert nicht; es gibt keinen Index. Wandle mit ToList() um, wenn du Positionen brauchst.

Häufig gestellte Fragen

Was ist ein HashSet in C#?

HashSet<T> ist eine Collection eindeutiger Elemente ohne festgelegte Reihenfolge. Ein Element hinzuzufügen, das schon vorhanden ist, bewirkt nichts, und Contains antwortet in ungefähr konstanter Zeit, egal wie groß das Set ist, weil Elemente wie die Schlüssel eines Dictionary nach Hashcode gespeichert werden.

Was gibt HashSet.Add zurück?

Add gibt true zurück, wenn das Element hinzugefügt wurde, und false, wenn es schon im Set war. Damit ist if (!seen.Add(x)) eine einzeilige Duplikatprüfung: Sie fügt neue Elemente hinzu und meldet wiederholte im selben Aufruf.

Wie entferne ich in C# Duplikate aus einer List?

list.Distinct().ToList() gibt eine neue Liste ohne Duplikate zurück und behält das erste Vorkommen jedes Elements in seiner ursprünglichen Reihenfolge. new HashSet<T>(list) entfernt ebenfalls Duplikate, aber ein Set hat keine garantierte Reihenfolge. Um an Ort und Stelle zu deduplizieren, nimm var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Wann sollte ich ein HashSet statt einer List verwenden?

Nimm ein HashSet<T>, wenn du hauptsächlich fragst „ist dieses Element in der Collection?“ oder die Elemente eindeutig sein müssen. List<T>.Contains durchsucht jedes Element und wird mit wachsender Liste langsamer, HashSet<T>.Contains nicht. Nimm eine List<T>, wenn Reihenfolge, Duplikate oder Indexzugriff zählen.

Warum enthält mein HashSet doppelte Objekte?

Deine Klasse überschreibt Equals und GetHashCode nicht, also vergleicht das Set Referenzen, und zwei Objekte mit denselben Feldwerten gelten als verschieden. Überschreibe beide Methoden (immer zusammen) oder übergib dem Konstruktor des Sets einen IEqualityComparer<T>.

Verwandte Konzepte