Wörterbuchimplementierung in Python 2.7

In diesem Artikel wird erläutert, wie das Wörterbuch in Python implementiert wird. Ich werde versuchen, die Frage zu beantworten, warum die Elemente des Wörterbuchs nicht sortiert sind, um zu beschreiben, wie die Wörterbücher ihre Elemente speichern, hinzufügen und löschen. Ich hoffe, dass der Artikel nicht nur für Leute nützlich ist, die Python lernen, sondern auch für alle, die an der internen Struktur und Organisation von Datenstrukturen interessiert sind.

Die Frage zu Stack Overflow veranlasste mich, diesen Artikel zu schreiben .
Dieser Artikel beschreibt die Implementierung von CPython Version 2.7. Alle Beispiele wurden in einer 32-Bit-Version von Python unter einem 64-Bit-Betriebssystem erstellt. Bei einer anderen Version unterscheiden sich die Werte.

Python-Wörterbuch


Ein Wörterbuch in Python ist ein assoziatives Array, das heißt, es speichert Daten als Paare (Schlüssel, Wert). Ein Wörterbuch ist ein veränderbarer Datentyp. Dies bedeutet, dass Sie Elemente hinzufügen, ändern und aus dem Wörterbuch löschen können. Es bietet auch die Möglichkeit, einen Artikel mit einem Schlüssel zu finden und zurückzugeben.

Elemente initialisieren und hinzufügen:

>>> d = {} # то же самое, что d = dict()
>>> d['a'] = 123
>>> d['b'] = 345
>>> d['c'] = 678
>>> d
{'a': 123, 'c': 678, 'b': 345}

Artikel erhalten:

>>> d['b']
345

Artikel löschen:

>>> del d['c']
>>> d
{'a': 123, 'b': 345}

Die Schlüssel des Wörterbuchs können nur Werte von Hash-Typen sein, dh Typen, die einen Hash haben können (hierfür müssen sie eine __hash __ () -Methode haben). Daher können Werte von Typen wie eine Liste, eine Menge und das Wörterbuch selbst (dict) keine Wörterbuchschlüssel sein:

>>> d[list()] = 1
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'list'
>>> d[set()] = 2
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'set'
>>> d[dict()] = 3
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'dict'


Implementierung


Ein Wörterbuch in Python ist als Hash-Tabelle implementiert. Wie Sie wissen, sollte eine Implementierung einer Hash-Tabelle die Möglichkeit von Kollisionen berücksichtigen - Situationen, in denen verschiedene Schlüssel den gleichen Hash-Wert haben. Es sollte eine Möglichkeit geben, Elemente unter Berücksichtigung von Kollisionen einzufügen und zu extrahieren. Es gibt verschiedene Möglichkeiten, um Kollisionen aufzulösen, z. B. die Verkettungsmethode und die offene Adressierungsmethode. Python verwendet die offene Adressierungsmethode. Die Entwickler zogen die offene Adressierungsmethode der Verkettungsmethode vor, da durch das Speichern von Zeigern, die in Ketten-Hash-Tabellen verwendet werden, Speicherplatz gespart werden kann.

In dieser Implementierung besteht jeder Eintrag (PyDictEntry) in der Dictionary-Hash-Tabelle aus drei Elementen - einem Hash, einem Schlüssel und einem Wert.

typedef struct {
  Py_ssize_t me_hash;
  PyObject *me_key;
  PyObject *me_value;
} PyDictEntry;

Die Struktur von PyDictObject ist wie folgt:

#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
  PyObject_HEAD
  Py_ssize_t ma_fill;
  Py_ssize_t ma_used;
  Py_ssize_t ma_mask;
  PyDictEntry *ma_table;
  PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
  PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

