Eine kurze Diskussion über Wörterbücher und Hash-Tabellen in Python und die Lösung von Hash-Konflikten

Der Inhalt dieses Artikels ist eine kurze Diskussion über Wörterbücher und Hash-Tabellen in Python und die Lösung von Hash-Konflikten. Ich hoffe, dass er für Sie hilfreich ist.

Python verwendet Hash-Tabellen, um Diktate zu implementieren.

Eine Hash-Tabelle ist eigentlich ein Sparse-Array (ein Array, das immer leere Elemente enthält, wird als Sparse-Array bezeichnet). In allgemeinen Büchern werden die Einheiten in einer Hash-Tabelle normalerweise als Buckets bezeichnet. existieren dict In der Hash-Tabelle belegt jedes Schlüssel-Wert-Paar ein Tabellenelement, und jedes Tabellenelement besteht aus zwei Teilen, einem ist ein Verweis auf den Schlüssel und der andere ist ein Verweis auf den Wert. Da jede Tabellenzelle die gleiche Größe hat, können Sie eine Tabellenzelle anhand des Offsets lesen.

Python wird versuchen sicherzustellen, dass etwa ein Drittel der Tabellenelemente leer sind. Wenn dieser Schwellenwert fast erreicht ist, wird die ursprüngliche Hash-Tabelle erweitert und in eine größere Hash-Tabelle kopiert.

Wenn Sie ein Objekt in eine Hash-Tabelle einfügen möchten, müssen Sie zunächst den Hash-Wert des Elementschlüssels berechnen. Dies erfordert, dass der Schlüssel hashbar sein muss.

Ein hashbares Objekt muss die folgenden Bedingungen erfüllen:

Unterstützt die Funktion hash() und der von der Methode __hash__() erhaltene Hashwert bleibt unverändert.

Unterstützt die Gleichheitserkennung durch die Methode __eq__().

Wenn a == b wahr ist, dann ist hash(a) == hash(b) auch wahr.

Im Folgenden wird hauptsächlich der Hash-Tabellenalgorithmus erläutert.

Um den Schlüssel zu bekommen Der Wert search_value entspricht search_key. Python ruft zur Berechnung zunächst hash(search_key) auf Suchschlüssel Der Hash-Wert des Werts, die niedrigsten Ziffern dieses Werts werden als Offsets verwendet und das Tabellenelement wird in der Hash-Tabelle durchsucht (die spezifische Zahl hängt von der Größe der aktuellen Hash-Tabelle ab). Wenn das gefundene Tabellenelement leer ist, wird KeyError geworfen Ausnahme; wenn es nicht leer ist, gibt es ein Paar „found_key:found_value“ im Tabellenelement, überprüfen Sie „search_key“ und „found_key“. Ob sie gleich sind. Wenn ja, wird „found_value“ zurückgegeben. Wenn sie nicht gleich sind, spricht man von einer Hash-Kollision.

Um den Hash-Konflikt zu lösen, nimmt der Algorithmus noch ein paar Bits im Hash-Wert, verarbeitet ihn dann mit einer speziellen Methode und verwendet den erhaltenen neuen Wert als Offset für die Suche Das Hash-Tabellenelement: Wenn das gefundene Tabellenelement leer ist, wird auch eine KeyError-Ausnahme ausgelöst, wenn es nicht leer ist. Vergleichen Sie die Schlüssel, um festzustellen, ob sie konsistent sind, und geben Sie den entsprechenden Wert zurück, wenn sie konsistent sind Wenn erneut ein Hash-Konflikt gefunden wird, wiederholen Sie die obigen Schritte.

Der Vorgang zum Hinzufügen eines neuen Elements ist fast der gleiche wie oben, mit der Ausnahme, dass das neue Element eingefügt wird, wenn ein leeres Tabellenelement gefunden wird. Wenn es nicht leer ist, wird der Hash wiederholt und Die Suche wird fortgesetzt.

Gehen Sie dorthin Wenn dem Diktat ein neues Element hinzugefügt wird und ein Hash-Konflikt auftritt, kann das neue Element so angeordnet werden, dass es an einem anderen Ort gespeichert wird. Es wird also die folgende Situation eintreten: dict([key1, value1], [key2, value2]) und dict([key2, value2], [key1, value1]) Beim Vergleich sind zwei Wörterbücher gleich, aber wenn die Hashes von Schlüssel1 und Schlüssel2 in Konflikt geraten, ist die Reihenfolge der beiden Schlüssel im Wörterbuch unterschiedlich.

Wann immer, geh Fügen Sie neue Schlüssel zu dict, Python hinzu Der Parser kann entscheiden, das Wörterbuch zu erweitern. Das Ergebnis der Erweiterung besteht darin, eine größere Hash-Tabelle zu erstellen und vorhandene Elemente im Wörterbuch zur neuen Hash-Tabelle hinzuzufügen. Während dieses Vorgangs können neue Hash-Konflikte auftreten, die dazu führen, dass sich die Reihenfolge der Schlüssel in der neuen Hash-Tabelle ändert. Was passiert, wenn Sie ein Wörterbuch durchlaufen und ihm gleichzeitig neue Schlüssel hinzufügen? Leider wurde die Kapazität erweitert, leider hat sich die Reihenfolge der Tasten geändert orz.

Da die Hash-Tabelle spärlich sein muss, muss ihr Platzverbrauch viel größer sein. Dies ist ein typischer Kompromiss zwischen Platz und Zeit.

Das obige ist der detaillierte Inhalt vonEine kurze Diskussion über Wörterbücher und Hash-Tabellen in Python und die Lösung von Hash-Konflikten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!