Zdefiniuj: Co to jest HashSet?

420

HashSet Struktura danych C # HashSet została wprowadzona w .NET Framework 3.5. Pełna lista zaimplementowanych elementów znajduje się na stronie MSDN HashSet .

  1. Gdzie jest używany?
  2. Dlaczego chcesz tego używać?
c# hashset 001
źródło
4
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
możliwy duplikat Kiedy należy użyć typu HashSet <T>?
nawfal
Wykorzystuje wewnętrznie hashtable. jeśli masz dobrą implementację tablicy mieszającej (na przykład Słownik <T>), możesz łatwo zaimplementować HashSet.
Raz Megrelidze

Odpowiedzi:

614

    1. HashSetPosiada zestaw obiektów, ale w sposób, który pozwala łatwo i szybko określić, czy obiekt jest już w zestawie czy nie. Odbywa się to poprzez wewnętrzne zarządzanie tablicą i przechowywanie obiektu za pomocą indeksu obliczanego na podstawie kodu skrótu obiektu. Spójrz tutaj

    2. HashSetto nieuporządkowana kolekcja zawierająca unikalne elementy. Ma standardowe operacje gromadzenia: Dodaj, Usuń, Zawiera, ale ponieważ używa implementacji opartej na haszowaniu, te operacje to O (1). (W przeciwieństwie na przykład do Listy, która jest O (n) dla Zawartości i Usuń.) HashSetZapewnia również standardowe operacje ustawiania, takie jak suma , przecięcie i różnica symetryczna . Spójrz tutaj

  2. Istnieją różne implementacje zestawów. Niektóre sprawiają, że operacje wstawiania i wyszukiwania są super szybkie dzięki elementom mieszającym. Oznacza to jednak, że kolejność dodawania elementów została utracona. Inne implementacje pozwalają zachować dodatkową kolejność kosztem dłuższego czasu działania.

HashSetKlasy w języku C # idzie za pierwszym podejściem, a tym samym nie zachowując kolejność elementów. Jest znacznie szybszy niż zwykły List. Niektóre podstawowe testy porównawcze wykazały, że HashSet jest przyzwoicie szybszy w przypadku typów podstawowych (int, double, bool itp.). Jest znacznie szybszy podczas pracy z obiektami klasy. Chodzi o to, że HashSet jest szybki.

Jedynym haczykiem HashSetjest to, że indeksy nie mają dostępu. Aby uzyskać dostęp do elementów, możesz użyć modułu wyliczającego lub użyć wbudowanej funkcji, aby przekonwertować HashSetplik na Listi iterować przez to. Spójrz tutaj

kamaci
źródło
13
Dwie rzeczy, hashset i podobne to .NET, a nie C #. Również HashSet nie zachowuje porządku. Spróbuj dodać i usunąć elementy z zestawu skrótów, będziesz wiedział, czy wykonasz iterację później ..
nawfal
13

HashSetMa strukturę wewnętrzną (hash), gdzie elementy mogą być wyszukiwane i identyfikowane szybko. Minusem jest to, że iteracja po HashSet(lub uzyskiwanie elementu według indeksu) jest raczej powolna.

Dlaczego więc ktoś chciałby wiedzieć, czy pozycja istnieje już w zestawie?

Jedną z sytuacji, w których HashSetużyteczne jest a, jest uzyskanie odrębnych wartości z listy, na której mogą istnieć duplikaty. Po dodaniu elementu HashSetmożna szybko ustalić, czy element istnieje ( Containsoperator).

Inne zalety HashSetto operacje Set: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Jeśli znasz język ograniczeń obiektowych , rozpoznasz te ustawione operacje. Zobaczysz również, że jest to krok bliżej implementacji wykonywalnego UML.

k rey
źródło
20
Re: minus. Nie, iteracja po HashSet jest całkowicie szybka. Po drugie, nie można uzyskać przedmiotu według indeksu. W rzeczywistości elementy są przechowywane nieuporządkowane.
Nigel Touch
@Nigel Touch. Iteracja jest szybka, jeśli nie obchodzi Cię indeks (kolejność, w jakiej zostały dodane). Jeśli jednak martwisz się indeksem, indeks musi być przechowywany z każdym kluczem skrótu, a zatem może być dość powolny, ponieważ lista musi być wyczerpująco przeszukana, aby uzyskać właściwy element. To zachowanie różni się bardzo od listy, w której elementy są indeksowane według kolejności ich dodawania.
k rey
Ma sens, dlaczego miałoby to być szybkie, ponieważ nie ma dwóch identycznych skrótów. Umożliwiając kwerendie skorzystanie z podejścia „zwarciowego”, szybko wykluczając określone kryteria.
Chef_Code
8

Mówiąc prosto i bez ujawniania tajemnic kuchni: zestaw ogólnie, to kolekcja, która nie zawiera zduplikowanych elementów i której elementy nie są ułożone w określonej kolejności. Tak więc A HashSet<T>jest podobny do ogólnego List<T>, ale jest zoptymalizowany do szybkiego wyszukiwania (za pomocą skrótów, jak sama nazwa wskazuje) kosztem utraty zamówienia.

Ułożone
źródło
1
Ale czy HashSet <T> może przechowywać dwa obiekty, które mają te same dane, na przykład dwie klasy Product, z których każda ma te same właściwości o tej samej zawartości?
Johan Herstad
Chyba nigdy się nie dowiemy
Denny,
@JohanHerstad Zakładając, że dla EqualityComparer dla twojej klasy zależy na tych właściwościach lub że budujesz HashSet z IEqualityComparer, który troszczy się o te właściwości, nie rozumiem, dlaczego by to nie miało. Dokumentacja HashSet wyjaśnia, że opiera się ona na jednej lub drugiej w celu określenia wyjątkowość.
Bacon Bits
2

Z perspektywy aplikacji, jeśli trzeba tylko unikać duplikatów, to HashSetjest to, czego szukasz, ponieważ złożoność wyszukiwania, wstawiania i usuwania jest stała O (1) - stała . Co to znaczy, że nie ma znaczenia, ile elementów HashSetma to tyle samo czasu, aby sprawdzić, czy jest taki element, czy nie, a ponadto, ponieważ wstawiasz elementy również w O (1), to czyni go idealnym do tego rodzaju rzeczy.

Matas Vaitkevicius
źródło