Beim Erstellen eines neuen Wörterbuchobjekts beträgt seine Größe 8. Dieser Wert wird durch die PyDict_MINSIZE-Konstante bestimmt. Um die Hash-Tabelle zu speichern, wurden die Variablen ma_smalltable und ma_table in PyDictObject eingeführt. Die Variable ma_smalltable mit vorab zugewiesenem Speicher der Größe PyDict_MINSIZE (d. H. 8) ermöglicht das Speichern kleiner Wörterbücher (bis zu 8 PyDictEntry-Objekte) ohne zusätzliche Speicherzuweisung. Die von den Entwicklern durchgeführten Experimente haben gezeigt, dass diese Größe für die meisten Wörterbücher ausreicht: kleine Instanzwörterbücher und normalerweise kleine Wörterbücher, die erstellt wurden, um benannte Argumente (kwargs) zu übergeben. Die Variable ma_table entspricht ma_smalltable für kleine Tabellen (dh für Tabellen mit 8 Zellen). Bei größeren Tabellen wird ma_table separat zugeordnet. Die Variable ma_table darf nicht NULL sein.

Wenn jemand plötzlich den Wert von PyDict_MINSIZE ändern möchte, können Sie dies in der Quelle tun und dann Python neu erstellen. Es wird empfohlen, dass der Wert der Potenz von zwei entspricht, jedoch nicht weniger als vier.

Eine Zelle in einer Hash-Tabelle kann drei Zustände haben


1) Unbenutzt (me_key == me_value == NULL)
Dieser Zustand bedeutet, dass die Zelle kein Paar (Schlüssel, Wert) enthält und niemals enthalten hat.
Nach dem Einstecken des Schlüssels geht die "unbenutzte" Zelle in den "aktiven" Zustand über.
Dieser Zustand ist der einzige Fall, wenn me_key = NULL ist, und ist der Anfangszustand für alle Zellen in der Tabelle.
2) Aktiv (me_key! = NULL und me_key! = Dummy und me_value! = NULL) Bedeutet,
dass die Zelle ein aktives Paar (Schlüssel, Wert) enthält.
Nach dem Entfernen des Schlüssels wechselt die Zelle aus dem aktiven Zustand in den leeren Zustand (dh me_key = dummy und
dummy = PyString_FromString ()")).
Это единственное состояние, когда me_value != NULL.
3) Пустая (me_key == dummy и me_value == NULL)
Это состояние говорит о том, что ячейка ранее содержала активную пару (ключ, значение), но она была удалена, и новая активная пара ещё не записана в ячейку.
Так же как и при состоянии «неиспользованная», после вставки ключа ячейка из состояния «пустая» переходит в состояние «активная».
«Пустая» ячейка не может вернуться в состояние «неиспользованная», то есть вернуть me_key = NULL, так как в данном случае последовательность проб в случае коллизии не будет иметь возможность узнать, были ли ячейки «активны».

Переменные-члены структуры


ma_fill - Die Anzahl der Nicht-Null-Schlüssel (me_key! = NULL), dh die Summe der "aktiven" und "leeren" Zellen.
ma_used - Die Anzahl der von Null verschiedenen und nicht leeren Schlüssel (me_key! = NULL, me_key! = Dummy), dh die Anzahl der "aktiven" Zellen.
ma_mask - Maske gleich PyDict_MINSIZE - 1.
ma_lookup - Suchfunktion. Standardmäßig wird lookdict_string beim Erstellen eines neuen Wörterbuchs verwendet. Dies geschieht, weil die Entwickler entschieden haben, dass die meisten Wörterbücher nur Zeichenfolgenschlüssel enthalten.

Die wichtigsten Feinheiten


Die Effektivität der Hash-Tabelle hängt von der Verfügbarkeit von "guten" Hash-Funktionen ab. Eine "gute" Hash-Funktion muss schnell und mit einem Minimum an Kollisionen berechnet werden. Leider geben die am häufigsten verwendeten und wichtigsten Hash-Funktionen (für String- und Integer-Typen) ziemlich reguläre Werte zurück, was zu Kollisionen führt. Nehmen Sie ein Beispiel:

>>> map(hash, [0, 1, 2, 3, 4])
[0, 1, 2, 3, 4]
>>> map(hash, ['abca', 'abcb', 'abcc', 'abcd', 'abce'])
[1540938117, 1540938118, 1540938119, 1540938112, 1540938113]

