Ich versuche die Python- hashFunktion unter der Haube zu verstehen . Ich habe eine benutzerdefinierte Klasse erstellt, in der alle Instanzen denselben Hashwert zurückgeben.
class C:
def __hash__(self):
return 42
Ich habe nur angenommen, dass immer nur eine Instanz der oben genannten Klasse in einer sein dictkann, aber tatsächlich dictkann a mehrere Elemente mit demselben Hash haben.
c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elementsIch habe ein wenig mehr experimentiert und festgestellt, dass, wenn ich die __eq__Methode so überschreibe , dass alle Instanzen der Klasse gleich sind, dictnur eine Instanz zulässig ist.
class D:
def __hash__(self):
return 42
def __eq__(self, other):
return True
p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 elementIch bin gespannt, wie ein dictElement mehrere Elemente mit demselben Hash haben kann.
Antworten:
Eine detaillierte Beschreibung der Funktionsweise von Pythons Hashing finden Sie in meiner Antwort auf Warum ist die frühe Rückkehr langsamer als sonst?
Grundsätzlich wird der Hash verwendet, um einen Platz in der Tabelle auszuwählen. Wenn sich im Slot ein Wert befindet und der Hash übereinstimmt, werden die Elemente verglichen, um festzustellen, ob sie gleich sind.
Wenn der Hash nicht übereinstimmt oder die Elemente nicht gleich sind, versucht es einen anderen Slot. Es gibt eine Formel, um dies auszuwählen (die ich in der Antwort, auf die verwiesen wird, beschreibe), und sie zieht allmählich nicht verwendete Teile des Hash-Werts ein. Sobald es sie alle aufgebraucht hat, arbeitet es sich schließlich durch alle Slots in der Hash-Tabelle. Das garantiert, dass wir irgendwann entweder einen passenden Gegenstand oder einen leeren Platz finden. Wenn die Suche einen leeren Platz findet, fügt sie den Wert ein oder gibt auf (je nachdem, ob wir einen Wert hinzufügen oder erhalten).
Es ist wichtig zu beachten, dass es keine Listen oder Buckets gibt: Es gibt nur eine Hash-Tabelle mit einer bestimmten Anzahl von Slots, und jeder Hash wird verwendet, um eine Folge von Kandidaten-Slots zu generieren.
quelle
Hier ist alles über Python-Diktate, die ich zusammenstellen konnte (wahrscheinlich mehr als jeder andere gerne wissen würde; aber die Antwort ist umfassend). Ein Gruß an Duncan, der darauf hingewiesen hat, dass Python-Diktate Slots verwenden und mich durch dieses Kaninchenloch führen.
O(1)nach Index suchen können ).Die folgende Abbildung ist eine logische Darstellung einer Python-Hash-Tabelle. In der folgenden Abbildung sind 0, 1, ..., i, ... links Indizes der Slots in der Hash-Tabelle (sie dienen nur zur Veranschaulichung und werden offensichtlich nicht zusammen mit der Tabelle gespeichert!).
Wenn ein neues Diktat initialisiert wird, beginnt es mit 8 Slots . (siehe dictobject.h: 49 )
ider auf dem Hash des Schlüssels basiert. CPython verwendet initiali = hash(key) & mask. Womask = PyDictMINSIZE - 1, aber das ist nicht wirklich wichtig. Beachten Sie nur, dass der anfängliche Steckplatz i, der überprüft wird, vom Hash des Schlüssels abhängt .<hash|key|value>). Aber was ist, wenn dieser Steckplatz belegt ist? Höchstwahrscheinlich, weil ein anderer Eintrag denselben Hash hat (Hash-Kollision!)==Vergleich nicht denisVergleich) des Eintrags im Steckplatz mit dem Schlüssel des aktuell einzufügenden Eintrags ( dictobject.c: 337 , 344 & ndash ; 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 .Los geht's! Die Python-Implementierung von dict überprüft
==beim Einfügen von Elementen sowohl die Hash-Gleichheit zweier Schlüssel als auch die normale Gleichheit ( ) der Schlüssel. Wenn also zwei Schlüssel vorhanden sindaundbundhash(a)==hash(b), abera!=b, dann können beide in einem Python-Dikt harmonisch existieren. Aber wennhash(a)==hash(b)unda==b, dann können sie nicht beide im selben Diktat sein.Da wir nach jeder Hash-Kollision prüfen müssen, besteht ein Nebeneffekt zu vieler Hash-Kollisionen darin, dass die Suchvorgänge und Einfügungen sehr langsam werden (wie Duncan in den Kommentaren hervorhebt ).
Ich denke, die kurze Antwort auf meine Frage lautet: "Weil es so im Quellcode implementiert ist;)"
Obwohl dies gut zu wissen ist (für Geek-Punkte?), Bin ich mir nicht sicher, wie es im wirklichen Leben verwendet werden kann. Denn wenn Sie nicht versuchen, etwas explizit zu brechen, warum sollten zwei Objekte, die nicht gleich sind, denselben Hash haben?
quelle
Bearbeiten : Die Antwort unten ist eine der möglichen Möglichkeiten, um mit Hash-Kollisionen umzugehen. Es ist jedoch nicht so, wie Python es tut. Pythons Wiki, auf das unten verwiesen wird, ist ebenfalls falsch. Die beste Quelle, die @Duncan unten angibt, ist die Implementierung selbst: https://github.com/python/cpython/blob/master/Objects/dictobject.c Ich entschuldige mich für die Verwechslung.
Es speichert eine Liste (oder einen Bucket) von Elementen im Hash und durchläuft diese Liste dann, bis der tatsächliche Schlüssel in dieser Liste gefunden wird. Ein Bild sagt mehr als tausend Worte:
Hier sehen Sie
John SmithundSandra Deebeide Hash zu152. Eimer152enthält beide. Beim Nachschlagen wirdSandra Deezuerst die Liste im Bucket gefunden152, dann wird diese Liste durchlaufen, bis sieSandra Deegefunden wird und zurückkehrt521-6955.Folgendes ist falsch, es ist nur hier für den Kontext: Im Python-Wiki finden Sie (Pseudo?) Code, wie Python die Suche durchführt.
Es gibt tatsächlich mehrere mögliche Lösungen für dieses Problem. Eine schöne Übersicht finden Sie im Wikipedia-Artikel: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
quelle
Hash-Tabellen müssen im Allgemeinen Hash-Kollisionen berücksichtigen! Sie werden Pech haben und zwei Dinge werden irgendwann zu derselben Sache führen. Darunter befindet sich eine Reihe von Objekten in einer Liste von Elementen, die denselben Hash-Schlüssel haben. Normalerweise enthält diese Liste nur eines, aber in diesem Fall werden sie weiterhin in derselben Liste gestapelt. Der einzige Weg, wie es weiß, dass sie unterschiedlich sind, ist durch den Gleichheitsoperator.
In diesem Fall nimmt Ihre Leistung mit der Zeit ab, weshalb Ihre Hash-Funktion so "zufällig wie möglich" sein soll.
quelle
Im Thread habe ich nicht gesehen, was Python genau mit Instanzen einer benutzerdefinierten Klasse macht, als wir es als Schlüssel in ein Wörterbuch einfügen. Lesen wir eine Dokumentation: Sie erklärt, dass nur hashbare Objekte als Schlüssel verwendet werden können. Hashable sind alle unveränderlichen integrierten Klassen und alle benutzerdefinierten Klassen.
Wenn Sie also ständig __hash__ in Ihrer Klasse haben, aber keine __cmp__- oder __eq__- Methode bereitstellen, sind alle Ihre Instanzen für das Wörterbuch ungleich. Wenn Sie dagegen eine __cmp__- oder __eq__- Methode bereitstellen, aber keine __hash__-Methode bereitstellen, sind Ihre Instanzen in Bezug auf das Wörterbuch immer noch ungleich.
Ausgabe
quelle