Die Reihenfolge der Elemente im Wörterbuch

107

Meine Frage betrifft die Aufzählung von Wörterbuchelementen

// Dictionary definition
private Dictionary<string, string> _Dictionary = new Dictionary<string, string>();

// add values using add

_Dictionary.Add("orange", "1");
_Dictionary.Add("apple", "4");
_Dictionary.Add("cucumber", "6");

// add values using []

_Dictionary["banana"] = 7;
_Dictionary["pineapple"] = 7;

// Now lets see how elements are returned by IEnumerator
foreach (KeyValuePair<string, string> kvp in _Dictionary)
{
  Trace.Write(String.Format("{0}={1}", kvp.Key, kvp.Value));
}

In welcher Reihenfolge werden die Elemente aufgelistet? Kann ich die alphabetische Reihenfolge erzwingen?

Captain Comic
quelle

Antworten:

125

Die Reihenfolge der Elemente in einem Wörterbuch ist nicht deterministisch. Der Ordnungsbegriff ist für Hashtabellen einfach nicht definiert. Verlassen Sie sich also nicht auf die Aufzählung in derselben Reihenfolge, in der Elemente zum Wörterbuch hinzugefügt wurden. Das ist nicht garantiert.

Zitat aus dem Dokument :

Zum Zwecke der Aufzählung wird jedes Element im Wörterbuch als KeyValuePair<TKey, TValue>Struktur behandelt , die einen Wert und seinen Schlüssel darstellt. Die Reihenfolge, in der die Artikel zurückgegeben werden, ist undefiniert.

Darin Dimitrov
quelle
1
Aber es gibt OrderedDictionary .
Peter Mortensen
28

Wenn Sie möchten, dass die Elemente geordnet werden, verwenden Sie ein OrderedDictionary . Ein gewöhnliches hastable / Wörterbuch wird nur in gewissem Sinne des Speicherlayouts bestellt.

Mitch Wheat
quelle
10
OrderedDictionary ist in den meisten Fällen falsch. Es ist weder nach Schlüssel noch nach Wert geordnet, sondern nach einem internen Index. SortedDictionary ist dasjenige, das so angeordnet ist, dass der Benutzer es manipulieren kann (Standardschlüssel)
Offler
2
Die Frage bezieht sich auf die Reihenfolge in alphabetischer Reihenfolge (vorausgesetzt, der Fragesteller spricht über den Schlüssel). Ein geordnetes Wörterbuch spuckt, wenn ich die Dokumentation richtig verstehe, die Elemente in der Reihenfolge aus, in der sie eingefügt werden, dh nicht alphabetisch, sondern unter Verwendung des internen Index. Ein SortedDictionary passt wahrscheinlich am besten zur Frage des Benutzers.
mattpm
28

Sie können immer dafür verwenden SortedDictionary. Beachten Sie, dass das Wörterbuch standardmäßig nach Schlüssel sortiert ist, sofern kein Vergleicher angegeben wurde.

Ich bin skeptisch in Bezug auf die Verwendung OrderedDictionaryfür das, was Sie wollen, da die Dokumentation Folgendes besagt:

Die Elemente eines OrderedDictionary werden im Gegensatz zu den Elementen einer SortedDictionary-Klasse nicht nach dem Schlüssel sortiert.

Adriano Carneiro
quelle
Es ist wichtig zu beachten, dass SortedDictionary<K,V>es als binärer Suchbaum implementiert ist, der seinen Operationen eine andere zeitliche und räumliche Komplexität verleiht als der auf Hashtabellen basierenden Dictionary<K,V>. Wenn Benutzer eine O(1)Hashtabellenstruktur zum Einfügen / Löschen benötigen und auch Elemente in Schlüsselreihenfolge durchlaufen möchten, sollten sie dict.Keys.OrderBy( k => k ).Select( k => dict[k] )stattdessen (auf Kosten von O(n)Platz und O( n log n )Zeit) für die OrderBy()(die die gesamte Schlüsselsammlung in einer internen Liste puffern muss) vorgehen ).
Dai
12

Die Elemente werden in der Reihenfolge zurückgegeben, in der sie physisch im Wörterbuch gespeichert sind. Dies hängt vom Hash-Code und der Reihenfolge ab, in der die Elemente hinzugefügt wurden. Daher erscheint die Reihenfolge zufällig, und wenn sich die Implementierungen ändern, sollten Sie sich niemals darauf verlassen, dass die Reihenfolge gleich bleibt.

Sie können die Artikel bestellen, wenn Sie sie auflisten:

foreach (KeyValuePair<string, string> kvp in _Dictionary.OrderBy(k => k.Value)) {
  ...
}

In Framework 2.0 müssten Sie zuerst die Elemente in eine Liste aufnehmen, um sie zu sortieren:

List<KeyValuePair<string, string>> items = new List<KeyValuePair<string, string>>(_Dictionary);
items.Sort(delegate(KeyValuePair<string, string> x, KeyValuePair<string, string> y) { return x.Value.CompareTo(y.Value); });
foreach (KeyValuePair<string,string> kvp in items) {
  ...
}
Guffa
quelle
11

Für ein bestelltes Wörterbuch:

 var _OrderedDictionary = new System.Collections.Specialized.OrderedDictionary();

_OrderedDictionary.Add("testKey1", "testValue1");
_OrderedDictionary.Add("testKey2", "testValue2");
_OrderedDictionary.Add("testKey3", "testValue3");

var k = _OrderedDictionary.Keys.GetEnumerator();
var v = _OrderedDictionary.Values.GetEnumerator();

while (k.MoveNext() && v.MoveNext()) {
    var key = k.Current; var value = v.Current;
}

Artikel werden in der Reihenfolge zurückgegeben, in der sie hinzugefügt wurden.

Barton
quelle
5

Assoziative Arrays (auch bekannt als Hash-Tabellen) sind ungeordnet, was bedeutet, dass die Elemente auf jede erdenkliche Weise geordnet werden können.

Sie können jedoch die Array-Schlüssel (nur die Schlüssel) abrufen, diese alphabetisch (über eine Sortierfunktion) sortieren und dann daran arbeiten.

Ich kann Ihnen kein C # -Beispiel geben, da ich die Sprache nicht kenne, aber dies sollte ausreichen, damit Sie selbst weitermachen können.

Tim Čas
quelle