Hashcodes und Hashfunktionen

Kurz gesagt: Ein Hashcode ist eine Zahl, die hash() aus dem Schlüssel berechnet; dict und set wählen damit, wo sie suchen, und finden so einen Schlüssel auch unter einer Million schnell.

Problem

Der Platz wurde zweimal verkauft

Die Theaterkasse hält die verkauften Plätze in einer Map: Platz → Name des Zuschauers. Ein Platz ist eine Klasse mit Reihe und Nummer:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

bookings = {}
bookings[Seat(5, 12)] = "Maria"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Jonas"
print(len(bookings))

Ausgabe

None
1
2

Maria hat Platz 5/12 gekauft, aber get mit demselben Platz liefert None. Dann kauft Jonas denselben Platz, und die Map hat jetzt zwei Schlüssel 5/12. Warum?

Die Idee

Hash: eine Zahl aus dem Schlüssel

Ein Dictionary vergleicht den Schlüssel nicht mit allen anderen. Es berechnet aus dem Schlüssel eine ganze Zahl und weiß daraus, wo es suchen muss. Diese Zahl heißt Hash (Hashcode), und die eingebaute Funktion hash() gibt sie zurück. Sie ruft die Methode __hash__ des Objekts auf.

print(hash("Maria") == hash("Maria"))
print(hash("Maria") == hash("Marie"))
print(hash("Maria") == hash("maria"))
print(hash(1004))

Ausgabe

True
False
False
1004

• Innerhalb eines Laufs gibt derselbe Text dieselbe Zahl.
• Eine kleine Änderung gibt eine andere Zahl: „Maria“, „Marie“ und „maria“ sind drei verschiedene Hashes.
• Der Hash einer ganzen Zahl ist die Zahl selbst.
• Ein Hash ist schnell berechnet, egal wie viele Schlüssel im Dictionary sind.

Die Zahl selbst wird für Text hier absichtlich nicht ausgegeben. Python berechnet den Hash von Text bei jedem Lauf des Programms anders, du würdest also eine andere bekommen. Die Vergleiche kommen jedes Mal gleich heraus.

Die Methode, die die Zahl macht, heißt Hashfunktion.

Genauer, für Neugierige

• Warum ändert sich der Hash von Text? Wäre er im Voraus bekannt, könnte jemand einem Server Tausende Schlüssel mit demselben Hash schicken und das Dictionary langsam machen. Deshalb wählt Python bei jedem Lauf ein zufälliges „Salz“. Du kannst es mit der Umgebungsvariablen PYTHONHASHSEED festlegen, aber ein Programm verlässt sich nicht auf die Zahl selbst.
• Eine Ausnahme bei ganzen Zahlen: hash(-1) ist -2. In der Karte über Kollisionen siehst du, warum das interessant ist.

• Kryptografische Hashfunktionen wie SHA-256 sind etwas anderes. Sie geben ein langes Ergebnis, und es ist praktisch unmöglich, zwei Texte mit demselben Hash zu finden. Deshalb prüft man mit ihnen, ob eine Datei nicht verändert wurde, und speichert damit Passwörter. hash() ist für schnelles Suchen da und gibt keinen solchen Schutz.

Sieh es dir an

Die Buckets

Innen ist ein dict ein Array von Buckets. Die Nummer des Buckets für einen Schlüssel ist der Rest des Hashs bei der Division durch die Anzahl der Buckets. Der Hash von Text ändert sich bei jedem Lauf, deshalb sind die Schlüssel hier Bestellnummern: Bei ihnen ist der Hash die Zahl selbst:

keys = [1007, 2043, 3010, 4051]
buckets = 8
for key in keys:
    h = hash(key)
    index = h % buckets
    print(f"{key} -> {h} -> Bucket {index}")

Schritt für Schritt, in Worten

1. Vier Schlüssel (Bestellnummern) und acht leere Buckets, nummeriert von 0 bis 7.
2. hash(1007) ist die Zahl selbst, 1007. Der Rest bei der Division durch 8 ist 7: Das ist der Bucket.
3. 2043 ergibt Bucket 3.
4. 3010 ergibt Bucket 2.
5. 4051 landet auch in Bucket 3: eine Kollision. Hier ist sie als Kette gezeichnet, wie in Java. Ein dict in CPython sucht stattdessen einen anderen freien Platz.
6. Suche nach 4051: dieselbe Zahl, derselbe Bucket 3. == mit 2043: nein. Mit 4051: ja.

• Das Schreiben bookings[key] = … berechnet den Bucket und legt das Paar dort ab. Die Suche berechnet denselben Bucket und sucht nur dort. Deshalb ist sie auch mit einer Million Schlüssel schnell.
• In Python gibt % mit einem positiven Teiler nie eine negative Zahl, auch wenn der Hash negativ ist: -7 % 8 ist 1. Eine Bucket-Nummer kann nicht negativ sein.
• 2043 und 4051 sind in Bucket 3 gelandet. Das heißt Kollision. Darum geht es in der nächsten Karte.

