Warum ist die Reihenfolge in Wörterbüchern und Mengen beliebig?

Ich verstehe nicht, wie das Durchlaufen eines Wörterbuchs oder eines Satzes in Python in 'beliebiger' Reihenfolge erfolgt.

Ich meine, es ist eine Programmiersprache, also muss alles in der Sprache zu 100% bestimmt sein, richtig? Python muss über einen Algorithmus verfügen, der entscheidet, welcher Teil des Wörterbuchs oder der Menge ausgewählt wird, 1., 2. usw.

Was vermisse ich?

Hinweis: Diese Antwort wurde geschrieben, bevor die Implementierung des dictTyps in Python 3.6 geändert wurde. Die meisten Implementierungsdetails in dieser Antwort gelten weiterhin, aber die Auflistungsreihenfolge der Schlüssel in Wörterbüchern wird nicht mehr durch Hashwerte bestimmt. Die eingestellte Implementierung bleibt unverändert.

Die Reihenfolge ist nicht willkürlich, sondern hängt vom Einfüge- und Löschverlauf des Wörterbuchs oder Satzes sowie von der spezifischen Python-Implementierung ab. Für den Rest dieser Antwort können Sie für 'Wörterbuch' auch 'set' lesen. Mengen werden als Wörterbücher mit nur Schlüsseln und ohne Werte implementiert.

Schlüssel werden gehasht und Hash-Werte werden Slots in einer dynamischen Tabelle zugewiesen (sie können je nach Bedarf wachsen oder schrumpfen). Und dieser Zuordnungsprozess kann zu Kollisionen führen, was bedeutet, dass ein Schlüssel in einen nächsten Steckplatz gesteckt werden muss, basierend auf dem, was bereits vorhanden ist.

Das Auflisten der Inhaltsschleifen über den Steckplätzen führt dazu, dass die Schlüssel in der Reihenfolge aufgelistet werden, in der sie sich derzeit in der Tabelle befinden.

Nehmen Sie zum Beispiel die Schlüssel 'foo'und 'bar'und nehmen wir an, dass die Tabellengröße 8 Steckplätze beträgt. In Python 2.7 hash('foo')ist -4177197833195190597, hash('bar')ist 327024216814240868. Modulo 8, dh diese beiden Tasten sind in die Steckplätze 3 und 4 eingesteckt.

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

Dies informiert ihre Auflistungsreihenfolge:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

Alle Steckplätze außer 3 und 4 sind leer. In einer Schleife über die Tabelle werden zuerst Steckplatz 3 und dann Steckplatz 4 'foo'aufgelistet 'bar'.

barund bazhaben jedoch Hash-Werte, die genau 8 voneinander entfernt sind und somit genau demselben Slot zugeordnet sind 4:

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

Ihre Reihenfolge hängt nun davon ab, welcher Schlüssel zuerst gesteckt wurde. Der zweite Schlüssel muss in einen nächsten Steckplatz verschoben werden:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

Die Tabellenreihenfolge unterscheidet sich hier, da der eine oder andere Schlüssel zuerst gesteckt wurde.

Der technische Name für die zugrunde liegende Struktur, die von CPython verwendet wird (die am häufigsten verwendete Python-Implementierung), ist eine Hash-Tabelle , die eine offene Adressierung verwendet. Wenn Sie neugierig sind und C gut genug verstehen, werfen Sie einen Blick auf die C-Implementierung, um alle (gut dokumentierten) Details zu erhalten. Sie können sich auch diese Pycon 2010-Präsentation von Brandon Rhodes über die Funktionsweise von CPython ansehen dictoder eine Kopie von Beautiful Code abholen , die ein Kapitel über die von Andrew Kuchling geschriebene Implementierung enthält.

Beachten Sie, dass ab Python 3.3 auch ein zufälliger Hash-Startwert verwendet wird, wodurch Hash-Kollisionen unvorhersehbar werden, um bestimmte Arten von Denial-of-Service zu verhindern (wenn ein Angreifer einen Python-Server durch Massen-Hash-Kollisionen nicht mehr reagiert). Dies bedeutet, dass die Reihenfolge eines bestimmten Wörterbuchs oder Satzes dann auch vom zufälligen Hash-Startwert für den aktuellen Python-Aufruf abhängt.

Andere Implementierungen können eine andere Struktur für Wörterbücher verwenden, sofern sie die für sie dokumentierte Python-Schnittstelle erfüllen. Ich glaube jedoch, dass alle Implementierungen bisher eine Variation der Hash-Tabelle verwenden.

