Wann sollte ich den HashSet <T> -Typ verwenden?

Ich erkunde das HashSet<T> Typ, verstehe aber nicht, wo er in Sammlungen steht.

Kann man damit ein ersetzen List<T>? Ich stelle mir die Leistung eines HashSet<T>besser vor, aber ich konnte keinen individuellen Zugang zu seinen Elementen sehen.

Ist es nur zur Aufzählung?

Das Wichtigste HashSet<T>ist genau dort im Namen: Es ist ein Set . Das einzige, was Sie mit einem einzelnen Satz tun können, ist festzustellen, was seine Mitglieder sind, und zu überprüfen, ob ein Element Mitglied ist.

Die Frage, ob Sie ein einzelnes Element (z. B. set[45]) abrufen können, ist ein Missverständnis des Konzepts der Menge. Es gibt kein 45. Element eines Sets. Artikel in einem Set haben keine Bestellung. Die Mengen {1, 2, 3} und {2, 3, 1} sind in jeder Hinsicht identisch, da sie dieselbe Mitgliedschaft haben und die Mitgliedschaft alles ist, was zählt.

Es ist etwas gefährlich, über a zu iterieren HashSet<T> da dies den Artikeln im Set eine Reihenfolge auferlegt. Diese Reihenfolge ist nicht wirklich eine Eigenschaft des Sets. Sie sollten sich nicht darauf verlassen. Wenn Ihnen die Bestellung der Artikel in einer Sammlung wichtig ist, ist diese Sammlung kein Satz.

Sets sind wirklich begrenzt und mit einzigartigen Mitgliedern. Andererseits sind sie sehr schnell.

Hier ist ein echtes Beispiel dafür, wo ich Folgendes verwende HashSet<string>:

Ein Teil meines Syntax-Textmarkers für UnrealScript-Dateien ist eine neue Funktion, die Kommentare im Doxygen-Stil hervorhebt . Ich muss feststellen können, ob ein Befehl @oder \gültig ist, um festzustellen, ob er grau (gültig) oder rot (ungültig) angezeigt werden soll. Ich habe einen HashSet<string>der gültigen Befehle. Wenn ich also ein @xxxToken im Lexer drücke, verwende ich es validCommands.Contains(tokenText)als meine O (1) -Gültigkeitsprüfung. Mir ist wirklich nichts anderes wichtig als das Vorhandensein des Befehls in der Menge der gültigen Befehle. Schauen wir uns die Alternativen an, mit denen ich konfrontiert war:

• Dictionary<string, ?>: Welchen Typ verwende ich für den Wert? Der Wert ist bedeutungslos, da ich ihn nur verwenden werde ContainsKey. Hinweis: Vor .NET 3.0 war dies die einzige Option für O (1) -Suchen - HashSet<T>wurde für 3.0 hinzugefügt und für die Implementierung ISet<T>für 4.0 erweitert.
• List<string>: Wenn ich die Liste sortiert halte, kann ich BinarySearchO (log n) verwenden (habe diese oben erwähnte Tatsache nicht gesehen). Da meine Liste der gültigen Befehle jedoch eine feste Liste ist, die sich nie ändert, ist dies niemals angemessener als einfach ...
• string[]: Gibt wieder Array.BinarySearchO (log n) Leistung. Wenn die Liste kurz ist, ist dies möglicherweise die Option mit der besten Leistung. Es hat immer weniger Platz Overhead als HashSet, Dictionaryoder List. Trotzdem BinarySearchist es für große Sets nicht schneller, aber für kleine Sets lohnt es sich zu experimentieren. Meins hat allerdings mehrere hundert Gegenstände, also habe ich das weitergegeben.

A HashSet<T>implementiert die ICollection<T>Schnittstelle:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

Ein List<T>Gerät IList<T>, das das erweitertICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

Ein HashSet hat eine Semantik festgelegt, die intern über eine Hashtabelle implementiert wird:

Ein Satz ist eine Sammlung, die keine doppelten Elemente enthält und deren Elemente in keiner bestimmten Reihenfolge vorliegen.

Was gewinnt das HashSet, wenn es das Verhalten von Index / Position / Liste verliert?

Das Hinzufügen und Abrufen von Elementen aus dem HashSet erfolgt immer durch das Objekt selbst, nicht über einen Indexer, und in der Nähe einer O (1) -Operation (Liste ist O (1) hinzufügen, O (1) durch Index abrufen, O (n) finden /entfernen).

Das Verhalten eines HashSets kann mit der Verwendung von a verglichen werden, Dictionary<TKey,TValue>indem nur Schlüssel als Werte hinzugefügt / entfernt werden und Wörterbuchwerte selbst ignoriert werden. Sie würden erwarten, dass Schlüssel in einem Wörterbuch keine doppelten Werte haben, und das ist der Punkt des Teils "Set".

Leistung wäre ein schlechter Grund, HashSet anstelle von List zu wählen. Was fängt Ihre Absicht besser ein? Wenn die Reihenfolge wichtig ist, ist Set (oder HashSet) nicht verfügbar. Wenn Duplikate ebenfalls erlaubt sind. Aber es gibt viele Umstände, unter denen uns die Bestellung egal ist und wir lieber keine Duplikate haben möchten - und dann möchten Sie ein Set.

HashSet ist eine Menge, die durch Hashing implementiert wird. Eine Menge ist eine Sammlung von Werten, die keine doppelten Elemente enthalten. Die Werte in einem Satz sind normalerweise auch ungeordnet. Nein, ein Satz kann nicht zum Ersetzen einer Liste verwendet werden (es sei denn, Sie hätten zuerst einen Satz verwenden sollen).

