W większości języków programowania preferowane są słowniki zamiast tablic skrótów. Jakie są tego przyczyny?
c#
.net
vb.net
data-structures
Nakul Chaudhary
źródło
źródło
Dictionary
to implementacjaHashtable
.HashTable
. nazywana jest nieogólna tablica skrótu C # . Kiedy dodali ogólne do języka, nazwali wersję ogólnąDictionary
. Oba są tabelami skrótów.Odpowiedzi:
Pod względem wartości Słownik jest (koncepcyjnie) tabelą skrótów.
Jeśli miałeś na myśli „dlaczego używamy
Dictionary<TKey, TValue>
klasy zamiastHashtable
klasy?”, To jest łatwa odpowiedź:Dictionary<TKey, TValue>
jest to rodzaj ogólny,Hashtable
nie jest. Oznacza to, że zyskujesz bezpieczeństwo typuDictionary<TKey, TValue>
, ponieważ nie możesz wstawić do niego żadnego losowego obiektu i nie musisz rzutować wartości, które bierzesz.Co ciekawe,
Dictionary<TKey, TValue>
implementacja w .NET Framework oparta jest naHashtable
, jak można powiedzieć z tego komentarza w jego kodzie źródłowym:Źródło
źródło
HashTable
(klasa), jak iDictionary
(klasa) są tablicami skrótu (koncepcja), ale aHashTable
nie jestDictionary
ani nie jestDictionary
aHashTable
. Są one używane w bardzo podobnych stylach iDictionary<Object,Object>
mogą działać w taki sam nietypowy sposób jak aHashTable
, ale nie dzielą bezpośrednio żadnego kodu (chociaż części mogą być implementowane w bardzo podobny sposób).Dictionary
<<< >>>Hashtable
różnice:Synchronized()
metodąKeyValuePair
<<< >>> Element wymieniony:DictionaryEntry
Dictionary
/Hashtable
podobieństwa:GetHashCode()
metodyPodobne kolekcje .NET (kandydaci do użycia zamiast Dictionary i Hashtable):
ConcurrentDictionary
- wątek bezpieczny (można bezpiecznie uzyskać dostęp z kilku wątków jednocześnie)HybridDictionary
- zoptymalizowana wydajność (dla kilku przedmiotów, a także dla wielu przedmiotów)OrderedDictionary
- dostęp do wartości można uzyskać za pomocą indeksu int (według kolejności, w której elementy zostały dodane)SortedDictionary
- pozycje sortowane automatycznieStringDictionary
- silnie napisane i zoptymalizowane pod kątem łańcuchówźródło
StringDictionary
... btwStringDictionary
to nie to samo, coDictionary<string, string>
przy użyciu domyślnego konstruktora.Ponieważ
Dictionary
jest to klasa ogólna (Dictionary<TKey, TValue>
), więc dostęp do jej zawartości jest bezpieczny dla typu (tzn. Nie trzeba rzutować zObject
, tak jak w przypadku aHashtable
).Porównać
do
Jednak
Dictionary
jest wewnętrznie implementowany jako tablica skrótów, więc technicznie działa tak samo.źródło
FYI: W .NET,
Hashtable
wątek jest bezpieczny do użytku przez wiele wątków czytnika i jeden wątek do pisania, podczas gdy wDictionary
publicznych elementach statycznych jest wątek bezpieczny, ale nie można zagwarantować, że jakikolwiek element instancji jest bezpieczny.Z tego powodu musieliśmy zmienić wszystkie nasze słowniki
Hashtable
.źródło
ConcurrentDictionary
klasę, w której zaimplementowano wszystkie metody publiczne / chronione, aby zapewnić bezpieczeństwo wątków. Jeśli nie potrzebujesz obsługi starszych platform, pozwoli to zastąpićHashtable
wielowątkowy kod: msdn.microsoft.com/en-us/library/dd287191.aspxW .NET różnica między
Dictionary<,>
iHashTable
polega przede wszystkim na tym, że ten pierwszy jest typem ogólnym, więc zyskujesz wszystkie zalety generyczne w zakresie statycznego sprawdzania typu (i zmniejszonego boksu, ale nie jest to tak duże, jak ludzie myślą w warunki wydajności - jednak boks ma określony koszt pamięci).źródło
Ludzie mówią, że słownik jest taki sam jak tabela skrótów.
To niekoniecznie jest prawdą. Tabela skrótów jest jednym ze sposobów implementacji słownika. W tym typowy i może być domyślny w .NET w
Dictionary
klasie, ale z definicji nie jest jedyny.Równie dobrze można zaimplementować słownik za pomocą połączonej listy lub drzewa wyszukiwania, po prostu nie byłby on tak wydajny (dla niektórych wskaźników wydajności).
źródło
Dictionary<K,V>
.IDictionary<K,V>
może być cokolwiek :)Collections
iGenerics
są przydatne do obsługi grupy obiektów. W .NET wszystkie obiekty kolekcji znajdują się w interfejsieIEnumerable
, który z kolei maArrayList(Index-Value))
&HashTable(Key-Value)
. Po .NET Framework 2.0,ArrayList
iHashTable
zostały zastąpione przezList
&Dictionary
. TerazArraylist
&HashTable
nie są już używane w dzisiejszych projektach.Różnica między
HashTable
&Dictionary
,Dictionary
jest ogólna, gdyHastable
nie jest ogólna. Możemy dodać dowolny typ obiektuHashTable
, ale podczas pobierania musimy rzucić go na wymagany typ. Więc nie jest to bezpieczne. Aledictionary
, deklarując się, możemy określić typ klucza i wartości, więc nie ma potrzeby rzucania podczas pobierania.Spójrzmy na przykład:
HashTable
Słownik,
źródło
Słownik:
Zwraca / zgłasza wyjątek, jeśli próbujemy znaleźć klucz, który nie istnieje.
Jest szybszy niż Hashtable, ponieważ nie ma boksu i rozpakowywania.
Tylko publiczne elementy statyczne są bezpieczne dla wątków.
Słownik jest typem ogólnym, co oznacza, że możemy go używać z dowolnym typem danych (podczas tworzenia należy określić typy danych zarówno dla kluczy, jak i wartości).
Przykład:
Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();
Dictionay jest bezpieczną implementacją Hashtable
Keys
iValues
jest mocno typowany.Hashtable:
Zwraca null, jeśli próbujemy znaleźć klucz, który nie istnieje.
Jest wolniejszy niż słownik, ponieważ wymaga boksu i rozpakowania.
Wszyscy członkowie Hashtable są bezpieczni dla wątków,
Hashtable nie jest typem ogólnym,
Hashtable to luźno wpisana struktura danych, możemy dodawać klucze i wartości dowolnego typu.
źródło
Dictionary.TryGetValue
Wszechstronne badania struktur danych przy użyciu C # artykułu na MSDN stwierdza, że istnieje również różnica w strategii rozdzielczości kolizji :
Klasa Hashtable wykorzystuje technikę nazywaną powtórnym przetwarzaniem .
Słownik wykorzystuje technikę zwaną łańcuchem .
źródło
Od .NET Framework 3.5 istnieje również taki,
HashSet<T>
który zapewnia wszystkie zalety,Dictionary<TKey, TValue>
jeśli potrzebujesz tylko kluczy i żadnych wartości.Więc jeśli używasz a
Dictionary<MyType, object>
i zawsze ustawiasz wartość, abynull
symulować bezpieczną tablicę skrótów, powinieneś rozważyć przejście naHashSet<T>
.źródło
Hashtable
Jest luźno wpisane struktura danych, dzięki czemu można dodać klucze i wartości dowolnego typu doHashtable
.Dictionary
Klasa jest typu bezpieczneHashtable
wdrożenie, a klucze i wartości są mocno wpisane. Podczas tworzeniaDictionary
instancji należy określić typy danych zarówno dla klucza, jak i wartości.źródło
Zauważ, że MSDN mówi: "Słownik <(z <(TKey, TValue>)>) Klasa jest zaimplementowany jako tabeli mieszania ", a nie "Dictionary <(z <(TKey, TValue>)>) Klasa jest zaimplementowany jako HashTable "
Słownik NIE jest zaimplementowany jako HashTable, ale jest implementowany zgodnie z koncepcją tabeli mieszającej. Implementacja nie jest powiązana z klasą HashTable z powodu użycia Generics, chociaż wewnętrznie Microsoft mógł użyć tego samego kodu i zastąpić symbole typu Object TKey i TValue.
W .NET 1.0 Generics nie istniał; to tutaj początkowo HashTable i ArrayList rozpoczęły się.
źródło
HashTable:
Klucz / wartość zostaną przekonwertowane na typ obiektu (boks) podczas przechowywania w stercie.
Klucz / wartość należy przekonwertować na pożądany typ podczas odczytu ze sterty.
Te operacje są bardzo kosztowne. Musimy unikać boksowania / rozpakowywania w jak największym stopniu.
Słownik: Ogólny wariant HashTable.
Bez boksowania / rozpakowywania. Nie wymaga konwersji.
źródło
Obiekt Hashtable składa się z segmentów zawierających elementy kolekcji. Wiadro to wirtualna podgrupa elementów w Hashtable, dzięki czemu wyszukiwanie i wyszukiwanie jest łatwiejsze i szybsze niż w większości kolekcji .
Klasa Dictionary ma taką samą funkcjonalność jak klasa Hashtable. Słownik określonego typu (inny niż Object) ma lepszą wydajność niż Hashtable dla typów wartości, ponieważ elementy Hashtable są typu Object, a zatem boksowanie i rozpakowywanie zwykle występuje podczas przechowywania lub pobierania typu wartości.
Do dalszej lektury: Hashtable i typy zbiorów słownikowych
źródło
Inną ważną różnicą jest to, że Hashtable jest bezpieczny dla wątków. Hashtable ma wbudowane zabezpieczenie wątku wielu czytników / pojedynczych pisarzy (MR / SW), co oznacza, że Hashtable umożliwia JEDEN pisarzowi razem z wieloma czytnikami bez blokowania.
W przypadku słownika nie ma bezpieczeństwa wątków; jeśli potrzebujesz bezpieczeństwa wątków, musisz wdrożyć własną synchronizację.
Aby rozwinąć dalej:
Jeśli potrzebujesz bezpieczeństwa typu oraz bezpieczeństwa wątków, użyj współbieżnych klas kolekcji w .NET Framework. Więcej informacji tutaj .
Dodatkową różnicą jest to, że po dodaniu wielu pozycji do słownika zachowana jest kolejność dodawania pozycji. Gdy odzyskamy elementy ze słownika, uzyskamy rekordy w tej samej kolejności, w jakiej je wstawiliśmy. Podczas gdy Hashtable nie zachowuje kolejności wstawiania.
źródło
Hashset
gwarancje bezpieczeństwa wątku MR / SW w scenariuszach użytkowania , które nie wymagają usunięcia . Wydaje mi się, że mogła być w pełni bezpieczna dla MR / SW, ale bezpieczne usuwanie usunięć znacznie zwiększa koszt bezpieczeństwa MR / SW. Chociaż projektDictionary
mógł zaoferować bezpieczeństwo MR / SW przy minimalnych kosztach w scenariuszach bez usuwania, myślę, że MS chciało uniknąć traktowania scenariuszy bez usuwania jako „specjalnych”.Jeszcze jedną różnicą, którą mogę zrozumieć, jest:
Nie możemy używać słownika <KT, VT> (ogólne) z usługami internetowymi. Powodem jest to, że żaden standard usług internetowych nie obsługuje standardu generycznego.
źródło
Dictionary<>
jest typem ogólnym, więc jest bezpieczny.Możesz wstawić dowolny typ wartości do HashTable, co może czasami generować wyjątek. Ale
Dictionary<int>
akceptuje tylko wartości całkowite i podobnieDictionary<string>
akceptuje tylko łańcuchy.Lepiej więc używać
Dictionary<>
zamiastHashTable
.źródło
Nie sądzę, że jest to koniecznie prawda, większość języków ma jeden lub drugi, w zależności od preferowanej terminologii .
Jednak w C # oczywistym powodem (dla mnie) jest to, że C # HashTables i inni członkowie przestrzeni nazw System.Collections są w dużej mierze przestarzałe. Byli obecni w c # V1.1. Zostały one zastąpione z C # 2.0 przez klasy Generic w przestrzeni nazw System.Collections.Generic.
źródło
Zgodnie z tym, co widzę za pomocą .NET Reflector :
Możemy więc być pewni, że DictionaryBase wewnętrznie używa HashTable.
źródło