.NET HashTable Vs Dictionary - Kann das Wörterbuch so schnell sein?

276

Ich versuche herauszufinden, wann und warum ein Wörterbuch oder eine HashTable verwendet werden soll. Ich habe hier ein bisschen gesucht und Leute gefunden, die über die allgemeinen Vorteile des Wörterbuchs sprechen, denen ich voll und ganz zustimme, was den Box- und Unboxing-Vorteil für einen leichten Leistungsgewinn führt.

Aber ich habe auch gelesen, dass das Wörterbuch die Objekte nicht immer in der Reihenfolge zurückgibt, in der sie eingefügt wurden, sondern sortiert ist. Wo als HashTable wird. Soweit ich weiß, führt dies dazu, dass die HashTable in einigen Situationen viel schneller ist.

Meine Frage ist wirklich, wie könnten diese Situationen sein? Bin ich in meinen obigen Annahmen einfach falsch? Welche Situationen könnten Sie verwenden, um eine über die andere zu wählen (ja, die letzte ist etwas mehrdeutig).

Jon
quelle
5
Ich werde das nicht positiv bewerten, aber dein Karma ist 7.777 und ich möchte nicht der Typ sein, der das für dich vermasselt.
CaptainMarvel

Antworten:

298

System.Collections.Generic.Dictionary<TKey, TValue>und System.Collections.HashtableKlassen pflegen beide intern eine Hash-Tabellendatenstruktur. Keiner von ihnen garantiert die Beibehaltung der Reihenfolge der Artikel.

Abgesehen von Box- / Unboxing-Problemen sollten sie die meiste Zeit eine sehr ähnliche Leistung haben.

Der primäre strukturelle Unterschied zwischen ihnen ist , dass Dictionaryberuht auf Verkettungs zu lösen Kollisionen während (eine Liste von Elementen für jede Hashtabelle bucket Aufrechterhaltung) HashtableVerwendungen Wiederkäuen für eine Kollisionsauflösung (wenn eine Kollision auftritt, versucht eine andere Hash - Funktion den Schlüssel zu einem Eimer zur Karte) .

Die Verwendung von HashtableKlassen bietet wenig Vorteile, wenn Sie auf .NET Framework 2.0+ abzielen. Es ist effektiv obsolet von Dictionary<TKey, TValue>.

Mehrdad Afshari
quelle
21
@ Jon- Das Verketten und Wiederaufwärmen wird hier ausführlich besprochen
msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx
Danke euch beiden. Ich habe diese Seite gerade gefunden, als Richard sie gepostet hat ... Ich wollte nach Chaining fragen, aber die MSDN-Site ist tatsächlich hilfreich!
Jon
6
@Mehrdad - Was mir nicht klar ist, wie Kollisionen gelöst werden, ist Folgendes: Wenn mehrere Schlüssel zu demselben Hash führen können, wie stellen Sie dann sicher, dass Sie den richtigen Wert für Suchvorgänge erhalten, dh woher weiß die Funktion, welches Element zu verwenden ist Rückkehr? In msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx heißt es: "Anstatt im Falle einer Kollision erneut zu testen , wie dies bei der Hashtable-Klasse der Fall ist, verkettet das Wörterbuch einfach alle Kollisionen auf die Liste des Eimers. " Bedeutet dies, dass sich der Entwickler bei der Verwendung von Dictionary keine Sorgen um Kollisionen machen muss?
Howiecamp
6
@ Howiecamp: Das ist nicht wirklich viel anders als Hashtable. In Hash-Tabellen werden 3 Informationen in einem Eintrag gespeichert: Schlüssel-Hash, Schlüssel selbst und der Wert. Bei Elementen mit gleichem Hash muss die Liste durchlaufen werden, um das Element mit gleichem Schlüssel zu finden und seinen Wert zurückzugeben. Dies gilt auch für Hashtable. Als Entwickler, der ein Dictionarynormales System verwendet, müssen Sie sich darüber keine Sorgen machen.
Mehrdad Afshari
@Mehrdad Um ganz klar zu sein, speichern sowohl das Hashtable- als auch das Dictionary-Objekt den Schlüssel selbst und beide verbergen auch Kollisionen vor dem Entwickler?
Howiecamp
111

Ich denke, es bedeutet dir jetzt nichts. Aber nur als Referenz für Leute, die vorbeischauen

Leistungstest - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

Speicherzuweisung:

Leistungstest für die Speichernutzung

Zeit zum Einfügen:

Zeit zum Einfügen

Zeit für die Suche nach einem Artikel:

Zeit für die Suche nach einem Artikel

Abdul Munim
quelle
Sehr interessant, dass die sortierte Liste SCHNELLER als die Hashtabelle ist. Ich dachte, Hashtabelle ist O (1) gegen sortierte Liste O (logn). Anscheinend ist Hashtable scheiße. Ich werde es nie benutzen.
John Henckel
@ JohnHenckel nein, sortierte Liste hat langsamere Suche. Ein größerer Leistungskoeffizient bedeutet eine bessere Leistung und eine bessere Speichernutzung. Die sortierte Liste hat also die beste Speichernutzung gemäß den Diagrammen, ist jedoch in anderen Bereichen wie dem Einfügen und Nachschlagen schlecht.
C0DEF52
31

Unterschiede zwischen Hashtable und Dictionary

