Definieren: Was ist ein HashSet?

420

HashSet Die C # HashSet-Datenstruktur wurde in .NET Framework 3.5 eingeführt. Eine vollständige Liste der implementierten Mitglieder finden Sie auf der HashSet MSDN- Seite.

  1. Wo wird es verwendet?
  2. Warum sollten Sie es verwenden wollen?
c# hashset 001
quelle
4
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
Mögliches Duplikat von Wann soll ich den HashSet <T> -Typ verwenden?
Nawfal
Es wird intern eine Hashtabelle verwendet. Wenn Sie eine gute Hashtable-Implementierung haben (zum Beispiel Dictionary <T>), können Sie HashSet einfach selbst implementieren.
Raz Megrelidze

Antworten:

614

    1. A HashSetenthält eine Reihe von Objekten, aber auf eine Weise, mit der Sie einfach und schnell feststellen können, ob sich ein Objekt bereits in der Menge befindet oder nicht. Dazu wird ein Array intern verwaltet und das Objekt mithilfe eines Index gespeichert, der aus dem Hashcode des Objekts berechnet wird. Schauen Sie hier

    2. HashSetist eine ungeordnete Sammlung mit einzigartigen Elementen. Es verfügt über die Standard-Erfassungsoperationen Hinzufügen, Entfernen, Enthält. Da jedoch eine Hash-basierte Implementierung verwendet wird, sind diese Operationen O (1). (Im Gegensatz zu List zum Beispiel O (n) für Enthält und Entfernen.) HashSetBietet auch Standardsatzoperationen wie Vereinigung , Schnittpunkt und symmetrische Differenz . Schauen Sie hier

  2. Es gibt verschiedene Implementierungen von Sets. Einige machen Einfüge- und Suchvorgänge durch Hashing-Elemente sehr schnell. Dies bedeutet jedoch, dass die Reihenfolge, in der die Elemente hinzugefügt wurden, verloren geht. Bei anderen Implementierungen bleibt die hinzugefügte Reihenfolge auf Kosten langsamerer Laufzeiten erhalten.

Die HashSetKlasse in C # geht für den ersten Ansatz, wobei die Reihenfolge der Elemente nicht beibehalten wird. Es ist viel schneller als ein normaler List. Einige grundlegende Benchmarks haben gezeigt, dass HashSet im Umgang mit Primärtypen (int, double, bool usw.) deutlich schneller ist. Es ist viel schneller, wenn Sie mit Klassenobjekten arbeiten. Der Punkt ist also, dass HashSet schnell ist.

Der einzige Haken dabei HashSetist, dass es keinen Zugriff durch Indizes gibt. Um auf Elemente zuzugreifen, können Sie entweder einen Enumerator verwenden oder die integrierte Funktion verwenden, um das HashSetin ein zu konvertieren Listund dieses zu durchlaufen. Schauen Sie hier

Kamaci
quelle
13
Zwei Dinge, Hashset und ähnliches, sind .NETs, ​​nicht C #. Auch HashSet behält die Ordnung nicht bei. Versuchen Sie, Elemente zu einem Hash-Set hinzuzufügen und daraus zu entfernen. Sie werden wissen, ob Sie später iterieren.
Nawfal
13

A HashSethat eine interne Struktur (Hash), in der Elemente schnell gesucht und identifiziert werden können. Der Nachteil ist, dass durch a iteriertHashSet (oder das Abrufen eines Elements nach Index) ziemlich langsam ist.

Warum sollte jemand wissen wollen, ob ein Eintrag bereits in einem Set vorhanden ist?

Eine Situation, in der a HashSetnützlich ist, besteht darin, eindeutige Werte aus einer Liste abzurufen, in der möglicherweise Duplikate vorhanden sind. Sobald ein Artikel zum hinzugefügt wurde, HashSetkann schnell festgestellt werden, ob der Artikel vorhanden ist ( ContainsOperator).

Weitere Vorteile der HashSetsind die Set - Vorgänge: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Wenn Sie mit der Sprache der Objektbeschränkungen vertraut sind, identifizieren Sie diese festgelegten Operationen. Sie werden auch sehen, dass es einer Implementierung von ausführbarer UML einen Schritt näher kommt.

k rey
quelle
20
Re: Nachteil. Nein, das Durchlaufen eines HashSets ist sehr schnell. Zweitens ist es nicht möglich, einen Artikel nach Index zu erhalten. Tatsächlich werden die Elemente ungeordnet gespeichert.
Nigel Touch
@ Nigel Touch. Das Iterieren ist schnell, wenn Sie sich nicht für den Index interessieren (Reihenfolge, in der sie hinzugefügt wurden). Wenn Sie sich jedoch Sorgen um den Index machen, muss der Index mit jedem Hash-Schlüssel gespeichert werden und kann daher ziemlich langsam sein, da die Liste gründlich durchsucht werden muss, um das richtige Element abzurufen. Dieses Verhalten unterscheidet sich stark von einer Liste, in der Elemente in der Reihenfolge indiziert werden, in der sie hinzugefügt werden.
k rey
Es macht Sinn, warum es schnell gehen würde, weil keine zwei Hashs gleich sind. Aktivieren der Abfrage, um einen "Kurzschluss" -Ansatz zu nutzen und bestimmte Kriterien schnell auszuschließen.
Chef_Code
8

Einfach gesagt und ohne die Geheimnisse der Küche preiszugeben: Ein Set im Allgemeinen ist eine Sammlung, die keine doppelten Elemente enthält und deren Elemente in keiner bestimmten Reihenfolge sind. A HashSet<T>ähnelt also einem Generikum List<T>, ist jedoch für schnelle Suchvorgänge (über Hashtabellen, wie der Name schon sagt) auf Kosten des Auftragsverlusts optimiert.

Gestapelt
quelle
1
Kann ein HashSet <T> jedoch zwei Objekte mit denselben Daten speichern, z. B. zwei Produktklassen mit jeweils denselben Eigenschaften und demselben Inhalt?
Johan Herstad
Ich denke, wir werden es nie erfahren
Denny
@JohanHerstad Angenommen, der EqualityComparer für Ihre Klasse kümmert sich um diese Eigenschaften, oder Sie erstellen das HashSet mit einem IEqualityComparer, der sich um diese Eigenschaften kümmert, verstehe ich nicht, warum dies nicht der Fall ist. Die Dokumentation für HashSet macht deutlich, dass es auf das eine oder andere angewiesen ist, um die Eindeutigkeit zu bestimmen.
Bacon Bits
2

Wenn Sie aus Anwendungssicht nur Duplikate vermeiden müssen, ist dies genau das, HashSetwonach Sie suchen, da die Komplexität beim Nachschlagen, Einfügen und Entfernen O (1) - konstant ist . Was dies bedeutet, dass es keine Rolle spielt, wie viele Elemente es HashSethat, wird die gleiche Zeit in Anspruch nehmen, um zu prüfen, ob es ein solches Element gibt oder nicht. Da Sie auch Elemente bei O (1) einfügen, ist es perfekt für diese Art von Dingen.

Matas Vaitkevicius
quelle