Warum kann ein Python-Diktat mehrere Schlüssel mit demselben Hash haben?

90

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 elements

Ich 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 element

Ich bin gespannt, wie ein dictElement mehrere Elemente mit demselben Hash haben kann.

Praveen Gollakota
quelle
3
Wie Sie selbst festgestellt haben, können Sets und Dicts mehrere Objekte mit gleichen Hashes enthalten, wenn die Objekte selbst nicht gleich sind. Was fragst du? Wie haben Tabellen funktioniert? Das ist eine ganz allgemeine Frage mit viel vorhandenem Material ...
@delnan Ich habe mehr darüber nachgedacht, nachdem ich die Frage gestellt habe. dass dieses Verhalten nicht auf Python beschränkt werden kann. Und du hast recht. Ich denke, ich sollte tiefer in die allgemeine Hash-Tabellenliteratur eintauchen. Vielen Dank.
Praveen Gollakota

Antworten:

55

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.

Duncan
quelle
7
Vielen Dank, dass Sie mich in die richtige Richtung bezüglich der Implementierung von Hash-Tabellen geführt haben. Ich habe viel mehr über Hash-Tabellen gelesen, als ich jemals wollte, und meine Ergebnisse in einer separaten Antwort erläutert. stackoverflow.com/a/9022664/553995
Praveen Gollakota
112

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.

  • Python-Wörterbücher werden als Hash-Tabellen implementiert .
  • Hash-Tabellen müssen Hash-Kollisionen zulassen, dh selbst wenn zwei Schlüssel denselben Hash-Wert haben, muss die Implementierung der Tabelle eine Strategie zum Einfügen und Abrufen der Schlüssel- und Wertepaare haben.
  • Python dict verwendet 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 O(1)nach Index suchen können ).
  • In jedem Slot in der Tabelle kann nur ein Eintrag gespeichert werden. Das ist wichtig
  • Jeder Eintrag in der Tabelle ist eigentlich eine Kombination der drei Werte -. Dies ist als C-Struktur implementiert (siehe dictobject.h: 51-56 ).
  • 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!).

    # 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 initial i = hash(key) & mask. Wo mask = 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 .
  • 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 Steckplatz belegt ist, vergleicht CPython (und sogar PyPy) den Hash UND den Schlüssel (mit Vergleich meine ich ==Vergleich nicht den isVergleich) 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 .
  • Das Prüfen bedeutet nur, dass die Steckplätze nach Steckplätzen durchsucht werden, um einen leeren Steckplatz zu finden. Technisch könnten wir einfach eins nach dem anderen gehen, i + 1, i + 2, ... und das erste verfügbare verwenden (das ist lineare Abtastung). 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 Slots 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 wird die Größe des Diktats geändert, wenn es zu zwei Dritteln voll ist. Dadurch wird vermieden, dass Suchvorgänge verlangsamt werden. (siehe dictobject.h: 64-65 )

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 sind aund bund hash(a)==hash(b), aber a!=b, dann können beide in einem Python-Dikt harmonisch existieren. Aber wenn hash(a)==hash(b) und a==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?