Bei ganzen Zahlen sind Hashes ihre Werte, sodass aufeinanderfolgende Zahlen aufeinanderfolgende Hashes haben und bei aufeinanderfolgenden Zeilen aufeinanderfolgende Hashes. Dies ist im Gegensatz dazu in einer Tabelle der Größe 2 ** i nicht unbedingt schlecht, da die i unteren Bits des Hash als Anfangsindex der Tabelle sehr schnell sind, und für Wörterbücher, die durch eine Folge von ganzen Zahlen indiziert sind, gibt es überhaupt keine Kollisionen:



Dasselbe wird fast vollständig beobachtet, wenn Wörterbuchtasten sind "aufeinanderfolgende" Zeilen (wie im obigen Beispiel). In der Regel führt dies bei Bedarf zu mehr als zufälligem Verhalten.



Wenn Sie nur die am wenigsten signifikanten Bits des Hash als Index verwenden, ist dies auch für Kollisionen anfällig. Nehmen Sie beispielsweise die Liste [i << 16 für i in range (20000)] als einen Satz von Schlüsseln. Da ganze Zahlen ihre eigenen Hashes sind und dies in ein Wörterbuch der Größe 2 ** 15 (seit 20.000 <32768) passt, sind die letzten 15 Bits von jedem Hash alle 0.

>>> map(lambda x: '{0:016b}'.format(x), [i << 16 for i in xrange(20000)])
['0000000000000000', '10000000000000000', '100000000000000000', '110000000000000000', '1000000000000000000', '1010000000000000000', '1100000000000000000', '1110000000000000000', ...]

Es stellt sich heraus, dass alle Schlüssel den gleichen Index haben. Das heißt, bei allen Schlüsseln (mit Ausnahme der ersten) treten Kollisionen auf.
Beispiele für speziell ausgewählte "schlechte" Fälle sollten normale Fälle nicht beeinflussen, lassen Sie also einfach die letzten i-Bits. Alles andere bleibt der Konfliktlösungsmethode überlassen.

Kollisionslösungsmethode


Das Verfahren zum Auswählen einer geeigneten Zelle zum Einfügen eines Elements in die Hash-Tabelle wird als Sondieren bezeichnet, und die betreffende Kandidatenzelle wird als Sondieren bezeichnet.

In der Regel befindet sich die Zelle beim ersten Versuch (und das ist tatsächlich so, weil der Füllfaktor der Hash-Tabelle unter 2/3 gehalten wird), wodurch Sie Zeit beim Prüfen sparen und den anfänglichen Index sehr schnell berechnen können. Aber schauen wir uns an, was passiert, wenn ein Konflikt auftritt.

Der erste Teil der Kollisionsauflösungsmethode besteht in der Berechnung der Tabellenindizes für die Prüfung mit der Formel:

j = ((5 * j) + 1) % 2**i

Für jedes initiale j innerhalb von [0 .. (2 ** i - 1)] wird durch zweimaliges Aufrufen dieser Formel jede Zahl innerhalb von [0 .. (2 ** i - 1)] genau einmal zurückgegeben. Zum Beispiel:

>>> j = 0
>>> i = 3
>>> for _ in xrange(0, 2**i):
...     print j,
...     j = ((5 * j) + 1) % 2**i
...
0 1 6 7 4 5 2 3

Sie werden sagen, dass dies nicht besser ist als die Verwendung der linearen Abtastung mit einem konstanten Schritt, da in diesem Fall die Zellen in der Hash-Tabelle ebenfalls in einer bestimmten Reihenfolge gescannt werden, dies ist jedoch nicht der einzige Unterschied. In der Regel ist diese Methode besser als die lineare Abtastung, wenn der Hash der Schlüsselwerte in einer Reihe liegt. Aus dem obigen Beispiel ist ersichtlich, dass für eine Tabelle der Größe 8 (2 ** 3) die Reihenfolge der Indizes wie folgt lautet:

0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 -> … (затем идут повторения)

Если произойдёт коллизия для пробы с индексом, равным 5, то следующий индекс пробы будет 2, а не 6, как в случае линейного пробирования с шагом +1, поэтому для ключа, добавляемого в будущем, индекс пробы которого будет равен 6, коллизии не произойдёт. Линейное пробирование в данном случае (при последовательных значениях ключей) было бы плохим вариантом, так как происходило бы много коллизий. Вероятность же того, что хэш значения ключей будут идти в порядке 5 * j + 1, намного меньше.

