Dlaczego słownik jest lepszy niż Hashtable w C #?

W większości języków programowania preferowane są słowniki zamiast tablic skrótów. Jakie są tego przyczyny?

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 zamiast Hashtableklasy?”, To jest łatwa odpowiedź: Dictionary<TKey, TValue>jest to rodzaj ogólny, Hashtablenie jest. Oznacza to, że zyskujesz bezpieczeństwo typu Dictionary<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 na Hashtable, jak można powiedzieć z tego komentarza w jego kodzie źródłowym:

Słownik ogólny został skopiowany ze źródła Hashtable

Źródło

Dictionary<<< >>> Hashtableróżnice:

• Ogólne <<< >>> Nie ogólne
• Potrzebuje własnej synchronizacji wątków <<< >>> Oferuje bezpieczną wersję wątkuSynchronized() metodą
• Element wymieniony: KeyValuePair<<< >>> Element wymieniony:DictionaryEntry
• Nowsze (> .NET 2.0 ) <<< >>> Starsze (od .NET 1.0 )
• jest w System.Collections.Generic <<< >>> znajduje się w System.Collections
• Żądanie na nieistniejący klucz zgłasza wyjątek <<< >>> Żądanie na nieistniejący klucz zwraca null
• potencjalnie nieco szybciej dla typów wartości <<< >>> nieco wolniej (wymaga boksu / rozpakowania) dla typów wartości

Dictionary/ Hashtablepodobieństwa:

• Oba są wewnętrznie hashtables == szybki dostęp do danych wielu pozycji według klucza
• Oba potrzebują niezmiennych i unikalnych kluczy
• Klucze obu wymagają własnej GetHashCode()metody

Podobne 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 automatycznie
• StringDictionary- silnie napisane i zoptymalizowane pod kątem łańcuchów

Ponieważ Dictionaryjest to klasa ogólna ( Dictionary<TKey, TValue>), więc dostęp do jej zawartości jest bezpieczny dla typu (tzn. Nie trzeba rzutować z Object, tak jak w przypadku a Hashtable).

Porównać

var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];

do

var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;

Jednak Dictionaryjest wewnętrznie implementowany jako tablica skrótów, więc technicznie działa tak samo.

FYI: W .NET, Hashtablewątek jest bezpieczny do użytku przez wiele wątków czytnika i jeden wątek do pisania, podczas gdy w Dictionarypublicznych 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.

W .NET różnica między Dictionary<,>i HashTablepolega 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).

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 Dictionaryklasie, 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).

Collectionsi Genericssą przydatne do obsługi grupy obiektów. W .NET wszystkie obiekty kolekcji znajdują się w interfejsie IEnumerable, który z kolei ma ArrayList(Index-Value))& HashTable(Key-Value). Po .NET Framework 2.0, ArrayListi HashTablezostały zastąpione przez List& Dictionary. Teraz Arraylist& HashTablenie są już używane w dzisiejszych projektach.

Różnica między HashTable& Dictionary, Dictionaryjest ogólna, gdy Hastablenie jest ogólna. Możemy dodać dowolny typ obiektu HashTable, ale podczas pobierania musimy rzucić go na wymagany typ. Więc nie jest to bezpieczne. Ale dictionary, 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

class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}

Słownik,

class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}

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 Keysi Valuesjest 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.

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 .

Rehashing działa w następujący sposób: istnieje zestaw różnych funkcji skrótu, H ₁ ... H _n , a podczas wstawiania lub pobierania elementu z tabeli skrótów początkowo używana jest funkcja skrótu H ₁ . Jeśli ten prowadzi do kolizji, H ₂ jest wypróbowany zamiast, i dalej aż do H _n razie potrzeby.

Słownik wykorzystuje technikę zwaną łańcuchem .

W przypadku powtórzenia skrótu w przypadku kolizji skrót jest obliczany ponownie i wypróbowywana jest nowa szczelina odpowiadająca skrótowi. W przypadku łańcuchów wykorzystywana jest jednak wtórna struktura danych, która przechowuje wszelkie kolizje . W szczególności każde miejsce w Słowniku ma tablicę elementów, które są mapowane do tego segmentu. W przypadku kolizji element kolidujący jest dodawany do listy wiadra.

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ść, aby nullsymulować bezpieczną tablicę skrótów, powinieneś rozważyć przejście na HashSet<T>.

HashtableJest luźno wpisane struktura danych, dzięki czemu można dodać klucze i wartości dowolnego typu do Hashtable. DictionaryKlasa jest typu bezpieczne Hashtablewdrożenie, a klucze i wartości są mocno wpisane. Podczas tworzenia Dictionaryinstancji należy określić typy danych zarówno dla klucza, jak i wartości.

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ę.

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.

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

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:

Hashtable zapewnia pewne bezpieczeństwo wątków poprzez Synchronizedwłaściwość, która zwraca bezpieczne opakowanie do 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 kolekcji .NET Framework 2.0, takie jak List<T>, Dictionary<TKey, TValue>itp., Nie zapewniają synchronizacji wątków; kod użytkownika musi zapewniać całą synchronizację, gdy elementy są dodawane lub usuwane jednocześnie w wielu wątkach

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.

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.

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 podobnie Dictionary<string>akceptuje tylko łańcuchy.

Lepiej więc używać Dictionary<>zamiast HashTable.

W większości języków programowania preferowane są słowniki zamiast tablic skrótów

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.

Zgodnie z tym, co widzę za pomocą .NET Reflector :

[Serializable, ComVisible(true)]
public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable
{
    // Fields
    private Hashtable hashtable;

    // Methods
    protected DictionaryBase();
    public void Clear();
.
.
.
}
Take note of these lines
// Fields
private Hashtable hashtable;

Możemy więc być pewni, że DictionaryBase wewnętrznie używa HashTable.