Wie werden die in Python integrierten Wörterbücher implementiert?

Weiß jemand, wie der eingebaute Wörterbuchtyp für Python implementiert ist? Mein Verständnis ist, dass es sich um eine Art Hash-Tabelle handelt, aber ich konnte keine endgültige Antwort finden.

Hier ist alles über Python-Diktate, die ich zusammenstellen konnte (wahrscheinlich mehr als jeder andere wissen möchte; aber die Antwort ist umfassend).

• Python-Wörterbücher werden als Hash-Tabellen implementiert .
• Hash-Tabellen müssen Hash-Kollisionen zulassen, dh selbst wenn zwei unterschiedliche Schlüssel denselben Hash-Wert haben, muss die Implementierung der Tabelle eine Strategie zum Einfügen und Abrufen der Schlüssel- und Wertepaare enthalten.
• Python dictverwendet eine offene Adressierung , um Hash-Kollisionen aufzulösen (siehe unten) (siehe dictobject.c: 296-297 ).
• Die Python-Hash-Tabelle ist nur ein zusammenhängender Speicherblock (ähnlich einem Array, sodass Sie eine O(1)Suche nach Index durchführen können).
• In jedem Slot in der Tabelle kann nur ein Eintrag gespeichert werden. Das ist wichtig.
• Jeder Eintrag in der Tabelle ist tatsächlich eine Kombination der drei Werte: <Hash, Schlüssel, Wert> . Dies wird als C-Struktur implementiert (siehe dictobject.h: 51-56 ).

• Die folgende Abbildung ist eine logische Darstellung einer Python-Hash-Tabelle. In der folgenden Abbildung 0, 1, ..., i, ...links sind die Indizes der Slots in der Hash-Tabelle dargestellt (sie dienen nur zur Veranschaulichung und werden offensichtlich nicht zusammen mit der Tabelle gespeichert!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Wenn ein neues Diktat initialisiert wird, beginnt es mit 8 Slots . (siehe dictobject.h: 49 )

• Beim Hinzufügen von Einträgen zur Tabelle beginnen wir mit einem Slot, ider auf dem Hash des Schlüssels basiert. CPython verwendet zunächst i = hash(key) & mask(wo mask = PyDictMINSIZE - 1, aber das ist nicht wirklich wichtig). Beachten Sie nur, dass der anfängliche Steckplatz, der iüberprüft wird, vom Hash des Schlüssels abhängt .
• Wenn dieser Slot leer ist, wird der Eintrag zum Slot hinzugefügt (mit Eintrag meine ich <hash|key|value>). Aber was ist, wenn dieser Steckplatz belegt ist? Höchstwahrscheinlich, weil ein anderer Eintrag denselben Hash hat (Hash-Kollision!)
• Wenn der Slot belegt ist, vergleicht CPython (und sogar PyPy) den Hash UND den Schlüssel (mit Vergleich meine ich ==Vergleich nicht den isVergleich) des Eintrags im Slot mit dem Hash und dem Schlüssel des aktuell einzufügenden Eintrags ( dictobject.c) : 337,344-345 ). Wenn beide übereinstimmen, wird angenommen, dass der Eintrag bereits vorhanden ist, gibt auf und fährt mit dem nächsten einzufügenden Eintrag fort. Wenn entweder Hash oder Schlüssel nicht übereinstimmen, beginnt die Prüfung .
• Das Prüfen bedeutet nur, dass die Steckplätze nach Steckplätzen durchsucht werden, um einen leeren Steckplatz zu finden. Technisch gesehen könnten wir einfach eins nach dem anderen gehen i+1, i+2, ...und das erste verfügbare verwenden (das ist lineare Prüfung). Aus Gründen, die in den Kommentaren ausführlich erläutert wurden (siehe dictobject.c: 33-126 ), verwendet CPython eine zufällige Prüfung . Bei der zufälligen Prüfung wird der nächste Schlitz in einer pseudozufälligen Reihenfolge ausgewählt. Der Eintrag wird dem ersten leeren Steckplatz hinzugefügt. Für diese Diskussion ist der tatsächliche Algorithmus, der zum Auswählen des nächsten Steckplatzes verwendet wird, nicht wirklich wichtig (siehe dictobject.c: 33-126 für den Algorithmus zum Prüfen ). Wichtig ist, dass die Steckplätze geprüft werden, bis der erste leere Steckplatz gefunden wird.
• Das gleiche passiert bei Suchvorgängen, beginnt nur mit dem anfänglichen Slot i (wobei i vom Hash des Schlüssels abhängt). Wenn sowohl der Hash als auch der Schlüssel nicht mit dem Eintrag im Slot übereinstimmen, beginnt die Prüfung, bis ein Slot mit einer Übereinstimmung gefunden wird. Wenn alle Steckplätze belegt sind, wird ein Fehler gemeldet.
• Übrigens dictwird die Größe geändert, wenn zwei Drittel voll sind. Dadurch wird vermieden, dass Suchvorgänge verlangsamt werden. (siehe dictobject.h: 64-65 )

