Jaka jest różnica między HashSet <T> a List <T>?


156

Czy możesz wyjaśnić, jaka jest różnica między HashSet<T>i List<T>w .NET?

Może mógłbyś wyjaśnić na przykładzie, HashSet<T>przeciwko czemu należy preferować przypadki List<T>?



Proponuję zapoznać się z artykułami Wikipedii na en.wikipedia.org/wiki/Hash_table i en.wikipedia.org/wiki/Dynamic_array .
mqp

Aby uzyskać informacje dotyczące wydajności, zobacz hashset-vs-list-performance
nawfal

Odpowiedzi:


213

W przeciwieństwie do listy <> ...

  1. HashSet to lista bez zduplikowanych członków.

  2. Ponieważ zestaw HashSet jest ograniczony tylko do unikalnych wpisów, struktura wewnętrzna jest zoptymalizowana pod kątem wyszukiwania (w porównaniu z listą) - jest znacznie szybsza

  3. Dodanie do HashSet zwraca wartość boolean - false, jeśli dodawanie nie powiedzie się z powodu już istniejącego w Set

  4. Może wykonywać operacje na zestawach matematycznych na zestawie: Union / Intersection / IsSubsetOf itp.

  5. HashSet nie implementuje IList only ICollection

  6. Nie można używać indeksów z HashSet, tylko modułami wyliczającymi.

Głównym powodem używania HashSet jest to, że jesteś zainteresowany wykonywaniem operacji na zbiorach.

Biorąc pod uwagę 2 zestawy: hashSet1 i hashSet2

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

leci w porównaniu z równoważną operacją przy użyciu LINQ. Ładniej jest też pisać!


IDK, miałem problemy z Unionmetodą. UnionWithZamiast tego użyłem .
użytkownik

2
+1 za „Głównym powodem korzystania z HashedSet byłoby zainteresowanie wykonywaniem operacji na zbiorach”.
LCJ

12
Właściwie wolę odpowiedź, która wskazuje, że HashSety są odpowiednie w przypadkach, gdy możesz traktować swoją kolekcję jako „przedmioty w torbie”. Operacje na zbiorach nie są tak częste jak kontrole przechowawcze. W dowolnym momencie, gdy masz zestaw unikatowych przedmiotów (np. Kody) i musisz sprawdzić, czy nie są one zabezpieczone, przydaje się zestaw HashSet.
ThunderGr,

Dobra odpowiedź. Kusi mnie, aby dodać kilka różnic charakterystycznych dla wydajności.
nawfal

1
Pytanie: głównym powodem nie jest to, aby mieć pewność, że nie będą one zduplikowane?
Andrea Scarafoni

54

Aby być bardziej precyzyjnym, pokażmy na przykładach,

Nie możesz użyć HashSet, jak w poniższym przykładzie.

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

hashSet1[i] spowodowałoby błąd:

Nie można zastosować indeksowania z [] do wyrażenia typu „System.Collections.Generic.HashSet”

Możesz użyć instrukcji foreach:

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

Nie możesz dodawać zduplikowanych elementów do HashSet, podczas gdy List pozwala na to, a podczas dodawania elementu do HashSet możesz sprawdzić, czy zawiera element, czy nie.

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 ma kilka przydatnych funkcji, takich jak IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith,SymmetricExceptWith itd.

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

Nawiasem mówiąc, kolejność nie jest zachowywana w HashSets. W przykładzie na końcu dodaliśmy element „2”, ale jest on w drugiej kolejności:

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

51

A HashSet<T>to klasa zaprojektowana, aby ci daćO(1) wyszukiwanie zawartości (tj. Czy ta kolekcja zawiera konkretny obiekt i szybko podaj mi odpowiedź).

A List<T>to klasa zaprojektowana w celu zapewnienia kolekcji z O(1)losowym dostępem, która może rosnąć dynamicznie (pomyśl o tablicy dynamicznej). Możesz testować zawieranie w O(n)czasie (jeśli lista nie jest posortowana, możesz przeprowadzić wyszukiwanie binarne w O(log n)czasie).

Może możesz wyjaśnić na przykładzie, w jakich przypadkach HashSet<T>należy preferowaćList<T>

Gdy chcesz przetestować zawieranie w O(1).