CPython 3.6 führt eine neue dict Implementierung ein, die die Einfügereihenfolge beibehält und schneller und speichereffizienter zu starten ist. Anstatt eine große Tabelle mit geringer Dichte zu führen, in der jede Zeile auf den gespeicherten Hashwert sowie auf die Schlüssel- und Wertobjekte verweist, fügt die neue Implementierung ein kleineres Hash- Array hinzu , das nur auf Indizes in einer separaten 'dichten' Tabelle verweist (eine, die nur so viele Zeilen enthält da es tatsächliche Schlüssel-Wert-Paare gibt), und es ist die dichte Tabelle, die die enthaltenen Elemente der Reihe nach auflistet. Weitere Informationen finden Sie im Vorschlag an Python-Dev . Beachten Sie, dass dies in Python 3.6 als Implementierungsdetail betrachtet wirdPython-the-language gibt nicht an, dass andere Implementierungen die Reihenfolge beibehalten müssen. Dies änderte sich in Python 3.7, wo dieses Detail zu einer Sprachspezifikation erhoben wurde . Damit eine Implementierung ordnungsgemäß mit Python 3.7 oder neuer kompatibel ist, muss dieses auftragserhaltende Verhalten kopiert werden. Und um es klar auszudrücken: Diese Änderung gilt nicht für Mengen, da Mengen bereits eine 'kleine' Hash-Struktur haben.

Python 2.7 und höher bietet auch eine OrderedDictKlasse , deren Unterklasse dicteine zusätzliche Datenstruktur zum Aufzeichnen der Schlüsselreihenfolge hinzufügt. Diese Klasse merkt sich zum Preis von Geschwindigkeit und zusätzlichem Speicher, in welcher Reihenfolge Sie Schlüssel eingefügt haben. Das Auflisten von Schlüsseln, Werten oder Elementen erfolgt dann in dieser Reihenfolge. Es verwendet eine doppelt verknüpfte Liste, die in einem zusätzlichen Wörterbuch gespeichert ist, um die Bestellung effizient auf dem neuesten Stand zu halten. Siehe den Beitrag von Raymond Hettinger, der die Idee umreißt . OrderedDictObjekte haben andere Vorteile, wie zum Beispiel die Nachbestellbarkeit .

Wenn Sie ein bestelltes Set wünschen, können Sie das osetPaket installieren . Es funktioniert unter Python 2.5 und höher.

Dies ist eher eine Antwort auf Python 3.41 Ein Satz, bevor er als Duplikat geschlossen wurde.

Die anderen haben Recht: Verlassen Sie sich nicht auf die Bestellung. Tu nicht einmal so, als gäbe es einen.

Es gibt jedoch eine Sache, auf die Sie sich verlassen können:

list(myset) == list(myset)

Das heißt, die Reihenfolge ist stabil .

Um zu verstehen, warum es eine wahrgenommene Ordnung gibt, müssen einige Dinge verstanden werden:

• Dass Python Hash-Sets verwendet ,

• Wie CPythons Hash-Set im Speicher gespeichert wird und

• Wie Zahlen gehasht werden

Von oben:

Ein Hash-Set ist eine Methode zum Speichern von Zufallsdaten mit sehr schnellen Suchzeiten.

Es hat ein Hintergrundarray:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Wir werden das spezielle Dummy-Objekt ignorieren, das nur existiert, um das Behandeln von Entfernungen zu vereinfachen, da wir nicht aus diesen Mengen entfernen werden.

Um wirklich schnell nachschlagen zu können, zaubern Sie einen Hash aus einem Objekt. Die einzige Regel ist, dass zwei Objekte, die gleich sind, denselben Hash haben. (Wenn jedoch zwei Objekte denselben Hash haben, können sie ungleich sein.)

Sie erstellen dann einen Index, indem Sie den Modul anhand der Arraylänge nehmen:

hash(4) % len(storage) = index 2

Dies macht es sehr schnell, auf Elemente zuzugreifen.

Hashes sind nur die meisten der Geschichte, wie hash(n) % len(storage)und hash(m) % len(storage)in gleicher Anzahl zur Folge haben kann. In diesem Fall können verschiedene Strategien versuchen, den Konflikt zu lösen. CPython verwendet 9-mal "lineares Prüfen", bevor komplizierte Dinge ausgeführt werden. Daher wird links vom Slot nach bis zu 9 Stellen gesucht, bevor nach einer anderen Stelle gesucht wird.

