Was ist der Unterschied zwischen HashSet <T> und List <T>?

156

Können Sie erklären, was der Unterschied zwischen HashSet<T>und List<T>in .NET ist?

Vielleicht können Sie anhand eines Beispiels erklären, in welchen Fällen Sie HashSet<T>bevorzugt werden sollten List<T>?

Bleistiftkuchen
quelle
22
Einige Lektüre zum Thema: C # /. NET Fundamentals: Auswahl der richtigen Sammlungsklasse
Fredrik Mörk
Ich schlage vor, Sie konsultieren die Wikipedia-Artikel auf en.wikipedia.org/wiki/Hash_table und en.wikipedia.org/wiki/Dynamic_array .
mqp

Antworten:

213

Im Gegensatz zu einer Liste <> ...

  1. Ein HashSet ist eine Liste ohne doppelte Mitglieder.

  2. Da ein HashSet nur eindeutige Einträge enthalten darf, ist die interne Struktur für die Suche optimiert (im Vergleich zu einer Liste) - sie ist erheblich schneller

  3. Das Hinzufügen zu einem HashSet gibt einen Booleschen Wert zurück - false, wenn das Hinzufügen fehlschlägt, weil es bereits in Set vorhanden ist

  4. Kann mathematische Mengenoperationen für eine Menge ausführen: Union / Intersection / IsSubsetOf usw.

  5. HashSet implementiert nicht nur IList ICollection

  6. Sie können mit einem HashSet keine Indizes verwenden, sondern nur Enumeratoren.

Der Hauptgrund für die Verwendung eines HashSet ist, wenn Sie Set-Operationen ausführen möchten.

Gegeben 2 Sätze: hashSet1 und hashSet2

 //returns a list of distinct items in both sets
 HashSet set3 = set1.Union( set2 );

fliegt im Vergleich zu einer äquivalenten Operation mit LINQ. Es ist auch ordentlicher zu schreiben!

BonyT
quelle
IDK, ich hatte Probleme mit der UnionMethode. Ich hatte UnionWithstattdessen verwendet.
Benutzer
2
+1 für "Der Hauptgrund für die Verwendung eines HashedSet ist, wenn Sie an der Ausführung von Set-Operationen interessiert sind."
LCJ
12
Eigentlich bevorzuge ich die Antwort, die darauf hinweist, dass HashSets für den Fall geeignet sind, dass Sie Ihre Sammlung als "Taschenartikel" behandeln können. Festgelegte Vorgänge sind nicht so häufig wie Containment-Prüfungen. An jedem Punkt, an dem Sie eine Reihe eindeutiger Elemente (z. B. Codes) haben und auf Eindämmung prüfen müssen, ist ein HashSet praktisch.
ThunderGr
Gute Antwort. Ich bin versucht, auch einige Unterschiede in den Leistungsmerkmalen hinzuzufügen.
Nawfal
1
Frage: Der Hauptgrund ist, nicht die Gewissheit zu haben, keine doppelten Elemente zu haben?
Andrea Scarafoni
54

Um genauer zu sein, lassen Sie uns anhand von Beispielen demonstrieren:

Sie können HashSet nicht wie im folgenden Beispiel verwenden.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
for (int i = 0; i < hashSet1.Count; i++)
    Console.WriteLine(hashSet1[i]);

hashSet1[i] würde einen Fehler erzeugen:

Die Indizierung mit [] kann nicht auf einen Ausdruck vom Typ 'System.Collections.Generic.HashSet' angewendet werden.

Sie können foreach-Anweisung verwenden:

foreach (var item in hashSet1)
    Console.WriteLine(item);

Sie können HashSet keine doppelten Elemente hinzufügen, während List dies zulässt. Während Sie HashSet ein Element hinzufügen, können Sie überprüfen, ob es das Element enthält oder nicht.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
if (hashSet1.Add("1"))
   Console.WriteLine("'1' is successfully added to hashSet1!");
else
   Console.WriteLine("'1' could not be added to hashSet1, because it contains '1'");

HashSet hat einige nützliche Funktionen wie IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith, SymmetricExceptWithusw.

IsProperSubsetOf::

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
HashSet<string> hashSet3 = new HashSet<string>() { "1", "2", "3", "4", "5" };
if (hashSet1.IsProperSubsetOf(hashSet3))
    Console.WriteLine("hashSet3 contains all elements of hashSet1.");
if (!hashSet1.IsProperSubsetOf(hashSet2))
    Console.WriteLine("hashSet2 does not contains all elements of hashSet1.");

UnionWith::

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
hashSet1.UnionWith(hashSet2); //hashSet1 -> 3, 2, 4, 6, 8

IntersectWith::

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }
hashSet1.IntersectWith(hashSet2);//hashSet1 -> 4, 8

ExceptWith ::

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.ExceptWith(hashSet2);//hashSet1 -> 5, 6

SymmetricExceptWith ::

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.SymmetricExceptWith(hashSet2);//hashSet1 -> 4, 5, 6

Die Reihenfolge bleibt übrigens nicht in HashSets erhalten. Im Beispiel haben wir zuletzt das Element "2" hinzugefügt, aber es ist in der zweiten Reihenfolge:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
hashSet1.Add("1");    // 3, 4, 8, 1
hashSet1.Remove("4"); // 3, 8, 1
hashSet1.Add("2");    // 3, 2 ,8, 1
GorkemHalulu
quelle
51

A HashSet<T>ist eine Klasse, mit der Sie O(1)nach Containment suchen können (dh enthält diese Sammlung ein bestimmtes Objekt und gibt mir die Antwort schnell).

