Słownik .NET HashTable Vs Dictionary - czy słownik może być tak szybki?

276

Próbuję dowiedzieć się, kiedy i dlaczego korzystać ze słownika lub tabeli HashTable. Przeprowadziłem tutaj trochę wyszukiwania i znalazłem ludzi mówiących o ogólnych zaletach Słownika, z którymi całkowicie się zgadzam, co prowadzi do przewagi nad boksem i rozpakowaniem dla niewielkiego wzrostu wydajności.

Ale przeczytałem również, że Słownik nie zawsze zwróci obiekty w kolejności, w jakiej zostały wstawione, co jest posortowane. Gdzie będzie jak HashTable. Jak rozumiem, prowadzi to do tego, że HashTable jest znacznie szybszy w niektórych sytuacjach.

Moje pytanie jest naprawdę, jakie mogą być te sytuacje? Czy po prostu mylę się w powyższych założeniach? Jakie sytuacje możesz wykorzystać, aby wybrać jedną z nich (tak, ta ostatnia jest nieco niejednoznaczna).

Jon
źródło
5
Nie chcę tego głosować, ale twoja karma wynosi 7 777 i nie chcę być facetem, który ci to przeszkadza.
CaptainMarvel

Odpowiedzi:

298

System.Collections.Generic.Dictionary<TKey, TValue>a System.Collections.Hashtableobie klasy wewnętrznie utrzymują strukturę danych tabeli skrótów. Żadna z nich nie gwarantuje zachowania kolejności produktów.

Pomijając problemy z boksem / rozpakowaniem, przez większość czasu powinny one mieć bardzo podobną wydajność.

Podstawowa różnica strukturalna między nimi Dictionarypolega na łączeniu łańcuchów (utrzymywanie listy elementów dla każdego segmentu tabeli skrótów) w celu rozstrzygania kolizji, a podczas ponownego rozwiązywania kolizji jest Hashtablestosowane ponowne użycie skrótu (gdy występuje kolizja, próbuje innej funkcji skrótu mapować klucz do segmentu) .

Korzystanie z Hashtableklasy jest niewielkie, jeśli kierujesz reklamy na platformę .NET Framework 2.0+. Jest skutecznie dezaktualizowany przez Dictionary<TKey, TValue>.

Mehrdad Afshari
źródło
21
@ Jon- Łańcuch i powtórne omówienie jest szczegółowo omówione tutaj- msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx
RichardOD
Dziękuję wam obu. Właśnie znalazłem tę stronę, jak opublikował ją Richard ... Chciałem zapytać o Łańcuch, ale strona MSDN jest naprawdę pomocna!
Jon
6
@ Mehrdad - Nie jest dla mnie jasne, w jaki sposób rozwiązuje się kolizje, to: jeśli wiele kluczy może spowodować ten sam skrót, to w jaki sposób upewniasz się, że otrzymujesz odpowiednią wartość podczas wyszukiwania, tj. Skąd funkcja wie, który element powrót? W msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx napisano: „Zamiast przeprogramowywania w przypadku kolizji, jak ma to miejsce w przypadku klasy Hashtable, słownik po prostu łączy wszelkie kolizje na listę wiaderka. ” Czy to oznacza, że ​​podczas korzystania ze słownika kolizje nie są czymś, o co deweloper musi się martwić?
Howiecamp
6
@Howiecamp: To naprawdę niewiele różni się od Hashtable. Tabele skrótów przechowują we wpisie 3 informacje: skrót klucza, sam klucz i wartość. W przypadku elementów z jednakowym skrótem będzie musiał przejść przez listę, aby znaleźć element z równym kluczem i zwrócić jego wartość. Jest to również w dużej mierze prawdziwe Hashtable. Jako programista używający Dictionarynormalnie, nie musisz się tym martwić.
Mehrdad Afshari
@ Meehrdad Żeby było jasne, zarówno obiekty Hashtable, jak i Dictionary przechowują sam klucz, a także oba ukrywają kolizje przed deweloperem?
Howiecamp
111

Myślę, że teraz to nic dla ciebie nie znaczy. Ale tylko w celach informacyjnych dla osób zatrzymujących się w pobliżu

Test wydajności - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

Przydział pamięci:

Test wydajności użycia pamięci

Czas wykorzystany na wstawienie:

Czas wykorzystany na wstawienie

Czas na wyszukiwanie przedmiotu:

Czas na wyszukiwanie przedmiotu

Abdul Munim
źródło
Bardzo interesujące jest to, że posortowana lista ma SZYBSZE wyszukiwanie niż tablica skrótów. Myślałem, że hashtable to O (1) vs posortowana lista O (logn). Najwyraźniej haszysz jest do bani. Nigdy tego nie użyję.
John Henckel,
@JohnHenckel nie, posortowana lista ma wolniejsze wyszukiwanie. Większy współczynnik wydajności oznacza lepszą wydajność i lepsze wykorzystanie pamięci. Tak więc posortowana lista ma najlepsze wykorzystanie pamięci zgodnie z wykresami, ale zasysa inne obszary, takie jak wstawianie i wyszukiwanie.
C0DEF52
31

Różnice między tabelą skrótów a słownikiem