HINWEIS: Ich habe die Python Dict-Implementierung als Antwort auf meine eigene Frage untersucht, wie mehrere Einträge in einem Diktat dieselben Hashwerte haben können. Ich habe hier eine leicht bearbeitete Version der Antwort gepostet, da die gesamte Forschung auch für diese Frage sehr relevant ist.

Wie werden die in Python integrierten Wörterbücher implementiert?

Hier ist der kurze Kurs:

• Sie sind Hash-Tabellen. (Einzelheiten zur Implementierung von Python finden Sie weiter unten.)
• Ein neues Layout und ein neuer Algorithmus ab Python 3.6 machen sie
  • bestellt durch Einstecken des Schlüssels und
  • weniger Platz beanspruchen,
  • praktisch ohne Leistungskosten.
• Eine weitere Optimierung spart Platz, wenn Diktate Schlüssel teilen (in besonderen Fällen).

Der geordnete Aspekt ist ab Python 3.6 inoffiziell (um anderen Implementierungen die Möglichkeit zu geben, Schritt zu halten), in Python 3.7 jedoch offiziell .

Pythons Wörterbücher sind Hash-Tabellen

Lange hat es genau so funktioniert. Python würde 8 leere Zeilen vorab zuordnen und anhand des Hashs bestimmen, wo das Schlüssel-Wert-Paar abgelegt werden soll. Wenn der Hash für den Schlüssel beispielsweise mit 001 endet, wird er im Index 1 (dh 2.) gespeichert (wie im folgenden Beispiel).

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Jede Zeile belegt 24 Bytes in einer 64-Bit-Architektur, 12 in einer 32-Bit-Architektur. (Beachten Sie, dass die Spaltenüberschriften nur Beschriftungen für unsere Zwecke sind - sie sind tatsächlich nicht im Speicher vorhanden.)

Wenn der Hash genauso endet wie der Hash eines bereits vorhandenen Schlüssels, handelt es sich um eine Kollision, die das Schlüssel-Wert-Paar an einer anderen Stelle festhält.

Nachdem 5 Schlüsselwerte gespeichert wurden, ist beim Hinzufügen eines weiteren Schlüssel-Wert-Paares die Wahrscheinlichkeit von Hash-Kollisionen zu groß, sodass das Wörterbuch doppelt so groß ist. In einem 64-Bit-Prozess sind vor der Größenänderung 72 Bytes leer, und danach verschwenden wir 240 Bytes aufgrund der 10 leeren Zeilen.

Dies nimmt viel Platz in Anspruch, aber die Suchzeit ist ziemlich konstant. Der Schlüsselvergleichsalgorithmus besteht darin, den Hash zu berechnen, zum erwarteten Speicherort zu gehen und die ID des Schlüssels zu vergleichen. Wenn es sich um dasselbe Objekt handelt, sind sie gleich. Wenn nicht, vergleichen Sie die Hash-Werte. Wenn sie nicht gleich sind, sind sie nicht gleich. Andernfalls vergleichen wir schließlich die Schlüssel auf Gleichheit und geben den Wert zurück, wenn sie gleich sind. Der endgültige Vergleich für die Gleichheit kann recht langsam sein, aber die früheren Überprüfungen verkürzen normalerweise den endgültigen Vergleich, wodurch die Suche sehr schnell erfolgt.

Kollisionen verlangsamen die Arbeit, und ein Angreifer könnte theoretisch Hash-Kollisionen verwenden, um einen Denial-of-Service-Angriff durchzuführen. Daher haben wir die Initialisierung der Hash-Funktion so randomisiert, dass für jeden neuen Python-Prozess unterschiedliche Hashes berechnet werden.

Der oben beschriebene verschwendete Speicherplatz hat uns veranlasst, die Implementierung von Wörterbüchern zu ändern, mit einer aufregenden neuen Funktion, bei der Wörterbücher jetzt durch Einfügen sortiert werden.

Die neuen kompakten Hash-Tabellen