CPythons Hash-Sets werden wie folgt gespeichert:

• Ein Hash-Set darf nicht mehr als 2/3 voll sein . Wenn 20 Elemente vorhanden sind und das Hintergrundarray 30 Elemente lang ist, wird die Größe des Hintergrundspeichers größer. Dies liegt daran, dass Kollisionen mit kleinen Backing-Stores häufiger auftreten und Kollisionen alles verlangsamen.

• Die Größe des Hintergrundspeichers wird in Potenzen von 4 beginnend bei 8 geändert, mit Ausnahme von großen Sätzen (50.000 Elemente), deren Größe in Zweierpotenzen geändert wird: (8, 32, 128, ...).

Wenn Sie also ein Array erstellen, hat der Hintergrundspeicher die Länge 8. Wenn er 5 voll ist und Sie ein Element hinzufügen, enthält er kurz 6 Elemente. 6 > ²⁄₃·8Dies löst also eine Größenänderung aus, und der Hintergrundspeicher vervierfacht sich auf Größe 32.

Schließlich wird hash(n)nur nfür Zahlen zurückgegeben (außer -1was speziell ist).

Schauen wir uns also den ersten an:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set)ist 10, also ist der Hintergrundspeicher mindestens 15 (+1), nachdem alle Elemente hinzugefügt wurden . Die relevante Potenz von 2 ist 32. Der Hintergrundspeicher lautet also:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Wir haben

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

also diese einfügen als:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

Wir würden also eine Bestellung wie erwarten

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

mit der 1 oder 33 ist das nicht woanders am Start. Dies wird eine lineare Abtastung verwenden, also haben wir entweder:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

oder

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

Sie können erwarten, dass die 33 diejenige ist, die verschoben wurde, weil die 1 bereits vorhanden war. Aufgrund der Größenänderung, die beim Erstellen des Sets auftritt, ist dies jedoch nicht der Fall. Jedes Mal, wenn das Set neu erstellt wird, werden die bereits hinzugefügten Elemente effektiv neu angeordnet.

Jetzt können Sie sehen warum

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

könnte in Ordnung sein. Es gibt 14 Elemente, sodass der Hintergrundspeicher mindestens 21 + 1 beträgt, was 32 bedeutet:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 bis 13 Hash in den ersten 13 Slots. 20 geht in Steckplatz 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 geht in Slot, hash(55) % 32der 23 ist:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

Wenn wir stattdessen 50 wählen würden, würden wir erwarten

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

Und siehe da:

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop wird ganz einfach durch das Aussehen der Dinge implementiert: Es durchläuft die Liste und öffnet die erste.

Dies ist alles Implementierungsdetail.

"Willkürlich" ist nicht dasselbe wie "unbestimmt".

Was sie sagen ist, dass es keine nützlichen Eigenschaften der Wörterbuch-Iterationsreihenfolge gibt, die "in der öffentlichen Schnittstelle" sind. Es gibt mit ziemlicher Sicherheit viele Eigenschaften der Iterationsreihenfolge, die vollständig durch den Code bestimmt werden, der derzeit die Wörterbuchiteration implementiert, aber die Autoren versprechen Ihnen diese nicht als etwas, das Sie verwenden können. Dies gibt ihnen mehr Freiheit, diese Eigenschaften zwischen Python-Versionen zu ändern (oder sogar nur unter verschiedenen Betriebsbedingungen oder zur Laufzeit völlig zufällig), ohne befürchten zu müssen, dass Ihr Programm kaputt geht.

Wenn Sie also ein Programm schreiben, das von einer Eigenschaft in der gesamten Wörterbuchreihenfolge abhängt , brechen Sie den Vertrag über die Verwendung des Wörterbuchtyps, und die Python-Entwickler versprechen nicht, dass dies immer funktioniert, auch wenn es zu funktionieren scheint für jetzt, wenn Sie es testen. Es ist im Grunde das Äquivalent zu "undefiniertem Verhalten" in C.

Die anderen Antworten auf diese Frage sind ausgezeichnet und gut geschrieben. Das OP fragt "wie", was ich als "wie kommen sie davon" oder "warum" interpretiere.

In der Python-Dokumentation heißt es, dass Wörterbücher nicht geordnet sind, da das Python-Wörterbuch das assoziative Array des abstrakten Datentyps implementiert . Wie sie sagen

Die Reihenfolge, in der die Bindungen zurückgegeben werden, kann beliebig sein

