Warum sind Einträge zusätzlich um in einem .Net-Wörterbuch?

Question

Ich habe gerade gesehen, dieses Verhalten, und ich bin ein wenig überrascht, es ...

Wenn ich hinzufügen, 3 oder 4 Elemente zu einem Wörterbuch, und führen Sie dann ein „For Each“ alle Schlüssel zu bekommen, sie erscheinen in der gleichen Reihenfolge ich sie hinzugefügt.

Der Grund dieser mich überrascht ist, dass ein Wörterbuch soll eine HashTable intern sein, so dass ich Dinge erwartet in beliebiger Reihenfolge zu kommen (durch den Hash-Wert des Schlüssels bestellt haben, nicht wahr?)

Was bin ich hier? Ist das ein Verhalten kann ich rechnen?

EDIT: OK, dachte ich schon von vielen der Gründe, warum diese könnte geschehen (wie die separate Liste mit Einträgen, ob dies ein Zufall ist, etc.). Meine Frage ist, hat jemand wissen , wie das wirklich funktioniert?

Answer 1

Wenn Sie .NET Reflector auf den Bibliotheken 3.5-Klasse verwenden, können Sie sehen, dass die Umsetzung der Definition tatsächlich die Elemente in einem Array gespeichert werden (die je nach Bedarf geändert wird), und Hashes Indizes in dieses Array. Wenn die Schlüssel bekommen, ignoriert vollständig die Hash-Tabelle und iteriert über die Anordnung von Elementen. Aus diesem Grunde sehen Sie das Verhalten, das Sie beschrieben haben, da neue Elemente am Ende des Arrays hinzugefügt werden. Es sieht aus wie wenn Sie wie folgt vor:

add 1
add 2
add 3
add 4
remove 2
add 5

Sie erhalten zurück 1 5 3 4, weil es leere Schlitze wieder verwendet.

Es ist wichtig zu beachten, wie viele andere haben, können Sie nicht auf dieses Verhalten in Zukunft (oder Vergangenheit) Veröffentlichungen zählen. Wenn Sie Ihr Wörterbuch sortiert werden möchten, dann gibt es eine SortedDictionary Klasse für dieser Zweck.

Answer 2

Ein Wörterbuch ruft Elemente in einem Hash-Reihenfolge. Die Tatsache, dass sie kamen in Auftrag heraus war ein totaler Zufall.

Die MSDN-Dokumentation sagt:

  

Die Reihenfolge der Schlüssel in der KeyCollection ist nicht spezifiziert, aber es ist die gleiche Reihenfolge wie die zugehörigen Werte in der Valuecollection durch die Wert Eigenschaft zurückgegeben.

Answer 3

Sie können nicht auf diesem Verhalten zählen, aber es ist nicht überraschend.

Überlegen Sie, wie Sie Schlüssel Iteration für eine einfache Hash-Tabelle implementieren würde. Sie müssten über alle Hash-Buckets zu durchlaufen, ob sie irgendetwas in ihnen hatten. Wie Sie ein kleines Datum aus einer großen Hash-Tabelle gesetzt könnte ineffizient sein.

Daher könnte es eine gute Optimierung sein eine separate, doppelte Liste der Schlüssel zu halten. Mit einem Doppelklick verknüpften Liste erhalten Sie noch konstante Zeit einfügen / löschen. (Sie würden einen Zeiger aus der Hash-Tabelle Eimer immer wieder auf dieser Liste.) Auf diese Weise durch die Liste der Schlüssel iterieren nur von der Anzahl der Einträge hängt nicht von der Anzahl der Schaufeln.

Answer 4

Ich denke, das von den alten kommt .NET 1.1 Zeiten, in denen man zwei Arten von Wörterbuch „Listdictionary“ hatte und „Hybriddictionary“. Listdictionary wurde intern als ein Wörterbuch umgesetzt geordnete Liste und wurde für „kleine Sätze von Einträgen“ empfohlen. Dann hatten Sie Hybriddictionary , das war zunächst intern als Liste organisiert, aber wenn es größer als eine konfigurierbare Schwelle wächst eine Hash-Tabelle werden würde. Dies geschieht, weil historisch korrekte Hash-basierten Wörterbücher wurden teuer angesehen. Nun wird ein Tag, der nicht viel Sinn macht, aber ich nehme an .NET nur auf Basis es neue Wörterbuch generische Klasse auf dem alten Hybriddictionary.

Hinweis : Wie auch immer, wie jemand anderes bereits erwähnt, sollten Sie nie auf dem Wörterbuch zählen für alles

Answer 5

Ein Zitat von MSDN :

  

Die Reihenfolge der Schlüssel in der   Dictionary <(Of <(TKey,   TValue>)>). KeyCollection ist   nicht spezifiziert, aber es ist die gleiche Reihenfolge   wie die zugehörigen Werte in der   Dictionary <(Of <(TKey,   TValue>)>). Valuecollection   vom Wörterbuch zurück <(Of <(TKey,   TValue>)>). Werte Eigenschaft.

Answer 6

Welche Tasten haben Sie mit in Ihrem Test hinzufügen, und in welcher Reihenfolge?

Answer 7

Ihre Eingaben können alle in dem gleichen Hash-Behälter in dem Wörterbuch sein. Jeder Eimer ist wahrscheinlich eine Liste von Einträgen auf dem heißen Stein. Dies würde die Einträge wieder kommen, um erklären.

Answer 8

Von dem, was ich weiß, soll dies kein Verhalten sein zu vertrauen. Um zu überprüfen, es schnell die gleichen Elemente verwenden und die Reihenfolge ändern, in der sie zum Wörterbuch hinzufügen. Sie werden sehen, wenn Sie sie in der Reihenfolge erhalten sie hinzugefügt wurden, oder war es nur ein Zufall.

Answer 9

Bis zu einer bestimmten Liste Größe ist es billiger, nur statt Hashing jeden Eintrag zu überprüfen. Das ist wahrscheinlich das, was passiert ist.

In

100 oder 1000 Stück und sehen, ob sie noch in derselben Reihenfolge sind.

Answer 10

Ich hasse diese Art von „by design“ Funktionalitäten. Ich denke, wenn Ihre Klasse einen solchen generischen Namen als „Dictionary“ zu geben, sollte es auch „wie allgemein erwartet“ verhalten. Zum Beispiel std :: map hält immer es Schlüsselwerte sortiert sind.

Edit: anscheinend Lösung ist SortedDictionary zu verwenden, die ähnlich wie std verhält :: map

.

Answer 11

Die Frage und viele Antworten scheinen den Zweck einer Hash-Tabelle oder Wörterbuch falsch zu verstehen. Diese Datenstrukturen haben keine bestimmten Verhaltensweisen in Bezug auf die Aufzählung der Werte (oder in der Tat der Schlüssel) der Elemente in der Datenstruktur enthalten.

Der Zweck eines Wörterbuchs oder Hash-Tabelle ist in der Lage sein, um effizient Lookup einen bestimmten Wert ein bekannter Schlüssel gegeben. Die interne Umsetzung eines Wörterbuchs oder Hash-Tabelle sollte für diese Effizienz in Lookups bieten, muss aber kein spezifisches Verhalten in Bezug auf Aufzählungen liefern oder „für jeden“ Typ Iterationen auf den Werten oder Tasten.

Kurz gesagt, die interne Datenstruktur kann diese Werte in irgendeiner Art und Weise speichern und zählen, dass sie wünscht, einschließlich der Reihenfolge, in sie eingefügt wurden.