Genauer, für Neugierige

• In CPython ist die Anzahl der Buckets eines Dictionarys ebenfalls eine Zweierpotenz, und die Suche beginnt bei den letzten Bits des Hashs. Das ist ein schneller Rest der Division durch die Anzahl der Buckets.

print(-7 % 8)

Ausgabe

1

Probier es aus

Welcher Bucket?

Der Hash einer ganzen Zahl ist die Zahl selbst. Die Bestellnummern kommen in eine Map mit 4 Buckets.

Was gibt das Programm aus?

order_ids = [6, 10, 13, 21]
for order_id in order_ids:
    print(f"{order_id} -> Bucket {hash(order_id) % 4}")

Antwort

6 -> Bucket 2
10 -> Bucket 0
13 -> Bucket 1
21 -> Bucket 3

6 -> Bucket 6
10 -> Bucket 10
13 -> Bucket 13
21 -> Bucket 21

6 -> Bucket 1
10 -> Bucket 2
13 -> Bucket 3
21 -> Bucket 4

6 -> Bucket 2
10 -> Bucket 2
13 -> Bucket 1
21 -> Bucket 1

Prüfen

Die Idee

Kollision: hash findet den Platz, == findet den Schlüssel

Verschiedene Schlüssel können denselben Hash haben. In Python ist das bekannteste Beispiel mit Zahlen:

print(hash(-1), hash(-2))

codes = {}
codes[-1] = "Minus eins"
codes[-2] = "Minus zwei"
print(codes[-1], codes[-2])

Ausgabe

-2 -2
Minus eins Minus zwei

Die beiden Schlüssel haben denselben Hash, aber das Dictionary verwechselt sie nicht. In CPython hält ein Bucket keine Liste von Paaren: Ist der Platz von einem anderen Schlüssel belegt, probiert das Dictionary nach einer Formel einen anderen Platz, bis es den Schlüssel oder einen leeren Platz findet. An jedem Platz vergleicht es die Schlüssel mit ==.

Die zwei Schritte arbeiten also so:

1. hash() sagt, wo die Suche beginnt.
2. == sagt, welcher der Schlüssel der gesuchte ist.

Jetzt ist klar, was mit dem Theaterplatz passiert ist. Seat hat weder __eq__ noch __hash__, also nutzt es die voreingestellten aus object. Dort ist == dasselbe wie is, und der Hash ist für jedes Objekt anders. Die beiden Objekte Seat(5, 12) sind zwei verschiedene Objekte, also auch zwei verschiedene Schlüssel.

Die Idee

Der Vertrag: __eq__ und __hash__ zusammen

Seat muss sagen, wann zwei Plätze derselbe Platz sind (__eq__), und gleichen Plätzen denselben Hash geben (__hash__):

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number

    def __hash__(self):
        return hash((self.row, self.number))

Mit demselben Programm wie in der ersten Karte:

bookings = {}
bookings[Seat(5, 12)] = "Maria"

print(bookings.get(Seat(5, 12)))
print(len(bookings))
bookings[Seat(5, 12)] = "Jonas"
print(len(bookings))

Ausgabe

Maria
1
1

Die Regeln, die Python erwartet:

• Wenn a == b, dann hash(a) == hash(b). Immer.
• Wenn die Hashes gleich sind, können die Objekte verschieden sein. Das ist eine Kollision.
• Wenn du __eq__ schreibst, schreib auch __hash__, mit denselben Attributen.

Schreibst du nur __eq__, lässt Python dich den Fehler nicht still machen. Es entfernt den Hash aus der Klasse, und so ein Objekt kann kein Schlüssel sein:

class Seat:
    def __init__(self, row, number):
        self.row = row
        self.number = number

    def __eq__(self, other):
        if not isinstance(other, Seat):
            return NotImplemented
        return self.row == other.row and self.number == other.number

Fehler

TypeError: unhashable type: 'Seat'

bookings[Seat(5, 12)] = "Maria" bricht mit diesem Fehler ab: „unhashable“ heißt „hat keinen Hash“.

Genauer, für Neugierige

• hash((self.row, self.number)) ist der Hash des Tupels aus den Attributen. Das ist der übliche Weg: Ein Tupel berechnet einen Hash aus all seinen Elementen und ihrer Reihenfolge, deshalb haben 5/12 und 12/5 verschiedene Hashes. Du kannst auch eine Formel nehmen, wie in Java:

def __hash__(self):
    return 31 * self.row + self.number