Вторая часть метода разрешения коллизий заключается в использовании не только младших i бит хэша, но и остальных бит тоже. Это реализовано с использованием переменной perturb следующим образом:

    j = (5 * j) + 1 + perturb
    perturb >>= PERTURB_SHIFT
    затем j % 2**i используется как следующий индекс пробы
где:
    perturb = hash(key)
    PERTURB_SHIFT = 5

Danach hängt die Reihenfolge der Tests von jedem Bit des Hashs ab. Pseudozufallsvariation ist sehr effektiv, da sie die Unterschiede in den Bits schnell erhöht. Da die Störungsvariable nicht vorzeichenbehaftet ist, wird und bleibt die Störungsvariable schließlich gleich Null, wenn das Testen häufig genug durchgeführt wird. Zu diesem Zeitpunkt (der sehr selten erreicht wird) wird das Ergebnis j wieder gleich 5 * j + 1. Ferner erfolgt die Suche genauso wie im ersten Teil des Verfahrens, und es wird letztendlich eine freie Zelle gefunden, da, wie bereits erwähnt, jede Eine Zahl im Bereich [0 .. (2 ** i - 1)] wird genau einmal zurückgegeben, und wir sind sicher, dass es immer mindestens eine "unbenutzte" Zelle gibt.

Die Wahl eines „guten“ Werts für PERTURB_SHIFT ist eine Frage der Ausgewogenheit. Wenn Sie es klein machen, beeinflussen die hohen Bits des Hash die Sequenz der Tests durch Iterationen. Wenn Sie es groß machen, wirken sich die hohen Bits des Hash in wirklich „schlechten“ Fällen nur auf die frühen Iterationen aus. Aufgrund von Experimenten, die von einem der Python-Entwickler, Tim Peters, durchgeführt wurden, wurde der Wert PERTURB_SHIFT gleich 5 gewählt, da sich dieser Wert als "am besten" herausstellte. Das heißt, es wurde die minimale Gesamtanzahl von Kollisionen sowohl für normale als auch für speziell ausgewählte "schlechte" Fälle angezeigt, obwohl die Werte 4 und 6 nicht signifikant schlechter waren.

Historischer Hinweis: Einer der Python-Entwickler, Reimer Berends, schlug vor, einen auf Polynomen basierenden Ansatz zur Berechnung von Tabellenindizes zu verwenden, der dann von Christian Tismer verbessert wurde. Dieser Ansatz zeigte auch hervorragende Ergebnisse bei Kollisionen, erforderte jedoch mehr Operationen sowie eine zusätzliche Variable zum Speichern des Tabellenpolynoms in der PyDictObject-Struktur. In den Experimenten von Tim Peters erwies sich die derzeit in Python verwendete Methode als schneller und zeigte beim Auftreten von Kollisionen gleich gute Ergebnisse, erforderte jedoch weniger Code und verbrauchte weniger Speicher.

Vokabelinitialisierung


Wenn Sie ein Wörterbuch erstellen, wird die Funktion PyDict_New aufgerufen. In dieser Funktion werden die folgenden Vorgänge nacheinander ausgeführt: Der Speicher wird für ein neues PyDictObject-Wörterbuchobjekt reserviert. Die Variable ma_smalltable wird gelöscht. Die Variablen ma_used und ma_fill werden auf 0 gesetzt, ma_table wird gleich ma_smalltable. Der Wert von ma_mask ist gleich PyDict_MINSIZE - 1. Die Funktion zum Suchen von ma_lookup ist auf lookdict_string gesetzt. Das erstellte Dictionary-Objekt wird zurückgegeben.

Artikel hinzufügen


Wenn Sie dem Wörterbuch ein Element hinzufügen oder den Wert eines Elements im Wörterbuch ändern, wird die Funktion PyDict_SetItem aufgerufen. In dieser Funktion wird der Hashwert genommen und die Funktion insertdict aufgerufen, sowie die Funktion dictresize, wenn die Tabelle zu 2/3 der aktuellen Größe gefüllt ist.