Wir beginnen stattdessen damit, ein Array für den Index der Einfügung vorab zuzuweisen.

Da unser erstes Schlüssel-Wert-Paar in den zweiten Slot geht, indizieren wir wie folgt:

[null, 0, null, null, null, null, null, null]

Und unsere Tabelle wird nur durch die Einfügereihenfolge gefüllt:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

Wenn wir also nach einem Schlüssel suchen, verwenden wir den Hash, um die erwartete Position zu überprüfen (in diesem Fall gehen wir direkt zu Index 1 des Arrays) und dann zu diesem Index in der Hash-Tabelle (z. B. Index 0) ), überprüfen Sie, ob die Schlüssel gleich sind (unter Verwendung des zuvor beschriebenen Algorithmus), und geben Sie in diesem Fall den Wert zurück.

Wir behalten die konstante Suchzeit bei, mit geringfügigen Geschwindigkeitsverlusten in einigen Fällen und Gewinnen in anderen Fällen, mit dem Vorteil, dass wir gegenüber der bereits vorhandenen Implementierung viel Platz sparen und die Einfügereihenfolge beibehalten. Der einzige verschwendete Speicherplatz sind die Null-Bytes im Index-Array.

Raymond Hettinger hat dies im Dezember 2012 auf Python-Dev eingeführt . Es wurde schließlich in Python 3.6 in CPython aufgenommen . Die Bestellung durch Einfügen wurde als Implementierungsdetail für 3.6 angesehen, damit andere Implementierungen von Python aufholen können.

Geteilte Schlüssel

Eine weitere platzsparende Optimierung ist eine Implementierung, die Schlüssel gemeinsam nutzt. Anstatt redundante Wörterbücher zu haben, die den gesamten Speicherplatz einnehmen, haben wir Wörterbücher, die die gemeinsam genutzten Schlüssel und Schlüssel-Hashes wiederverwenden. Sie können sich das so vorstellen:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Bei einem 64-Bit-Computer können bis zu 16 Byte pro Schlüssel und zusätzlichem Wörterbuch eingespart werden.

Freigegebene Schlüssel für benutzerdefinierte Objekte und Alternativen

Diese Dicts mit gemeinsamem Schlüssel sind für benutzerdefinierte Objekte vorgesehen __dict__. Um dieses Verhalten zu erhalten, müssen Sie meines Erachtens das __dict__Auffüllen Ihres Objekts beenden, bevor Sie Ihr nächstes Objekt instanziieren ( siehe PEP 412 ). Dies bedeutet, dass Sie alle Ihre Attribute im __init__oder zuweisen sollten, da Sie __new__sonst möglicherweise keine Platzersparnis erzielen.

Wenn Sie jedoch alle Ihre Attribute zum Zeitpunkt Ihrer __init__Ausführung kennen, können Sie auch __slots__für Ihr Objekt sorgen und garantieren, dass __dict__es überhaupt nicht erstellt wird (falls es nicht in den Eltern verfügbar ist), oder sogar zulassen, __dict__aber garantieren, dass Ihre vorgesehenen Attribute vorhanden sind sowieso in Steckplätzen gespeichert. Weitere Informationen __slots__finden Sie in meiner Antwort hier .

Siehe auch:

• PEP 509 - Fügen Sie eine private Version zum Diktieren hinzu
• PEP 468 - Beibehalten der Reihenfolge **kwargsin einer Funktion.
• PEP 520 - Beibehalten der Reihenfolge der Definition von Klassenattributen
• PyCon 2010: Das Machtwörterbuch - Brandon Rhodes
• PyCon 2017: Das Wörterbuch noch mächtiger - Brandon Rhodes
• PyCon 2017: Moderne Python-Wörterbücher Ein Zusammenfluss von einem Dutzend großartiger Ideen - Raymond Hettinger
• dictobject.c - CPythons tatsächliche Dikt-Implementierung in C.

Python-Wörterbücher verwenden offene Adressierung ( Referenz im schönen Code )

NB! Offenes Adressieren , auch geschlossenes Hashing genannt, sollte, wie in Wikipedia erwähnt, nicht mit dem entgegengesetzten offenen Hashing verwechselt werden !

Offene Adressierung bedeutet, dass das Diktat Array-Slots verwendet. Wenn die primäre Position eines Objekts im Diktat eingenommen wird, wird der Punkt des Objekts an einem anderen Index im selben Array gesucht, wobei ein "Störungs" -Schema verwendet wird, bei dem der Hash-Wert des Objekts eine Rolle spielt .