Kiedy należy używać typu HashSet <T>?

Badam ten HashSet<T>typ, ale nie rozumiem, jakie miejsce zajmuje w kolekcjach.

Czy można go użyć do zastąpienia List<T>? Wyobrażam sobie, że działanie a HashSet<T>jest lepsze, ale nie widziałem indywidualnego dostępu do jego elementów.

Czy to tylko do wyliczenia?

Ważna rzecz HashSet<T>jest w nazwie: to zestaw . Jedyne, co możesz zrobić z pojedynczym zestawem, to ustalić, jakie są jego elementy i sprawdzić, czy element jest członkiem.

Pytanie, czy możesz pobrać pojedynczy element (np. set[45]), Jest niezrozumieniem koncepcji zbioru. Nie ma czegoś takiego jak 45. element zestawu. Elementy w zestawie nie mają zamówienia. Zbiory {1, 2, 3} i {2, 3, 1} są identyczne pod każdym względem, ponieważ mają to samo członkostwo, a liczy się tylko członkostwo.

Iterowanie po a jest nieco niebezpieczne, HashSet<T>ponieważ narzuca porządek na elementach zestawu. Ta kolejność nie jest tak naprawdę właściwością zbioru. Nie powinieneś na tym polegać. Jeśli porządkowanie pozycji w kolekcji jest dla Ciebie ważne, ta kolekcja nie jest zestawem.

Zestawy są naprawdę ograniczone i mają unikalnych członków. Z drugiej strony są naprawdę szybkie.

Oto prawdziwy przykład, w którym używam HashSet<string>:

Częścią mojego wyróżnienia składni dla plików UnrealScript jest nowa funkcja, która wyróżnia komentarze w stylu Doxygen . Muszę być w stanie stwierdzić, @czy \polecenie lub jest prawidłowe, aby określić, czy pokazać je w kolorze szarym (prawidłowe), czy czerwonym (nieprawidłowe). Mam HashSet<string>ze wszystkich poprawnych poleceń, więc za każdym razem, gdy uderzę w @xxxtoken w lexerze, używam validCommands.Contains(tokenText)jako mojego sprawdzenia poprawności O (1). Naprawdę nie obchodzi mnie nic poza istnieniem polecenia w zestawie prawidłowych poleceń. Spójrzmy na alternatywy, z którymi się spotkałem:

• Dictionary<string, ?>: Jakiego typu użyć dla wartości? Wartość jest bez znaczenia, ponieważ zamierzam po prostu użyć ContainsKey. Uwaga: przed .NET 3.0 był to jedyny wybór dla wyszukiwań O (1) - HashSet<T>został dodany do 3.0 i rozszerzony do implementacji ISet<T>dla 4.0.
• List<string>: Jeśli utrzymam posortowaną listę, mogę użyć BinarySearch, czyli O (log n) (nie widziałem tego faktu wspomnianego powyżej). Ponieważ jednak moja lista prawidłowych poleceń to stała lista, która nigdy się nie zmienia, nigdy nie będzie to bardziej odpowiednie niż po prostu ...
• string[]: Ponownie, Array.BinarySearchdaje wydajność O (log n). Jeśli lista jest krótka, może to być najlepsza opcja. Zawsze ma mniej miejsca niż narzut HashSet, Dictionarylub List. Nawet BinarySearchw przypadku dużych zestawów nie jest to szybsze, ale w przypadku małych zestawów warto byłoby poeksperymentować. Mój ma jednak kilkaset pozycji, więc przekazałem to.

A HashSet<T>implementuje ICollection<T>interfejs:

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; }
}

A List<T>narzędzia IList<T>, która rozszerzaICollection<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; }
}

HashSet ma ustawioną semantykę, zaimplementowaną wewnętrznie za pomocą tablicy haszującej:

Zestaw to zbiór, który nie zawiera zduplikowanych elementów i którego elementy nie są w określonej kolejności.

Co zyskuje HashSet, jeśli utraci zachowanie indeksu / pozycji / listy?

Dodawanie i pobieranie elementów z HashSet jest zawsze wykonywane przez sam obiekt, a nie przez indeksator i blisko operacji O (1) (lista to O (1) dodawanie, O (1) pobieranie według indeksu, O (n) znajdowanie /usunąć).

Zachowanie HashSet można porównać do używania a Dictionary<TKey,TValue>, dodając / usuwając klucze jako wartości i ignorując same wartości słownikowe. Można by oczekiwać, że klucze w słowniku nie będą miały zduplikowanych wartości i to jest sedno części „Set”.

Wydajność byłaby złym powodem, aby wybrać HashSet zamiast List. Zamiast tego, co lepiej oddaje twoje zamiary? Jeśli kolejność jest ważna, to Set (lub HashSet) jest niedostępny. Podobnie, jeśli dozwolone są duplikaty. Ale jest wiele okoliczności, w których nie dbamy o porządek i wolelibyśmy nie mieć duplikatów - i właśnie wtedy potrzebujesz zestawu.

