442 Stimmen

Definieren Sie: Was ist ein HashSet?

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

  1. Wo wird es verwendet?
  2. Warum sollten Sie es verwenden?

634voto

kamaci Punkte 69025
    1. A HashSet enthält eine Menge von Objekten, aber auf eine Weise, die es Ihnen ermöglicht, einfach und schnell festzustellen, ob ein Objekt bereits in der Menge enthalten ist oder nicht. Dazu wird intern ein Array verwaltet und das Objekt mit einem Index gespeichert, der anhand des Hashcodes des Objekts berechnet wird. Schauen Sie hier
  1. HashSet ist eine ungeordnete Sammlung mit eindeutigen Elementen. Sie verfügt über die Standard-Sammlungsoperationen Add, Remove, Contains, aber da sie eine hashbasierte Implementierung verwendet, sind diese Operationen O(1). (Im Gegensatz zum Beispiel zu List, das für Contains und Remove O(n) ist). HashSet bietet auch Standardmengenoperationen wie Gewerkschaft , Kreuzung y Symmetriedifferenz . Schauen Sie hier

  2. Es gibt verschiedene Implementierungen von Sets. Einige machen Einfüge- und Nachschlageoperationen superschnell, indem sie Elemente hashen. Das bedeutet jedoch, dass die Reihenfolge, in der die Elemente hinzugefügt wurden, verloren geht. Andere Implementierungen bewahren die hinzugefügte Reihenfolge um den Preis langsamerer Laufzeiten.

Le site HashSet Klasse in C# wählt den ersten Ansatz, also pas wobei die Reihenfolge der Elemente beibehalten wird. Es ist viel schneller als eine reguläre List . Einige grundlegende Benchmarks haben gezeigt, dass HashSet bei der Arbeit mit primären Typen (int, double, bool usw.) anständig schnell ist. Es ist sehr viel schneller, wenn es mit Klassenobjekten arbeitet. Der Punkt ist also, dass HashSet schnell ist.

Der einzige Fang von HashSet ist, dass es keinen Zugriff über Indizes gibt. Um auf Elemente zuzugreifen, können Sie entweder einen Enumerator verwenden oder die eingebaute Funktion nutzen, um die HashSet in eine List und iterieren diese. Schauen Sie hier

14voto

k rey Punkte 591

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

Warum also sollte jemand wissen wollen, ob ein Eintrag bereits in einer Menge vorhanden ist?

Eine Situation, in der ein HashSet ist nützlich, um eindeutige Werte aus einer Liste zu erhalten, in der es möglicherweise Duplikate gibt. Sobald ein Element in die Liste HashSet lässt sich schnell feststellen, ob der Artikel existiert ( Contains Operator).

Weitere Vorteile des HashSet sind die Mengenoperationen: IntersectWith , IsSubsetOf , IsSupersetOf , Overlaps , SymmetricExceptWith , UnionWith .

Wenn Sie sich mit dem Objektbeschränkungssprache dann werden Sie diese Mengenoperationen erkennen. Sie werden auch sehen, dass Sie damit einen Schritt näher an eine Implementierung der ausführbaren UML herankommen.

10voto

Stacked Punkte 6174

Einfach gesagt und ohne die Küchengeheimnisse zu verraten: eine Menge im Allgemeinen ist eine Sammlung, die keine doppelten Elemente enthält und deren Elemente in keiner bestimmten Reihenfolge angeordnet sind. Also, A HashSet<T> ist vergleichbar mit einem generischen List<T> , ist jedoch für schnelle Suchvorgänge (über Hashtabellen, wie der Name schon sagt) optimiert, was jedoch zu einem Verlust an Ordnung führt.

2voto

Matas Vaitkevicius Punkte 53532

Aus der Sicht der Anwendung, wenn man nur Duplikate vermeiden will, dann HashSet ist das, wonach Sie suchen, denn es ist Lookup, Insert und Remove Komplexitäten sind O(1) - konstant . Das bedeutet, dass es keine Rolle spielt, wie viele Elemente HashSet hat es wird die gleiche Menge an Zeit, um zu überprüfen, ob es ein solches Element oder nicht, plus, da Sie Elemente bei O (1) einfügen auch macht es perfekt für diese Art von Sache.

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X