Praveen Gollakota
quelle
8
Dies erklärt, wie das Auffüllen des Wörterbuchs funktioniert. Was aber, wenn beim Abrufen eines key_value-Paares eine Hash-Kollision auftritt? Nehmen wir an, wir haben 2 Objekte A und B, die beide auf 4 hashen. Also wird zuerst A Slot 4 und dann B Slot durch zufällige Prüfung zugewiesen. Was passiert, wenn ich B abrufen möchte? B-Hashes auf 4, also prüft Python zuerst Steckplatz 4, aber der Schlüssel stimmt nicht überein, sodass er A nicht zurückgeben kann. Da der Steckplatz von B durch zufällige Prüfung zugewiesen wurde, wie wird B erneut zurückgegeben? in O (1) Zeit?
Sayantankhan
4
@ Bolt64 die zufällige Prüfung ist nicht wirklich zufällig. Für die gleichen Schlüsselwerte folgt es immer der gleichen Sequenz von Sonden, so dass es schließlich B findet. Wörterbücher sind nicht garantiert O (1), wenn Sie viele Kollisionen bekommen, können sie länger dauern. Mit älteren Versionen von Python ist es einfach, eine Reihe von Schlüsseln zu erstellen, die kollidieren. In diesem Fall werden Wörterbuchsuchen zu O (n). Dies ist ein möglicher Vektor für DoS-Angriffe, sodass neuere Python-Versionen das Hashing ändern, um es absichtlich schwieriger zu machen.
Duncan
2
@Duncan was ist, wenn A gelöscht wird und wir dann eine Suche für B durchführen? Ich denke, Sie löschen Einträge nicht wirklich, sondern markieren sie als gelöscht? Das würde bedeuten, dass die Diktate nicht für fortlaufende Einfügungen und Löschungen geeignet sind ....
gen-ys
2
@ gen-ys yes gelöschte und nicht verwendete werden für die Suche unterschiedlich behandelt. Nicht verwendet stoppt die Suche nach einer Übereinstimmung, gelöscht jedoch nicht. Beim Einfügen werden gelöschte oder nicht verwendete Slots als leere Slots behandelt, die verwendet werden können. Kontinuierliche Einfügungen und Löschungen sind in Ordnung. Wenn die Anzahl der nicht verwendeten (nicht gelöschten) Slots zu niedrig ist, wird die Hash-Tabelle auf dieselbe Weise neu erstellt, als wäre sie für die aktuelle Tabelle zu groß geworden.
Duncan
1
Dies ist keine sehr gute Antwort auf den Kollisionspunkt, den Duncan zu beheben versuchte. Es ist eine besonders schlechte Antwort auf die Referenz für die Implementierung Ihrer Frage. Das Wichtigste, um dies zu verstehen, ist, dass Python bei einer Kollision erneut versucht, mithilfe einer Formel den nächsten Versatz in der Hash-Tabelle zu berechnen. Wenn der Schlüssel beim Abrufen nicht identisch ist, wird dieselbe Formel verwendet, um den nächsten Versatz nachzuschlagen. Es ist nichts Zufälliges daran.
Evan Carroll
20

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:

Hash-tabelle

Hier sehen Sie John Smithund Sandra Deebeide Hash zu 152. Eimer 152enthält beide. Beim Nachschlagen wird Sandra Deezuerst die Liste im Bucket gefunden 152, dann wird diese Liste durchlaufen, bis sie Sandra Deegefunden wird und zurückkehrt 521-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

Rob Wouters
quelle
Vielen Dank für die Erklärung und insbesondere für den Link zum Python-Wiki-Eintrag mit dem Pseudocode!
Praveen Gollakota
2
Entschuldigung, aber diese Antwort ist einfach falsch (ebenso der Wiki-Artikel). Python speichert keine Liste oder einen Bucket von Elementen im Hash: Es speichert genau ein Objekt in jedem Slot der Hash-Tabelle. Wenn der Slot, den es zuerst zu verwenden versucht, belegt ist, wählt es einen anderen Slot (zieht nicht verwendete Teile des Hashs so lange wie möglich ein) und dann einen anderen und einen anderen. Da keine Hash-Tabelle mehr als ein Drittel voll ist, muss sie eventuell einen verfügbaren Slot finden.
Duncan
@Duncan, Pythons Wiki sagt, dass es auf diese Weise implementiert ist. Ich würde mich freuen, eine bessere Quelle zu finden. Die Seite wikipedia.org ist definitiv nicht falsch, sondern nur eine der möglichen Lösungen.
Rob Wouters
@Duncan Kannst du bitte erklären ... unbenutzte Teile des Hash so lange wie möglich einziehen? Alle Hashes in meinem Fall werden mit 42 bewertet. Danke!
Praveen Gollakota
@PraveenGollakota Folgen Sie dem Link in meiner Antwort, der ausführlich erklärt, wie der Hash verwendet wird. Bei einem Hash von 42 und einer Tabelle mit 8 Slots werden zunächst nur die niedrigsten 3 Bits verwendet, um Slot Nummer 2 zu finden. Wenn dieser Slot jedoch bereits verwendet wird, kommen die verbleibenden Bits ins Spiel. Wenn zwei Werte genau den gleichen Hash haben, geht der erste in den ersten versuchten Slot und der zweite in den nächsten Slot. Wenn es 1000 Werte mit identischen Hashes gibt, versuchen wir am Ende 1000 Slots, bevor wir den Wert finden und die Wörterbuchsuche sehr, sehr langsam wird!
Duncan
4

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.

Donald Miner
quelle
2

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.

Benutzerdefinierte Klassen haben standardmäßig die Methoden __cmp __ () und __hash __ (). Mit ihnen vergleichen alle Objekte ungleich (außer mit sich selbst) und x .__ hash __ () gibt ein von id (x) abgeleitetes Ergebnis zurück.

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.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Ausgabe

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}
checkraise
quelle