Die Funktion insertdict ruft wiederum lookdict_string auf (oder lookdict, wenn das Wörterbuch keinen Zeichenfolgenschlüssel enthält), wodurch nach einer freien Zelle in der Hash-Tabelle zum Einfügen gesucht wird. Dieselbe Funktion wird verwendet, um den Schlüssel während des Extrahierens zu finden.

Der anfängliche Index des Samples in dieser Funktion wird als Hash des Schlüssels geteilt, modulo die Größe der Tabelle (somit werden die unteren Bits des Hashs erfasst). Also:

>>> PyDict_MINSIZE = 8
>>> key = 123
>>> hash(key) % PyDict_MINSIZE
>>> 3

In Python wird dies mithilfe der logischen UND-Operation und einer Maske implementiert. Die Maske entspricht dem folgenden Wert: mask = PyDict_MINSIZE - 1.

>>> PyDict_MINSIZE = 8
>>> mask = PyDict_MINSIZE - 1
>>> key = 123
>>> hash(key) & mask
>>> 3

Dies erzeugt die niedrigstwertigen Bits des
Hashs : 2 ** i = PyDict_MINSIZE, daher ist i = 3, dh die drei niedrigstwertigen Bits sind ausreichend.
Hash (123) = 123 = 1111011 2
mask = PyDict_MINSIZE - 1 = 8 - 1 = 7 = 111 2
index = Hash (123) & mask = 1111011 2 & 111 2 = 011 2 = 3

Nachdem der Index berechnet wurde, wird die Zelle vom Index überprüft. Wenn sie nicht verwendet wird, wird ein Datensatz hinzugefügt (Hash, Schlüssel, Wert). Wenn diese Zelle jedoch aufgrund der Tatsache ausgelastet ist, dass ein anderer Datensatz denselben Hash aufweist (d. H. Eine Kollision aufgetreten ist), werden der Hash und der Schlüssel des eingefügten Datensatzes und des Datensatzes in der Zelle verglichen. Wenn der Hash und der Schlüssel für die Einträge übereinstimmen, wird davon ausgegangen, dass der Eintrag bereits im Wörterbuch vorhanden ist, und die Aktualisierung wird durchgeführt.

Dies erklärt den kniffligen Moment, der mit dem Hinzufügen von gleichen, aber unterschiedlichen Schlüsseltypen (z. B. float, int und complex) verbunden ist:

>>> 7.0 == 7 == (7+0j)
True
>>> d = {}
>>> d[7.0]='float'
>>> d
{7.0: 'float'}
>>> d[7]='int'
>>> d
{7.0: 'int'}
>>> d[7+0j]='complex'
>>> d
{7.0: 'complex'}
>>> type(d.keys()[0])

Das heißt, der Typ, der zuerst zum Wörterbuch hinzugefügt wurde, ist trotz der Aktualisierung der Schlüsseltyp. Dies liegt daran, dass die Hash-Implementierung für Float-Werte den Hash von int zurückgibt, wenn der Bruchteil 0.0 ist. Eine Beispiel-Hash-Berechnung für float, die in Python umgeschrieben wurde:

def float_hash(float_value):
    ...
    fractpart, intpart = math.modf(float_value)
    if fractpart == 0.0:
        return int_hash(int(float_value))  # использовать хэш int 
    ...

Und der Hash von complex gibt den Hash von float zurück. In diesem Fall wird nur der Hash des Realteils zurückgegeben, da der Imaginärteil Null ist:

def complex_hash(complex_value):
    hashreal = float_hash(complex_value.real)
    if hashreal == -1:
        return -1
    hashimag = float_hash(complex_value.imag)
    if hashimag == -1:
        return -1
    res = hashreal + 1000003 * hashimag
    res = handle_overflow(res)
    if res == -1:
        res = -2
    return res

Ein Beispiel:

>>> hash(7)
7
>>> hash(7.0)
7
>>> hash(7+0j)
7

Aufgrund der Tatsache, dass sowohl Hashes als auch Werte für alle drei Typen gleich sind, wird eine einfache Aktualisierung des Werts des gefundenen Datensatzes durchgeführt.

Hinweis zum Hinzufügen von Elementen: Python verhindert das Hinzufügen von Elementen zum Wörterbuch während der Iteration. Daher tritt ein Fehler auf, wenn versucht wird, ein neues Element hinzuzufügen:

>>> d = {'a': 1}
>>> for i in d:
...     d['new item'] = 123
...
Traceback (most recent call last):
  File "", line 1, in 
RuntimeError: dictionary changed size during iteration

Kehren wir zum Verfahren zum Hinzufügen eines Elements zum Wörterbuch zurück. Nach dem erfolgreichen Hinzufügen oder Aktualisieren eines Datensatzes in der Hash-Tabelle wird der nächste Kandidatendatensatz zum Einfügen verglichen. Wenn der Hash oder Schlüssel der Datensätze nicht übereinstimmt, beginnt die Prüfung. Sucht nach der "unbenutzten" einzufügenden Zelle. Diese Python-Implementierung verwendet eine zufällige (und wenn die Störungsvariable nullquadratisch ist) Prüfung. Wie oben beschrieben, wird bei zufälliger Prüfung der Index der nächsten Zelle auf pseudozufällige Weise ausgewählt. Der Datensatz wird der ersten gefundenen „nicht verwendeten“ Zelle hinzugefügt. Das heißt, zwei Schlüssel a und b, für die Hash (a) == Hash (b), aber a! = B kann leicht in einem Wörterbuch existieren. Wenn die Zelle am Anfangsindex der Probe "leer" ist, erfolgt eine Prüfung. Und wenn die erste gefundene Zelle "Null" ist, dann wird die "leere" Zelle wiederverwendet. Auf diese Weise können Sie gelöschte Zellen überschreiben und nicht verwendete Zellen beibehalten.

Es stellt sich heraus, dass die Indizes der zum Wörterbuch hinzugefügten Elemente von den Elementen abhängen, die bereits enthalten sind, und die Reihenfolge der Schlüssel für zwei Wörterbücher, die aus demselben Satz von Paaren (Schlüssel, Wert) bestehen, kann unterschiedlich sein und wird durch die Reihenfolge des Hinzufügens der Elemente bestimmt:

>>> d1 = {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}
>>> d2 = {'three': 3, 'two': 2, 'five': 5, 'four': 4, 'one': 1}
>>> d1 == d2
True
>>> d1.keys()
['four', 'three', 'five', 'two', 'one']
>>> d2.keys()
['four', 'one', 'five', 'three', 'two']

Dies erklärt, warum Wörterbücher in Python gespeicherte Paare (Schlüssel, Wert) in der Reihenfolge anzeigen, in der sie beim Anzeigen von Inhalten zum Wörterbuch hinzugefügt werden. Wörterbücher geben sie in der Reihenfolge in der Hash-Tabelle aus (d. H. In der Indexreihenfolge).

Betrachten Sie ein Beispiel:

>>> d = {}
>>> d['habr'] = 1



Bei Index 5 wurde eine Einfügung vorgenommen. Die Variablen ma_fill und ma_used wurden gleich 1.

>>> d['python'] = 2



Index 0 wurde eingefügt, die Variablen ma_fill und ma_used wurden gleich 2.

>>> d['dict'] = 3



Bei Index 4 wurde eine Einfügung vorgenommen. Die Variablen ma_fill und ma_used wurden gleich 3.
>>> d['article'] = 4



Index 1 wurde eingefügt, die Variablen ma_fill und ma_used wurden gleich 4.

>>> d['!!!'] = 5



Произошло следующее:
hash('!!!') = -1297030748
i = -1297030748 & 7 = 4
Но как видно из таблицы, индекс 4 уже занят записью с ключом 'dict'. То есть произошла коллизия. Начинается пробирование:
perturb = -1297030748
i = (i * 5) + 1 + perturb
i = (4 * 5) + 1 + (-1297030748) = -1297030727
index = -1297030727 & 7 = 1
Новый индекс пробы равен 1, но данный индекс тоже занят (записью с ключом 'article'). Произошла ещё одна коллизия, продолжаем пробирование:
perturb = perturb >> PERTURB_SHIFT
perturb = -1297030748 >> 5 = -40532211
i = (i * 5) + 1 + perturb
i = (-1297030727 * 5) + 1 + (-40532211) = -6525685845
index = -6525685845 & 7 = 3
Der neue Beispielindex ist 3 und da er nicht belegt ist, wird ein Eintrag mit der Taste '!!!' eingefügt. in die Zelle mit dem dritten Index. In diesem Fall wurde der Datensatz nach zwei Versuchen aufgrund von Kollisionen hinzugefügt. Die Variablen ma_fill und ma_used wurden gleich 5.