Z wyjątkiem O (log n), jeśli lista jest posortowana; w końcu jest szybszy niż wyszukiwanie na niesortowanej liście.
Andrei

20

Użyj a, List<T>jeśli chcesz:

  • Przechowuj kolekcję przedmiotów w określonej kolejności.

Jeśli znasz indeks żądanego elementu (a nie wartość samego elementu), pobieranie to O(1). Jeśli nie znasz indeksu, znalezienie elementu zajmuje więcej czasu O(n)w przypadku nieposortowanej kolekcji.

Użyj a, Hashset<T>jeśli chcesz:

  • Szybko dowiedz się, czy dany obiekt znajduje się w kolekcji.

Jeśli znasz nazwę rzeczy, którą chcesz znaleźć, Lookup to O(1)(to jest część „Hash”). Nie utrzymuje kolejności tak jak List<T>robi i nie możesz przechowywać duplikatów (dodanie duplikatu nie ma żadnego efektu, to jest część „Zestaw”).

Przykład zastosowania pliku Hashset<T> byłoby sprawdzenie, czy słowo w grze Scrabble jest poprawnym słowem w języku angielskim (lub innym). Jeszcze lepiej byłoby, gdybyś chciał zbudować usługę sieciową, z której będą korzystać wszystkie instancje wersji online takiej gry.

List<T>Byłaby dobra struktura danych do tworzenia wynik śledzić wyniki zawodnika.


15

Lista to uporządkowana lista. To jest

  • dostępny przez indeks całkowity
  • może zawierać duplikaty
  • ma przewidywalną kolejność

HashSet to zestaw. To:

  • Może blokować zduplikowane elementy (patrz Dodaj (T) )
  • Nie gwarantuje kolejności elementów w zestawie
  • Zawiera operacje, których można oczekiwać na zbiorze, np. IntersectWith, IsProperSubsetOf, UnionWith.

Lista jest bardziej odpowiednia, gdy chcesz uzyskać dostęp do swojej kolekcji tak, jakby była jak tablica, do której możesz dołączać, wstawiać i usuwać elementy. HashSet to lepszy wybór, jeśli chcesz traktować swoją kolekcję jak „worek” przedmiotów, w których kolejność nie jest ważna lub gdy chcesz porównać ją z innymi zestawami za pomocą operacji takich jak IntersectWith lub UnionWith.



3

Lista jest uporządkowaną kolekcją obiektów typu T, które w przeciwieństwie do tablicy można dodawać i usuwać wpisy.

Możesz użyć listy, na której chcesz odwoływać się do członków w kolejności, w jakiej ich zapisałeś, i uzyskujesz do nich dostęp za pomocą pozycji, a nie samego elementu.

HashSet jest jak słownik, w którym sam element jest kluczem, a także wartością, kolejność nie jest gwarantowana.

Użyłbyś HashSet, w którym chcesz sprawdzić, czy obiekt znajduje się w kolekcji


1
Dla wyjaśnienia, na wypadek, gdyby ktoś na pierwszy rzut oka źle to odczytał - Listutrzymuje kolejność (tj. Kiedy rzeczy zostały dodane), ale nie sortuje automatycznie pozycji. Musisz zadzwonić .Sortlub użyć SortedList.
drzaus

1

Jeśli zdecydujesz się zastosować te struktury danych do rzeczywistego wykorzystania w programowaniu opartym na danych, zestaw HashSet jest BARDZO pomocny w testowaniu replikacji ze źródłami adapterów danych w celu czyszczenia i migracji danych.

Ponadto, korzystając z klasy DataAnnotations, można zaimplementować logikę klucza we właściwościach klasy i skutecznie kontrolować indeks naturalny (klastrowany lub nie) za pomocą zestawu HashSet, gdzie byłoby to bardzo trudne w implementacji listy.

Mocną opcją korzystania z listy jest zaimplementowanie typów ogólnych dla wielu mediów w modelu widoku, na przykład wysłanie listy klas do widoku MVC dla pomocnika DropDownList, a także do wysyłania jako konstrukcji JSON za pośrednictwem WebApi. Lista pozwala na typową logikę zbierania klas i zachowuje elastyczność w podejściu bardziej "interfejsowym" do obliczania modelu pojedynczego widoku na różnych mediach.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.