Wörterbuch:

  • Dictionary gibt einen Fehler zurück, wenn wir versuchen, einen Schlüssel zu finden, der nicht existiert.
  • Wörterbuch schneller als eine Hashtable, da es kein Boxen und Unboxing gibt.
  • Dictionary ist ein generischer Typ, dh wir können ihn mit jedem Datentyp verwenden.

Hash-tabelle:

  • Hashtable gibt null zurück, wenn wir versuchen, einen Schlüssel zu finden, der nicht existiert.
  • Hashtable langsamer als Wörterbuch, da Boxen und Unboxing erforderlich sind.
  • Hashtable ist kein generischer Typ.
user2771704
quelle
24

Ein weiterer wichtiger Unterschied besteht darin, dass der Hashtable-Typ mehrere Leser und einen einzelnen Schreiber gleichzeitig sperrfrei unterstützt, Dictionary jedoch nicht.

Steven
quelle
8
Concurrent Dictionary unterstützt (.Net 4.0)
Tamilmaran
1
Ich bin mir nicht sicher, ob ich diese Antwort verstehe. Unter msdn.microsoft.com/en-us/library/… heißt es: "Um mehrere Writer zu unterstützen, müssen alle Vorgänge auf der Hashtable über den von der Synchronized-Methode zurückgegebenen Wrapper ausgeführt werden, vorausgesetzt, es gibt keine Threads, die das Hashtable-Objekt lesen." "" Das scheint die Funktion "Mehrfachleser ohne Sperren" ziemlich nutzlos zu machen. Dann müssen wir wieder den gesamten Zugriff auf die Hashtabelle sperren, genau wie bei Dictionary.
RenniePet
16

MSDN-Artikel: "Die Dictionary<TKey, TValue>Klasse hat die gleiche Funktionalität wie die HashtableKlasse. A Dictionary<TKey, TValue> eines bestimmten Typs (außer Object) hat eine bessere Leistung als a Hashtablefür Werttypen, da die Elemente von Hashtablevom Typ sind Objectund daher Boxing und Unboxing normalerweise beim Speichern oder auftreten Abrufen eines Werttyps ".

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

Juan Camilo Caro J.
quelle
11

Beide sind praktisch dieselbe Klasse (Sie können sich die Demontage ansehen). HashTable wurde zuerst erstellt, bevor .Net Generika hatte. Dictionary ist jedoch eine generische Klasse und bietet Ihnen starke Tippvorteile. Ich würde HashTable niemals verwenden, da die Verwendung von Dictionary nichts kostet.

Adam Luter
quelle
8

Ein weiterer wichtiger Unterschied ist, dass HashtableThread-sicher ist. Hashtablehat eine eingebaute Thread-Sicherheit für mehrere Leser / einzelne Schreiber (MR / SW), was bedeutet, Hashtabledass EIN Schreiber zusammen mit mehreren Lesern ohne Sperren verwendet werden kann. Im Falle der Dictionaryes keinen Thread - Sicherheit, wenn Sie Sicherheitsfaden müssen Sie Ihre eigene Synchronisierung implementieren müssen.

Um weiter auszuarbeiten:

HashtableStellen Sie durch die Synchronized-Eigenschaft, die einen thread-sicheren Wrapper um die Sammlung zurückgibt, eine gewisse Thread-Sicherheit bereit. Der Wrapper sperrt die gesamte Sammlung bei jedem Hinzufügen oder Entfernen. Daher muss jeder Thread, der versucht, auf die Sammlung zuzugreifen, warten, bis er an der Reihe ist, um die eine Sperre zu erhalten. Dies ist nicht skalierbar und kann bei großen Sammlungen zu erheblichen Leistungseinbußen führen. Auch das Design ist nicht vollständig vor Rennbedingungen geschützt.

Die .NET Framework 2.0 Collection - Klassen mögen List<T>, Dictionary<TKey, TValue>usw. bieten keine Thread - Synchronisation; Der Benutzercode muss die gesamte Synchronisierung bereitstellen, wenn Elemente in mehreren Threads gleichzeitig hinzugefügt oder entfernt werden. Wenn Sie sowohl Typensicherheit als auch Thread-Sicherheit benötigen, verwenden Sie in .NET Framework gleichzeitige Sammlungsklassen. Lesen Sie hier weiter.

NullReference
quelle
3

Wörterbücher haben den Vorteil, dass sie ein generischer Typ sind, der sie typsicher und etwas schneller macht, da kein Boxen erforderlich ist. Die folgende Vergleichstabelle (erstellt anhand der Antworten in einem ähnlichen SO- Fragenbeitrag ) zeigt einige der anderen Gründe, die Wörterbücher über Hash-Tabellen unterstützen (oder umgekehrt).

Janeon
quelle
1

Wenn Sie sich für das Lesen interessieren, das die Objekte immer in der Reihenfolge zurückgibt, in der sie in ein Wörterbuch eingefügt wurden, können Sie sich das ansehen

OrderedDictionary - Auf Werte kann über einen ganzzahligen Index zugegriffen werden (nach der Reihenfolge, in der Elemente hinzugefügt wurden). SortedDictionary - Elemente werden automatisch sortiert

ToXinE
quelle
0

Das Wörterbuch ist schneller als die Hashtabelle, da das Wörterbuch ein allgemein starker Typ ist. Hashtable ist langsamer, da es Objekte als Datentyp verwendet, was zum Ein- und Auspacken führt.

Jitendra Mahaapatro
quelle
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx Bitte lesen Sie die Kommentare unter dem Artikel
Arvand
4
@Arvand Link defekt - Domain zu verkaufen.
RenniePet