>>> d
{'python': 2, 'article': 4, '!!!': 5, 'dict': 3, 'habr': 1}

Wir versuchen, das sechste Element zum Wörterbuch hinzuzufügen.

>>> d[';)'] = 6



Nachdem Sie das sechste Element hinzugefügt haben, wird die Tabelle zu 2/3 gefüllt, und entsprechend ändert sich ihre Größe. Nachdem sich die Größe geändert hat (in diesem Fall wird sie um das Vierfache vergrößert), wird die Hash-Tabelle unter Berücksichtigung der neuen Größe vollständig neu erstellt. Alle "aktiven" Zellen werden neu verteilt und "leere" und "nicht verwendete" Zellen werden ignoriert.

Die Größe der Hash-Tabelle ist jetzt 32, und die Variablen ma_fill und ma_used sind jetzt gleich 6. Wie Sie sehen, hat sich die Reihenfolge der Elemente vollständig geändert:

>>> d
{'!!!': 5, 'python': 2, 'habr': 1, 'dict': 3, 'article': 4, ';)': 6}


Elementsuche


Die Suche nach Einträgen in der Dictionary-Hash-Tabelle ist ähnlich, beginnend mit Zelle i, wo i vom Schlüssel-Hash abhängt. Wenn der Hash und der Schlüssel nicht mit dem Hash und dem Schlüssel des gefundenen Datensatzes übereinstimmen (dh es gab eine Kollision und Sie müssen den entsprechenden Datensatz finden), wird der Test gestartet, der fortgesetzt, bis ein Datensatz gefunden wird, für den der Hash und der Schlüssel übereinstimmen. Wenn alle Zellen angezeigt wurden, der Datensatz jedoch nicht gefunden wurde, wird ein Fehler zurückgegeben.

>>> d = {'a': 123, 'b': 345, 'c': 678}
>>> d['x']
Traceback (most recent call last):
  File "", line 1, in 
KeyError: 'x'


Füllfaktor der Hash-Tabelle


Die Größe der Tabelle ändert sich, wenn 2/3 ausgefüllt werden. Das heißt, für die Anfangsgröße der Dictionary-Hash-Tabelle von 8 tritt die Änderung ein, nachdem 6 Elemente hinzugefügt wurden.

>>> 8 * 2.0 / 3
5.333333333333333

Gleichzeitig wird die Hash-Tabelle unter Berücksichtigung ihrer neuen Größe neu erstellt, und dementsprechend ändern sich die Indizes aller Datensätze.

Der Wert 2/3 der Größe wurde als optimal gewählt, damit das Abtasten nicht zu lange dauert, dh das Einfügen eines neuen Datensatzes ging schnell. Das Erhöhen dieses Werts führt dazu, dass das Wörterbuch dichter mit Einträgen gefüllt ist, was wiederum die Anzahl der Kollisionen erhöht. Eine Abnahme erhöht die Spärlichkeit von Datensätzen zu Lasten einer Zunahme der von ihnen belegten Prozessor-Cache-Zeilen und zu Lasten einer Zunahme des Gesamtspeichers. Das Überprüfen des Füllens der Tabelle erfolgt in einem sehr zeitkritischen Code. Versuche, die Prüfung komplexer zu gestalten (z. B. durch Ändern des Füllfaktors für verschiedene Größen der Hash-Tabelle), verringerten die Leistung.

So überprüfen Sie, ob sich die Größe des Wörterbuchs tatsächlich ändert:

>>> d = dict.fromkeys(range(5))
>>> d.__sizeof__()
248
>>> d = dict.fromkeys(range(6))
>>> d.__sizeof__()
1016

Das Beispiel gibt die Größe des gesamten PyDictObject für die 64-Bit-Version des Betriebssystems zurück.
Die Anfangsgröße der Tabelle ist 8. Wenn die Anzahl der gefüllten Zellen 6 ist (dh mehr als 2/3 der Größe), wird die Größe der Tabelle auf 32 erhöht. Wenn die Anzahl 22 ist, wird sie auf 128 erhöht. Bei 86 wird sie auf 512 erhöht , bei 342 - bis 2048 und so weiter.