• isinstance prüft, ob das andere überhaupt ein Seat ist. Wenn nicht, sagt NotImplemented zu Python „ich weiß nicht, wie ich mich damit vergleiche“, und dann ist Seat(5, 12) == "5/12" gleich False.
• Für einen Schlüssel aus mehreren Werten brauchst du oft keine Klasse: Das Tupel (5, 12) hat schon == und einen Hash.

bookings = {}
bookings[(5, 12)] = "Maria"
print(bookings.get((5, 12)))
print(hash((5, 12)) == hash((12, 5)))

Ausgabe

Maria
False

Probier es aus

Finde den Fehler

Der Katalog hält die Produkte in einem set. Zwei Produkte mit demselben Code sind dasselbe Produkt, auch wenn sich der Preis geändert hat. Aber in mit dem neuen Preis ergibt False:

catalog = set()
catalog.add(Product("A-100", 25.0))
# Der Preis ist gesunken, aber es ist dasselbe Produkt.
print(Product("A-100", 19.9) in catalog)

Ausgabe

False

In welcher Zeile der Klasse steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1class Product:2 def __init__(self, code, price):3 self.code = code4 self.price = price56 def __eq__(self, other):7 if not isinstance(other, Product):8 return NotImplemented9 return self.code == other.code1011 def __hash__(self):12 return hash((self.code, self.price))

Prüfen

Die Idee

Die Buckets füllen sich

Bei vielen Paaren werden die Buckets lang, und die Suche wird langsamer. Deshalb wächst ein dict:

• In CPython hat ein kleines Dictionary 8 Plätze.
• Gibt es mehr Paare als 2/3 der Plätze, legt es eine größere Tabelle an und verteilt alle Schlüssel neu. Der Platz hängt von der Größe der Tabelle ab, deshalb wird jeder Schlüssel neu berechnet. Hier siehst du, wann es wächst, gemessen am Speicher, den das Dictionary belegt:

import sys

prices = {}
size = sys.getsizeof(prices)
for i in range(1, 12):
    prices[f"Produkt {i}"] = i
    if sys.getsizeof(prices) != size:
        size = sys.getsizeof(prices)
        print("Wächst bei Paar", i)

Ausgabe

Wächst bei Paar 1
Wächst bei Paar 6
Wächst bei Paar 11

• Das erste Mal ist, wenn die Tabelle mit 8 Plätzen entsteht. Dann wächst es beim 6. Paar (5 sind 2/3 von 8) und beim 11. (10 sind 2/3 von 16).
• Deshalb sind Schreiben und Suchen im Durchschnitt schnell, aber ab und zu dauert ein Schreiben länger.

Es gibt auch eine Falle. Ein Schlüssel darf sich nicht ändern, während er in einer Map oder einem Set liegt:

seat = Seat(5, 12)
sold = set()
sold.add(seat)

seat.number = 13
print(seat in sold)
print(Seat(5, 12) in sold)
print(len(sold))

Ausgabe

False
False
1

Der Platz wurde an der Stelle für 5/12 abgelegt. Dann wurde seine Nummer 13, und der Hash hat sich geändert. seat in sold sucht an der Stelle für 5/13 und findet ihn nicht. Seat(5, 12) in sold sucht an der richtigen Stelle, aber das Objekt dort ist nicht mehr gleich 5/12. Das Element ist im Set (die Größe ist 1), aber es kann nicht gefunden werden. Python hat kein final: Dass sich die Attribute eines Schlüssels nicht ändern, ist eine Abmachung. Ein Schlüssel, der sich wirklich nicht ändern kann, ist ein Tupel.

Genauer, für Neugierige

• sys.getsizeof gibt an, wie viele Bytes das Dictionary selbst belegt. Hier dient es nur dazu, zu sehen, wann sich die Tabelle ändert.
• Ein set funktioniert genauso, hält aber nur Schlüssel.

Übung

Eigene Hashes

Löse die Aufgaben in deinem Editor.

1. Ein Hash für eine Person. Eine Klasse Person mit Vorname, Nachname und Alter. Schreib __eq__ und __hash__ aus den drei Attributen, mit einem Tupel. Leg Jonas Weber mit 30 zweimal an und einmal mit 31. Gib aus, ob die Hashes der ersten beiden gleich sind, ob die Hashes der ersten und der dritten gleich sind, und wie viele verschiedene Personen in einem Set bleiben. Gib die Hashes selbst nicht aus: Bei Text ändern sie sich bei jedem Lauf.

Ausgabe

True
False
Verschiedene Personen: 2

2. Der Roboter im Lager. Der Roboter startet in Zelle (0, 0) und macht die Schritte NNEESWWN: N ist nach oben (y + 1), S nach unten, E nach rechts (x + 1), W nach links. Wie viele verschiedene Zellen hat er besucht, die Startzelle mitgezählt? Halte sie in einem Set von Point. Mit dieser Klasse sagt das Programm 9, es sollte aber 7 sagen. Repariere es:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

