Die Go-Programmiersprachenspezifikation lautet:
3. Die Iterationsreihenfolge über Maps ist nicht angegeben. [...]
Das ist zu erwarten, da ein Kartentyp als Hash-Tabelle oder als Suchbaum oder als eine andere Datenstruktur implementiert werden kann. Aber wie ist map tatsächlich in Go implementiert?
Anders gesagt, was bestimmt die Iterationsreihenfolge der Schlüssel in
%Vor% Ich habe mich darüber gewundert, nachdem ich gesehen habe, dass eine Karte mit string keys anscheinend do eine bestimmte Iterationsreihenfolge hat. Ein Programm wie
druckt Folgendes auf meinem Computer aus:
%Vor%ungeachtet des Anzeigenauftrags.
Das äquivalente Programm mit einer map[byte]byte -Karte druckt die Schlüssel auch in einer gemischten Reihenfolge, aber hier hängt die Schlüsselreihenfolge von der Reihenfolge ab.
Wie ist das alles implementiert? Ist das map speziell auf Ganzzahlen und Strings spezialisiert?
Karte ist in Go als Hashmapp implementiert.
Die Go-Laufzeit verwendet eine Common-Hashmap-Implementierung, die in C implementiert ist. Die einzigen Implementierungsunterschiede zwischen map[string]T und map[byte]T sind: Hash-Funktion, Äquivalenzfunktion und Kopierfunktion.
Im Gegensatz zu (einigen) C ++ - Maps sind Go-Maps nicht vollständig auf ganze Zahlen und Strings spezialisiert.
In Go release.r60 ist die Iterationsreihenfolge unabhängig von der Einfügereihenfolge, solange keine Schlüsselkollisionen auftreten. Wenn Kollisionen auftreten, wird die Reihenfolge der Iterationen von der Reihenfolge der Einfügungen beeinflusst. Dies gilt unabhängig vom Schlüsseltyp. Es gibt keinen Unterschied zwischen Schlüsseln vom Typ string und Schlüsseln vom Typ byte in diesem Zusammenhang, so dass es nur ein Zufall ist, dass Ihr Programm die Zeichenfolgenschlüssel immer in der gleichen Reihenfolge druckte. Die Iterationsreihenfolge ist immer gleich, es sei denn, die Map wird geändert.
In der neuesten Veröffentlichung Go weekly (und in Go1 , die voraussichtlich diesen Monat veröffentlicht wird) ist die Iterationsreihenfolge jedoch randomisiert (beginnend bei a pseudozufällig gewählten Schlüssel, und die Hashcode-Berechnung wird mit einer Pseudozufallszahl versehen). Wenn Sie Ihr Programm mit der wöchentlichen Version kompilieren (und mit Go1), wird die Iterationsreihenfolge jedes Mal unterschiedlich sein, wenn Sie Ihr Programm ausführen. Wenn Sie jedoch Ihr Programm unendlich oft ausführen, werden wahrscheinlich nicht alle möglichen Permutationen des Schlüsselsatzes gedruckt. Beispielausgaben:
%Vor%Wenn die Spezifikationen angeben, dass die Iterationsreihenfolge nicht angegeben ist, ist eine bestimmte Reihenfolge in bestimmten Fällen nicht ausgeschlossen.
Der Punkt ist, dass man sich auf keinen Fall auf diese Reihenfolge verlassen kann, nicht einmal in einem speziellen Fall. Die Implementierung kann dieses Verhalten jederzeit ändern, einschließlich der Laufzeit.
Beachten Sie, dass es nicht so seltsam für die Reihenfolge ist, unabhängig von der Reihenfolge der Reihenfolge stabil zu sein, wenn es eine Gesamtordnung über den Schlüsseln gibt (wie es häufig der Fall ist, wenn sie von einem homogenen Typ sind); wenn nichts anderes, kann es eine effiziente Suche über Schlüssel ermöglichen, die den gleichen Hash generieren.
Dies kann auch eine andere zugrundeliegende Implementierung widerspiegeln - insbesondere ist dies etwas, was Leute für Strings wünschen, aber für Ganzzahlen könnten Sie stattdessen ein Sparse-Array verwenden.