HashSet to zestaw implementowany przez haszowanie. Zestaw to zbiór wartości, które nie zawierają zduplikowanych elementów. Wartości w zestawie również są zazwyczaj nieuporządkowane. Więc nie, zestaw nie może być użyty do zastąpienia listy (chyba że powinieneś był użyć zestawu w pierwszej kolejności).

Jeśli zastanawiasz się, do czego może się przydać zestaw: oczywiście wszędzie tam, gdzie chcesz pozbyć się duplikatów. Jako nieco wymyślony przykład, załóżmy, że masz listę 10.000 wersji projektów oprogramowania i chcesz dowiedzieć się, ile osób przyczyniło się do tego projektu. Możesz użyć a Set<string>i iterować po liście rewizji i dodać autora każdej rewizji do zestawu. Po zakończeniu iteracji rozmiar zestawu jest odpowiedzią, której szukałeś.

HashSet byłby używany do usuwania zduplikowanych elementów w kolekcji IEnumerable. Na przykład,

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

po uruchomieniu tych kodów uniqueStrings przechowuje {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

Prawdopodobnie najczęstszym zastosowaniem hashetów jest sprawdzenie, czy zawierają one pewien element, który jest dla nich bliski operacji O (1) (zakładając wystarczająco silną funkcję haszującą), w przeciwieństwie do list, dla których sprawdzanie włączenia jest O ( n) (i posortowane zbiory, dla których jest to O (log n)). Więc jeśli wykonujesz wiele sprawdzeń, czy pozycja znajduje się na jakiejś liście, hahssets może oznaczać poprawę wydajności. Jeśli kiedykolwiek będziesz je iterować, nie będzie dużej różnicy (iteracja po całym zestawie to O (n), tak samo jak w przypadku list i hashsetów, które mają nieco więcej narzutu podczas dodawania elementów).

I nie, nie możesz zindeksować zestawu, co i tak nie miałoby sensu, ponieważ zestawy nie są uporządkowane. Jeśli dodasz jakieś elementy, zestaw nie zapamięta, który był pierwszy, a który drugi itd.

HashSet<T>jest strukturą danych w środowisku .NET, która jest w stanie przedstawić zestaw matematyczny jako obiekt. W tym przypadku używa kodów skrótu ( GetHashCodewyniku każdego elementu) do porównania równości elementów zestawu.

Zestaw różni się od listy tym, że dopuszcza tylko jedno wystąpienie tego samego elementu w nim zawartego. HashSet<T>po prostu zwróci, falsejeśli spróbujesz dodać drugi identyczny element. Rzeczywiście, wyszukiwanie elementów jest bardzo szybkie ( O(1)czas), ponieważ wewnętrzna struktura danych jest po prostu haszowana.

Jeśli zastanawiasz się, którego użyć, pamiętaj, że użycie List<T>gdzie HashSet<T>jest właściwe nie jest największym błędem, chociaż może potencjalnie powodować problemy, gdy masz niepożądane zduplikowane elementy w swojej kolekcji. Co więcej, wyszukiwanie (pobieranie przedmiotów) jest znacznie bardziej wydajne - najlepiej O(1)(dla idealnego zasobnika) zamiast O(n)czasu - co jest dość ważne w wielu scenariuszach.

List<T>służy do przechowywania uporządkowanych zestawów informacji. Jeśli znasz względną kolejność elementów listy, możesz uzyskać do nich dostęp w stałym czasie. Jednak aby określić, gdzie element znajduje się na liście lub sprawdzić, czy istnieje na liście, czas wyszukiwania jest liniowy. Z drugiej strony,HashedSet<T> nie gwarantuje porządku przechowywanych danych, a co za tym idzie zapewnia stały czas dostępu do ich elementów.

Jak sama nazwa wskazuje, HashedSet<T>implementuje strukturę danych semantykę zbioru . Struktura danych jest zoptymalizowana pod kątem implementacji operacji na zestawach (tj. Suma, Różnica, Przecięcie), czego nie można wykonać tak wydajnie w przypadku tradycyjnej implementacji listy.

Tak więc wybór typu danych do użycia naprawdę zależy od tego, co próbujesz zrobić z aplikacją. Jeśli nie obchodzi Cię kolejność elementów w kolekcji i chcesz tylko wyliczyć lub sprawdzić istnienie, użyj HashSet<T>. W przeciwnym razie rozważ użycie List<T>lub innej odpowiedniej struktury danych.

Krótko mówiąc - za każdym razem, gdy masz ochotę użyć słownika (lub słownika, w którym S jest własnością T), powinieneś rozważyć HashSet (lub HashSet + implementujący IEquatable na T, który równa się S)

W podstawowym zamierzonym scenariuszu HashSet<T>należy używać, gdy chcesz uzyskać bardziej szczegółowe operacje na dwóch kolekcjach niż zapewnia LINQ. Metody LINQ podoba Distinct, Union, Intersecti Exceptsą na tyle w większości przypadków, ale czasami może być konieczne kolejne operacje drobnoziarnistą i HashSet<T>zapewnia:

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

Inną różnicą między HashSet<T>metodami LINQ i „nakładającymi się” jest to, że LINQ zawsze zwraca nowy IEnumerable<T>, a HashSet<T>metody modyfikują kolekcję źródłową.