Mit anderen Worten, ein Informatikstudent kann nicht davon ausgehen, dass ein assoziatives Array geordnet ist. Gleiches gilt für Mengen in Mathematik

Die Reihenfolge, in der die Elemente einer Menge aufgelistet werden, spielt keine Rolle

und Informatik

Ein Satz ist ein abstrakter Datentyp, der bestimmte Werte ohne bestimmte Reihenfolge speichern kann

Das Implementieren eines Wörterbuchs mithilfe einer Hash-Tabelle ist ein Implementierungsdetail , das insofern interessant ist, als es hinsichtlich der Reihenfolge dieselben Eigenschaften wie assoziative Arrays aufweist.

Python verwendet eine Hash-Tabelle zum Speichern der Wörterbücher, daher gibt es keine Reihenfolge in Wörterbüchern oder anderen iterierbaren Objekten, die eine Hash-Tabelle verwenden.

Aber in Bezug auf die Indizes der Elemente in einem Hash - Objekt, berechnen Python die Indizes basieren auf folgenden Code inhashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

Da der Hash-Wert von Ganzzahlen die Ganzzahl selbst ist ^*, basiert der Index auf der Zahl ( ht->num_buckets - 1ist eine Konstante), so dass der von Bitwise-and zwischen (ht->num_buckets - 1)und der Zahl selbst berechnete Index ^* (erwarten Sie für -1, dass sein Hash -2 ist ) und für andere Objekte mit ihrem Hashwert.

Betrachten Sie das folgende Beispiel mit setdieser Hash-Tabelle:

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

Für die Nummer haben 33wir:

33 & (ht->num_buckets - 1) = 1

Das ist eigentlich:

'0b100001' & '0b111'= '0b1' # 1 the index of 33

Hinweis in diesem Fall (ht->num_buckets - 1)ist 8-1=7oder 0b111.

Und für 1919:

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

Und für 333:

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

Weitere Informationen zur Python-Hash-Funktion finden Sie in den folgenden Zitaten aus dem Python-Quellcode :

Wichtige Feinheiten: Die meisten Hash-Schemata hängen von einer "guten" Hash-Funktion im Sinne einer Simulation der Zufälligkeit ab. Python nicht: Die wichtigsten Hash-Funktionen (für Strings und Ints) sind in den häufigsten Fällen sehr regelmäßig:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

Das ist nicht unbedingt schlecht! Im Gegensatz dazu ist es in einer Tabelle der Größe 2 ** i extrem schnell, die niederwertigen i-Bits als anfänglichen Tabellenindex zu verwenden, und es gibt überhaupt keine Kollisionen für Dikte, die durch einen zusammenhängenden Bereich von Ints indiziert sind. Das gleiche gilt ungefähr, wenn Schlüssel "aufeinanderfolgende" Zeichenfolgen sind. Dies führt in häufigen Fällen zu einem besser als zufälligen Verhalten, und das ist sehr wünschenswert.

OTOH: Wenn Kollisionen auftreten, ist die Tendenz, zusammenhängende Abschnitte der Hash-Tabelle zu füllen, eine gute Strategie zur Auflösung von Kollisionen von entscheidender Bedeutung. Es ist auch anfällig, nur die letzten i Bits des Hash-Codes zu verwenden: Betrachten Sie die Liste beispielsweise [i << 16 for i in range(20000)]als einen Satz von Schlüsseln. Da Ints ihre eigenen Hash-Codes sind und dies in ein Diktat der Größe 2 ** 15 passt, sind die letzten 15 Bits jedes Hash-Codes alle 0: Sie werden alle demselben Tabellenindex zugeordnet.

Aber die Behandlung ungewöhnlicher Fälle sollte die üblichen nicht verlangsamen, also nehmen wir trotzdem nur die letzten i Bits. Es liegt an der Kollisionsauflösung, den Rest zu erledigen. Wenn wir normalerweise beim ersten Versuch den Schlüssel finden, nach dem wir suchen (und wie sich herausstellt, tun wir dies normalerweise - der Tabellenladefaktor wird unter 2/3 gehalten, sodass die Chancen solide zu unseren Gunsten sind), dann ist es so Es ist am besten, die anfängliche Indexberechnung spottbillig zu halten.

_{* Die Hash-Funktion für die Klasse int:}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

Ab Python 3.7 (und bereits in CPython 3.6 ) bleiben die Wörterbuchelemente in der Reihenfolge, in der sie eingefügt wurden .