Słownik:

  • Słownik zwraca błąd, jeśli próbujemy znaleźć klucz, który nie istnieje.
  • Słownik szybciej niż Hashtable, ponieważ nie ma boksu i rozpakowywania.
  • Słownik jest typem ogólnym, co oznacza, że ​​możemy go używać z dowolnym typem danych.

Hashtable:

  • Hashtable zwraca null, jeśli próbujemy znaleźć klucz, który nie istnieje.
  • Hashtable wolniejszy niż słownik, ponieważ wymaga boksu i rozpakowania.
  • Hashtable nie jest typem ogólnym,
użytkownik2771704
źródło
24

Inną ważną różnicą jest to, że typ Hashtable obsługuje jednocześnie wiele czytników i jednego pisarza bez blokady, podczas gdy Słownik nie.

Steven
źródło
8
Współbieżny słownik będzie obsługiwał (.Net 4.0)
Tamilmaran,
1
Nie jestem pewien, czy rozumiem tę odpowiedź. Patrząc tutaj msdn.microsoft.com/en-us/library/... napisano: „Aby obsługiwać wielu autorów, wszystkie operacje na Hashtable muszą być wykonywane przez opakowanie zwrócone metodą Synchronized, pod warunkiem, że nie ma nici odczytujących obiekt Hashtable. „ Wydaje się, że funkcja „wielu blokad czytników bez blokady” jest dość bezużyteczna, więc wróciliśmy do konieczności blokowania całego dostępu do Hashtable, tak jak w przypadku Dictionary.
RenniePet
16

Artykuł MSDN: „ Dictionary<TKey, TValue>Klasa ma taką samą funkcjonalność jak Hashtableklasa. A Dictionary<TKey, TValue> określonego typu (innego niż Object) ma lepszą wydajność niż Hashtabledla typów wartości, ponieważ elementy Hashtablesą typu, Objecta zatem boksowanie i rozpakowywanie zwykle występują, gdy są przechowywane lub pobieranie typu wartości ".

Link: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

Juan Camilo Caro J.
źródło
11

Oba są faktycznie tej samej klasy (możesz spojrzeć na demontaż). HashTable został stworzony, zanim .Net miał generyczne. Słownik jest jednak klasą ogólną i daje duże korzyści w zakresie pisania. Nigdy nie użyłbym HashTable, ponieważ słownik nie kosztuje nic do użycia.

Adam Luter
źródło
8

Inną ważną różnicą jest to, że Hashtablejest wątkowo bezpieczny. Hashtablema wbudowane zabezpieczenie wątku wielu czytników / pojedynczych pisarzy (MR / SW), co oznacza, że HashtableJEDEN pisarz może współpracować z wieloma czytnikami bez blokowania. W przypadku Dictionarybraku bezpieczeństwa wątku, jeśli potrzebujesz bezpieczeństwa wątku, musisz wdrożyć własną synchronizację.

Aby rozwinąć dalej:

Hashtable, zapewnij pewne bezpieczeństwo wątków za pomocą właściwości Synchronized, która zwraca opakowanie bezpieczne dla wątków wokół kolekcji. Opakowanie działa poprzez zablokowanie całej kolekcji przy każdej operacji dodawania lub usuwania. Dlatego każdy wątek, który próbuje uzyskać dostęp do kolekcji, musi czekać na swoją kolej, aby przejąć jedną blokadę. Nie jest to skalowalne i może powodować znaczne obniżenie wydajności dużych kolekcji. Ponadto projekt nie jest całkowicie chroniony przed warunkami wyścigowymi.

Klasy .NET Framework 2.0 zbiórki podoba List<T>, Dictionary<TKey, TValue>itp nie zapewniają żadnej synchronizacji wątku; kod użytkownika musi zapewniać całą synchronizację, gdy elementy są dodawane lub usuwane jednocześnie w wielu wątkach. Jeśli potrzebujesz zarówno bezpieczeństwa typu, jak i bezpieczeństwa wątków, użyj równoczesnych klas kolekcji w .NET Framework. Więcej informacji tutaj.

NullReference
źródło
3

Słowniki mają tę zaletę, że są typem ogólnym, co sprawia, że ​​jest on bezpieczny i nieco szybszy z powodu braku potrzeby boksowania. Poniższa tabela porównawcza (skonstruowana przy użyciu odpowiedzi znalezionych w podobnym pytaniu SO ) ilustruje niektóre inne powody, dla których słowniki obsługują tabele skrótów (lub odwrotnie).

janeon
źródło
1

Jeśli zależy ci na czytaniu, które zawsze zwrócą obiekty w kolejności, w jakiej zostały wstawione do słownika, możesz rzucić okiem

OrdersDictionary - dostęp do wartości można uzyskać za pomocą indeksu liczb całkowitych (według kolejności, w której elementy zostały dodane) SortedDictionary - elementy są automatycznie sortowane

TOKSYNA
źródło
0

Słownik jest szybszy niż hashtable, ponieważ słownik jest silnym typem ogólnym. Hashtable działa wolniej, ponieważ przyjmuje obiekt jako typ danych, co prowadzi do boksu i rozpakowania.

jitendra mahaapatro
źródło
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx plz przeczytaj komentarze poniżej artykułu
Arvand
4
@Arvand Link uszkodzony - domena na sprzedaż.
RenniePet