Wenn Sie sich fragen, wozu ein Set gut sein könnte: Natürlich überall dort, wo Sie Duplikate entfernen möchten. Angenommen, Sie haben eine Liste mit 10.000 Revisionen eines Softwareprojekts und möchten herausfinden, wie viele Personen zu diesem Projekt beigetragen haben. Sie können a verwenden Set<string>und die Liste der Revisionen durchlaufen und den Autor jeder Revision zum Satz hinzufügen. Sobald Sie mit dem Iterieren fertig sind, ist die Größe des Sets die Antwort, nach der Sie gesucht haben.

HashSet wird verwendet, um doppelte Elemente in einer IEnumerable-Sammlung zu entfernen. Beispielsweise,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

Nachdem diese Codes ausgeführt wurden, enthält uniqueStrings {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

Wahrscheinlich wird Hashsets am häufigsten verwendet, um festzustellen, ob sie ein bestimmtes Element enthalten, das für sie nahe an einer O (1) -Operation liegt (unter der Annahme einer ausreichend starken Hashing-Funktion), im Gegensatz zu Listen, für die die Prüfung auf Aufnahme O ( n) (und sortierte Mengen, für die es O ist (log n)). Wenn Sie also viele Überprüfungen durchführen, ob ein Element in einer Liste enthalten ist, können Hahssets eine Leistungsverbesserung darstellen. Wenn Sie immer nur über sie iterieren, gibt es keinen großen Unterschied (das Iterieren über die gesamte Menge ist O (n), genau wie bei Listen und Hashsets, die beim Hinzufügen von Elementen etwas mehr Overhead haben).

Und nein, Sie können einen Satz nicht indizieren, was ohnehin keinen Sinn ergibt, da Sätze nicht geordnet sind. Wenn Sie einige Elemente hinzufügen, merkt sich das Set nicht, welches zuerst und welches zweite usw. war.

HashSet<T>ist eine Datenstruktur im .NET Framework, die eine mathematische Menge als Objekt darstellen kann. In diesem Fall werden Hash-Codes (das GetHashCodeErgebnis jedes Elements) verwendet, um die Gleichheit der festgelegten Elemente zu vergleichen.

Eine Menge unterscheidet sich von einer Liste dadurch, dass nur ein Vorkommen desselben Elements zulässig ist. HashSet<T>wird nur zurückgegeben, falsewenn Sie versuchen, ein zweites identisches Element hinzuzufügen. In der Tat ist die Suche nach Elementen sehr schnell (O(1) Zeit), da die interne Datenstruktur einfach eine Hashtabelle ist.

Wenn Sie sich fragen , welche Note zu verwenden, das eine mit List<T>dem HashSet<T>sachgemäßer ist , ist nicht der größte Fehler, obwohl es möglicherweise Probleme erlauben kann , wenn Sie unerwünschte doppelte Elemente in Ihrer Sammlung haben. Darüber hinaus ist die Suche (Item Retrieval) wesentlich effizienter - idealerweise O(1)(für perfektes Bucketing) anstelle von O(n)Zeit - was in vielen Szenarien sehr wichtig ist.

List<T>wird zum Speichern geordneter Informationssätze verwendet. Wenn Sie die relative Reihenfolge der Elemente der Liste kennen, können Sie in konstanter Zeit darauf zugreifen. Um jedoch festzustellen, wo sich ein Element in der Liste befindet, oder um zu überprüfen, ob es in der Liste vorhanden ist, ist die Suchzeit linear. Andererseits HashedSet<T>übernimmt keine Garantie für die Reihenfolge der gespeicherten Daten und bietet folglich eine konstante Zugriffszeit für ihre Elemente.

Wie der Name schon sagt, HashedSet<T>handelt es sich um eine Datenstruktur, die eine festgelegte Semantik implementiert . Die Datenstruktur ist für die Implementierung von Set-Operationen (dh Union, Difference, Intersect) optimiert, die mit der herkömmlichen List-Implementierung nicht so effizient ausgeführt werden können.

Die Auswahl des zu verwendenden Datentyps hängt also davon ab, was Sie mit Ihrer Anwendung versuchen. Wenn Sie sich nicht darum kümmern, wie Ihre Elemente in einer Sammlung angeordnet sind, und nur die Existenz aufzählen oder überprüfen möchten, verwenden Sie HashSet<T>. Andernfalls sollten Sie eine List<T>andere geeignete Datenstruktur verwenden.

Kurz gesagt: Immer wenn Sie versucht sind, ein Wörterbuch (oder ein Wörterbuch, in dem S eine Eigenschaft von T ist) zu verwenden, sollten Sie ein HashSet in Betracht ziehen (oder HashSet +, das IEquatable auf T implementiert, was S entspricht).

Im grundlegenden beabsichtigten Szenario HashSet<T>sollte verwendet werden, wenn Sie spezifischere Set-Operationen für zwei Sammlungen wünschen, als LINQ bereitstellt. LINQ Methoden wie Distinct, Union, Intersectund Exceptsind genug , um in den meisten Situationen, aber manchmal kann man mehr feinkörnige Operation benötigen, und HashSet<T>bieten:

• UnionWith
• IntersectWith
• ExceptWith
• SymmetricExceptWith
• Overlaps
• IsSubsetOf
• IsProperSubsetOf
• IsSupersetOf
• IsProperSubsetOf
• SetEquals

Ein weiterer Unterschied zwischen LINQ- und HashSet<T>"überlappenden" Methoden besteht darin, dass LINQ immer eine neue zurückgibt IEnumerable<T>und HashSet<T>Methoden die Quellensammlung ändern.