Ausgabe

Schritte: 8
Verschiedene Zellen: 7

3. Ein Hash einer Datei. Eine Funktion hash_file_content(file_path) liest die Datei und gibt den Hash ihres Inhalts als hexadezimalen Text zurück. hash() taugt hier nicht: Beim nächsten Lauf hätte dieselbe Datei einen anderen Hash. Nimm SHA-256 aus dem eingebauten Modul hashlib: hashlib.sha256(content.encode("utf-8")).hexdigest(). Schreib drei Berichte: a.txt und b.txt mit „Bericht für Oktober: 1250 €“ und c.txt mit „Bericht für Oktober: 1260 €“. Vergleiche ihre Hashes. Verschiedene Hashes heißen verschiedene Dateien, und gleiche SHA-256-Hashes heißen in der Praxis gleiche Dateien.

Ausgabe

a.txt: db6cf1fbd452ee116b95c9ed5d604e3b2b93d34a0e660991e991e1d84f43898f
b.txt: db6cf1fbd452ee116b95c9ed5d604e3b2b93d34a0e660991e991e1d84f43898f
c.txt: 7fad428479b6c5af07d54dcdf9665ded486847b65ef67aec7681a24e450d4902
a und b: gleich
a und c: verschieden

Weitere Aufgaben

• Eine eigene Hashtabelle. Eine Fortsetzung der Benutzertabelle aus der letzten Lektion, diesmal ohne dict. Leg eine Liste aus 8 Buckets an, jeder eine Liste aus Paaren von Benutzername und E-Mail. Die Hashfunktion ist die Summe der Zeichencodes im Namen (ord). Schreib add, get und eine Methode, die ausgibt, wie viele Paare in jedem Bucket sind.
• Eine ID aus einer E-Mail. generate_user_id(email) gibt "U" und die ersten 8 Zeichen des SHA-256 der kleingeschriebenen E-Mail zurück. Ist die ID für Jonas@Example.com und jonas@example.com dieselbe? Warum taugt hash() hier nicht? Können zwei verschiedene E-Mails dieselbe ID bekommen? Wie würdest du es herausfinden?
• Kollisionen zählen. Berechne den Platz der Schlüssel user1 … user1000 mit hash(key) % n bei 16, 64 und 1024 Buckets und zähle, wie viele Schlüssel in einem Bucket landen, in dem schon ein Schlüssel ist. Starte das Programm zweimal: Die Zahl ändert sich ein wenig, weil sich der Hash von Text ändert.
• Der Schuhkarton. Eine Klasse Box mit Breite, Höhe und Tiefe. Zwei Kartons sind gleich, wenn ihre Maße gleich sind, in derselben Reihenfolge. Schreib __eq__ und __hash__ mit einem Tupel und prüfe die Kartons 30×20×10 und 10×20×30 in einem Set.

Test

Teste dich

1. Was macht ein dict mit dem Hash eines Schlüssels?

Es berechnet daraus, wo es zu suchen beginntEs speichert ihn statt des SchlüsselsEs vergleicht ihn mit allen anderen Hashes

2. Zwei verschiedene Schlüssel haben denselben Hash. Was passiert?

Das Programm bricht mit einem Fehler abDer zweite löscht den erstenBeide bleiben im Dictionary, und == unterscheidet sie

3. a == b ist True. Was muss für ihre Hashes gelten?

hash(a) == hash(b), immerSie müssen verschieden seinNichts

4. Du nimmst deine eigene Klasse Seat als Schlüssel, ohne __eq__ und __hash__. Was gibt bookings.get(Seat(5, 12)) zurück?

None: Das neue Objekt ist ein anderes Objekt, und das voreingestellte == und hash schauen nicht auf die AttributeDen Wert, der mit bookings[Seat(5, 12)] = … hineingelegt wurdeDas Programm bricht mit einem Fehler ab

5. Seat hat __eq__, aber kein __hash__. Was passiert bei bookings[Seat(5, 12)] = "Maria"?

Es funktioniert wie mit __hash__TypeError: unhashable type: Python entfernt den Hash, wenn es __eq__ ohne __hash__ gibtDie Schlüssel werden zu Text

6. Welches Attribut darf sicher in den __hash__ eines Schlüssels eingehen?

Eine Zufallszahl, die in __init__ gewählt wirdEin Attribut, das sich nicht ändert und das auch __eq__ vergleichtEin Attribut, das sich ändert, während das Objekt in einem set liegt

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Dateien · Listen: append, remove und sort · Stack, Queue und verkettete Liste · dict und set
• Geht weiter in: dataclass, match und Muster · Hashtabelle · Passwörter · Abhängigkeiten: fremder Code, den dein Code ausführt
• Aufgaben zum Thema: Collections