A List<T>ist eine Klasse, die Ihnen eine Sammlung mit O(1)wahlfreiem Zugriff bietet, die dynamisch wachsen kann (denken Sie an ein dynamisches Array). Sie können die Eindämmung O(n)rechtzeitig testen (sofern die Liste nicht sortiert ist, können Sie eine binäre Suche O(log n)rechtzeitig durchführen).

Vielleicht können Sie anhand eines Beispiels erklären, in welchen Fällen HashSet<T>dies vorzuziehen istList<T>

Wenn Sie das Containment in testen möchten O(1).

Jason
quelle
Außer es ist O (log n), wenn die Liste sortiert ist; es ist schließlich schneller als das Nachschlagen in einer unsortierten Liste.
Andrei
20

Verwenden Sie a, List<T>wenn Sie möchten:

  • Speichern Sie eine Sammlung von Artikeln in einer bestimmten Reihenfolge.

Wenn Sie den Index des gewünschten Elements kennen (und nicht den Wert des Elements selbst), ist der Abruf O(1). Wenn Sie den Index nicht kennen, dauert das Auffinden des Elements O(n)für eine unsortierte Sammlung länger .

Verwenden Sie a, Hashset<T>wenn Sie möchten:

  • Finden Sie schnell heraus, ob ein bestimmtes Objekt in einer Sammlung enthalten ist.

Wenn Sie den Namen des Objekts kennen, das Sie suchen möchten, lautet Lookup O(1)(das ist der 'Hash'-Teil). Es wird keine Reihenfolge wie in der Reihenfolge beibehalten List<T>und Sie können keine Duplikate speichern (das Hinzufügen eines Duplikats hat keine Auswirkung, das ist der 'Set'-Teil).

Ein Beispiel für die Verwendung von a Hashset<T>wäre, wenn Sie herausfinden möchten, ob ein in einem Scrabble-Spiel gespieltes Wort ein gültiges Wort in Englisch (oder einer anderen Sprache) ist. Noch besser wäre es, wenn Sie einen Webdienst erstellen möchten, der von allen Instanzen einer Online-Version eines solchen Spiels verwendet wird.

A List<T>wäre eine gute Datenstruktur zum Erstellen der Anzeigetafel zur Verfolgung der Spielerergebnisse.

Waylon Flinn
quelle
15

Liste ist eine geordnete Liste. Es ist

  • Zugriff über einen Integer-Index
  • kann Duplikate enthalten
  • hat eine vorhersehbare Reihenfolge

HashSet ist eine Menge. Es:

  • Kann doppelte Elemente blockieren (siehe Hinzufügen (T) )
  • Garantiert nicht die Reihenfolge der Artikel innerhalb des Sets
  • Hat Operationen, die Sie für einen Satz erwarten würden, z. B. IntersectWith, IsProperSubsetOf, UnionWith.

Die Liste ist besser geeignet, wenn Sie auf Ihre Sammlung zugreifen möchten, als wäre sie wie ein Array, an das Sie Elemente anhängen, einfügen und entfernen können. HashSet ist die bessere Wahl, wenn Sie Ihre Sammlung wie eine "Tüte" mit Elementen behandeln möchten, deren Reihenfolge nicht wichtig ist, oder wenn Sie sie mit anderen Sets mithilfe von Operationen wie IntersectWith oder UnionWith vergleichen möchten.

dgvid
quelle
3

Die Liste ist nicht unbedingt eindeutig, während das Hashset zum einen eindeutig ist.

die realen Steckverbinder
quelle
3

Eine Liste ist eine geordnete Sammlung von Objekten vom Typ T, mit denen Sie im Gegensatz zu einem Array Einträge hinzufügen und entfernen können.

Sie würden eine Liste verwenden, in der Sie die Mitglieder in der Reihenfolge referenzieren möchten, in der Sie sie gespeichert haben, und auf die Sie über eine Position anstatt über das Element selbst zugreifen.

Ein HashSet ist wie ein Wörterbuch, bei dem der Artikel selbst sowohl der Schlüssel als auch der Wert ist. Die Reihenfolge ist nicht garantiert.

Sie würden ein HashSet verwenden, mit dem Sie überprüfen möchten, ob sich ein Objekt in der Auflistung befindet

Bob Vale
quelle
1
Zur Verdeutlichung: Falls jemand anderes das auf den ersten Blick falsch liest - Listbehält eine Reihenfolge bei (dh wann Dinge hinzugefügt wurden), sortiert jedoch nicht automatisch Elemente. Sie müssten a anrufen .Sortoder verwenden SortedList.
Drzaus
1

Wenn Sie diese Datenstrukturen auf die tatsächliche Verwendung in der datengesteuerten Entwicklung anwenden möchten, ist ein HashSet SEHR hilfreich, um die Replikation anhand von Datenadapterquellen für die Datenbereinigung und -migration zu testen.

Wenn Sie die DataAnnotations-Klasse verwenden, können Sie die Schlüssellogik für Klasseneigenschaften implementieren und einen natürlichen Index (gruppiert oder nicht) mit einem HashSet effektiv steuern, wobei dies in einer List-Implementierung sehr schwierig wäre.

Eine gute Option für die Verwendung einer Liste ist die Implementierung von Generika für mehrere Medien in einem Ansichtsmodell, z. B. das Senden einer Liste von Klassen an eine MVC-Ansicht für einen DropDownList-Helper und das Senden als JSON-Konstrukt über WebApi. Die Liste ermöglicht eine typische Klassensammlungslogik und bietet Flexibilität für einen "Interface" -ähnlichen Ansatz zur Berechnung eines einzelnen Ansichtsmodells für verschiedene Medien.

Nathan Teague
quelle