Verhältnis zur Erhöhung der Tischgröße


Der Koeffizient zum Erhöhen der Tabellengröße bei Erreichen des maximalen Füllstands beträgt 4, wenn die Tabellengröße weniger als 50.000 Elemente beträgt, und 2 für größere Tabellen. Dieser Ansatz kann für speicherbegrenzte Anwendungen nützlich sein.

Das Vergrößern der Tabelle verbessert die durchschnittliche Spärlichkeit, dh die Streuung der Einträge in der Wörterbuchtabelle (Reduzierung von Kollisionen) aufgrund einer Zunahme der verbrauchten Speicherkapazität und der Geschwindigkeit von Iterationen, und verringert auch die Anzahl teurer Speicherzuweisungsoperationen, wenn die Größe für ein wachsendes Wörterbuch geändert wird.

Normalerweise kann das Hinzufügen eines Elements zum Wörterbuch seine Größe in Abhängigkeit von der aktuellen Größe des Wörterbuchs um das Vier- oder Zweifache erhöhen. Es ist jedoch auch möglich, dass die Größe des Wörterbuchs abnimmt. Diese Situation kann auftreten, wenn ma_fill (die Anzahl der Nicht-Null-Schlüssel, die Summe der "aktiven" und "leeren" Zellen) viel größer ist als ma_used (die Anzahl der "aktiven" Zellen), dh viele Schlüssel wurden gelöscht.

Element löschen


Wenn ein Element aus dem Wörterbuch gelöscht wird, wird die PyDict_DelItem-Funktion aufgerufen.
Das Löschen aus dem Wörterbuch erfolgt per Schlüssel, obwohl in Wirklichkeit der Speicher nicht freigegeben wird. In dieser Funktion wird der Hash-Wert des Schlüssels berechnet, und dann wird ein Datensatz in der Hash-Tabelle mit derselben lookdict_string- oder lookdict-Funktion durchsucht. Wenn ein Datensatz mit einem solchen Schlüssel und einem solchen Hash gefunden wird, wird der Schlüssel dieses Datensatzes auf "leer" (dh me_key = dummy) und der Datensatzwert auf NULL (me_value = NULL) gesetzt. Danach verringert sich die Variable ma_used um eins und ma_fill bleibt unverändert. Wird der Datensatz nicht gefunden, wird ein Fehler zurückgegeben.

>>> del d['!!!']



Nach dem Löschen wurde die Variable ma_used gleich 4 und ma_fill blieb gleich 5, da die Zelle nicht gelöscht, sondern nur als "leer" markiert wurde und die Zelle in der Hash-Tabelle weiterhin belegt.

Hash-Randomisierung


Wenn Sie Python starten, können Sie mit der Option -R ein Pseudozufalls-Salt verwenden. In diesem Fall ist der Hash von Werten von Typen wie Zeichenfolgen, Puffer, Bytes und Datum / Uhrzeit-Objekten (Datum, Uhrzeit und Datum / Uhrzeit) zwischen den Aufrufen des Interpreters nicht vorhersehbar. Diese Methode wird als Schutz vor DoS-Angriffen vorgeschlagen.

Referenzen


github.com/python/cpython/blob/2.7/Objects/dictobject.c
github.com/python/cpython/blob/2.7/Include/dictobject.h
github.com/python/cpython/blob/2.7/Objects/dictnotes.txt
www.shutupandship.com/2012/02/how-hash-collisions-are-resolved-in.html
www.laurentluce.com/posts/python-dictionary-implementation
rhodesmill.org/brandon/slides/2010-03-pycon
www.slideshare.net/MinskPythonMeetup/ss-26224561 – Dictionary в Python. По мотивам Objects/dictnotes.txt – SlideShare (Cyril notorca Lashkevich)
www.youtube.com/watch?v=JhixzgVpmdM – Видео доклада «Dictionary в Python. По мотивам Objects/dictnotes.txt»

Jetzt auch beliebt: