Schließfachnummern: Hash, Gleichheit und Gesamtbild

Gestern wurden die beiden Geisterkoffer von Band 13 weggeräumt. Übrig ist nur noch eine Zeile im Aufbewahrungsbuch. Letzten Monat wurde B im Fundsachen-Schließfach eingetragen, doch als der Besitzer es abholen wollte, antwortete das Buch „nicht vorhanden“. B kam zurück aufs Band, und der Rest ist die Geschichte bis gestern.

Han schlägt das Buch von damals noch einmal auf. Gibt man die Liste aus, steht B eindeutig darin, aber fragt man mit in, kommt False heraus. Schichtleiterin Do Miran nimmt die letzte Meldung entgegen. „Die Schließfachnummer bestimmt der Koffer. Ändert sich der Koffer nach dem Einlagern, ändert sich auch die Nummer.“

12-1. Schließfachnummern: Fach per Hash finden, mit == bestätigen (8 min)

dict und set sind Schließfachanlagen mit vielen Fächern. Beim Einlagern und beim Suchen eines Schlüssels laufen jedes Mal dieselben Schritte ab:

1. Mit hash(key) wird der Hash (die Schließfachnummer) des Schlüssels bestimmt.
2. Der Hash legt das Startfach fest.
3. Ist das Fach leer, ist hier Schluss: Beim Einlagern kommt der Schlüssel in dieses Fach, beim Suchen heißt es „nicht vorhanden“.
4. Ist das Fach belegt, wird geprüft, ob der Hash gleich ist und == denselben Schlüssel bestätigt. Wenn nicht, geht es nach einer festen Regel zum nächsten Fach.

Deshalb braucht es ein Versprechen: Gilt a == b, muss auch hash(a) == hash(b) gelten. Würde derselbe Schlüssel in verschiedenen Fächern mit der Suche beginnen, würden sie sich nie begegnen.

print(1 == 1.0 == True, hash(1) == hash(1.0) == hash(True))
# True True
print({1: "int", 1.0: "float", True: "bool"})
# {1: 'bool'}

1, 1.0 und True sind untereinander ==, haben also auch denselben Hash und sind im dict derselbe Schlüssel. Als Schlüssel bleibt die zuerst eingetragene 1, nur der Wert wird durch den letzten ersetzt.

Umgekehrt muss es nicht gelten. Eine Kollision, also gleicher Hash bei verschiedenem Wert, ist normal. Das == in Schritt 4 sortiert sie aus.

print(hash(42), hash(-1), hash(-2))
# 42 -2 -2
print(hash(-1) == hash(-2), -1 == -2)
# True False
lockers = {-1: "A", -2: "B"}
print(lockers[-1], lockers[-2])
# A B

In CPython ist der Hash einer kleinen Ganzzahl die Zahl selbst. Die -1 bedeutet intern in C aber „Fehler“, deshalb ergibt hash(-1) die -2. Das ist eine Kollision, und trotzdem hält das dict die beiden problemlos auseinander.

Der Hash eines Strings ändert sich bei jedem Programmstart. Das soll Angriffe verhindern, die Hashwerte vorausberechnen. Braucht man stets denselben Wert (etwa um Tests reproduzierbar zu machen), legt man die Umgebungsvariable PYTHONHASHSEED fest.

$ python -c "print(hash('T1'))"
# z. B.: 4646783657884298203
$ python -c "print(hash('T1'))"
# z. B.: -1769311965495050168
$ PYTHONHASHSEED=0 python -c "print(hash('T1'))"
# bei jedem Start derselbe Wert

Deshalb darf man Hashwerte weder in Dateien speichern noch mit anderen Prozessen austauschen. Ein Hash ist eine Nummer, die nur innerhalb eines einzigen Programmlaufs gilt.

Das Schließfach unten ist auf 8 Fächer vereinfacht. Es beginnt im Fach „Hash modulo 8“ und geht, wenn es belegt ist, direkt zum nächsten Fach. Lagere nacheinander 7 und 15 sowie -1 und -2 ein, um Kollisionen zu erzeugen.

12-2. Der Schlüssel, der sich nach dem Einlagern ändert (10 min)

Das Schließfach legt den Schlüssel in das Fach mit der Nummer, die beim Einlagern berechnet wurde, und berechnet diese Nummer danach nie wieder. Was passiert, wenn sich der Wert des Schlüssels nach dem Einlagern ändert und damit sein Hash? Wir probieren es mit einem absichtlich falsch gebauten Schlüssel aus.

class Tag:
    def __init__(self, n):
        self.n = n
    def __eq__(self, other):
        return isinstance(other, Tag) and self.n == other.n
    def __hash__(self):
        return hash(self.n)   # Fehler: Hash aus einem veränderlichen Wert gebildet
    def __repr__(self):
        return f"Tag({self.n})"

key = Tag(3)
lockers = {key: "bag B"}
print(Tag(3) in lockers)
# True
key.n = 13
print(lockers)
# {Tag(13): 'bag B'}
print(Tag(13) in lockers, Tag(3) in lockers, key in lockers)
# False False False

In der Ausgabe steht Tag(13), doch egal wie man fragt, es kommt False heraus.

• Sucht man mit Tag(13): Die Suche beginnt im Fach für Hash 13. Der Koffer liegt im Fach für Hash 3, die beiden begegnen sich nicht.
• Sucht man mit Tag(3): Man kommt zwar im Fach für Hash 3 an. Der Schlüssel dort ist jetzt aber Tag(13), also ergibt == False.
• Sucht man mit dem eingelagerten key selbst: Sein Hash ist jetzt 13, also geht es denselben Weg wie im ersten Fall.

# Fortsetzung des Beispiels oben
key.n = 3
print(Tag(3) in lockers)
# True

Setzt man den Wert auf 3 zurück, wird er wieder gefunden. Der Koffer lag die ganze Zeit in dem Fach, in das er eingelagert wurde. Geändert hat sich nur die Nummer, mit der man das Fach sucht.

Deshalb nimmt Python eingebaute Typen, deren Wert sich ändern kann, gar nicht erst als Schlüssel an. list, dict und set haben keinen Hash.

lockers = {}
lockers[[1, 2]] = "bag"
# TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

print(hash((1, 2)) == hash((1, 2)))
# True
hash((1, [2]))
# TypeError: unhashable type: 'list'

Ein Tupel kann Schlüssel sein, aber steckt eine Liste darin, lässt sich kein Hash bilden. Wie in Lektion 2 gesehen, bedeutet die Unveränderlichkeit eines Tupels nur, dass seine Referenzen feststehen. Ändert sich die Liste darin, müsste sich auch der Hash ändern. Als Schlüssel nimmt man Werte, die bis ganz innen unveränderlich sind, etwa (1, (2,)) oder ein frozenset.

12-3. Wer Gleichheit festlegt, legt auch den Hash fest (7 min)

Eine Klasse, die nichts davon definiert, vergleicht auf Gleichheit per is und bildet auch den Hash aus der Identität. Deshalb kann man ihre Instanzen als Schlüssel benutzen. Definiert man aber nur __eq__, setzt Python __hash__ auf None (wie in Lektion 8 angekündigt). Hat sich der Maßstab für Gleichheit geändert und benutzt man trotzdem den alten Hash, wäre das Versprechen gebrochen.

class Label:
    def __init__(self, code):
        self.code = code
    def __eq__(self, other):
        return isinstance(other, Label) and self.code == other.code

print(Label("T1") == Label("T1"), Label.__hash__)
# True None
{Label("T1")}
# TypeError: cannot use 'Label' as a set element (unhashable type: 'Label')

Braucht man einen Hash, gibt es zwei Wege.

1. @dataclass(frozen=True): erzeugt __eq__ und __hash__ aus den Feldern und verhindert, dass Felder geändert werden.

from dataclasses import dataclass

@dataclass(frozen=True)
class Tag:
    n: int

key = Tag(3)
lockers = {key: "bag B"}
print(lockers[Tag(3)])
# bag B
key.n = 13
# dataclasses.FrozenInstanceError: cannot assign to field 'n'

Ein @dataclass ohne frozen erzeugt nur __eq__, also ist __hash__ dann None. Bei einer Klasse, die als Schlüssel dienen soll, gehört frozen=True dazu.

2. __hash__ selbst schreiben: Man packt genau die Felder, die __eq__ vergleicht, in ein Tupel und bildet daraus den Hash.

class Route:
    def __init__(self, origin, dest):
        self.origin = origin
        self.dest = dest
    def __eq__(self, other):
        if not isinstance(other, Route):
            return NotImplemented
        return (self.origin, self.dest) == (other.origin, other.dest)
    def __hash__(self):
        return hash((self.origin, self.dest))

seen = {Route("ICN", "NRT")}
print(Route("ICN", "NRT") in seen, len({Route("ICN", "NRT"), Route("ICN", "NRT")}))
# True 1

Wer ihn selbst schreibt, hält sich an drei Regeln:

• Den Hash aus denselben Feldern bilden, die __eq__ vergleicht.
• Diese Felder nicht ändern, solange das Objekt als Schlüssel dient.
• Bei einem Gegenüber, mit dem man nicht vergleichen kann, NotImplemented statt False zurückgeben (Lektion 8).

12-4. Gesamtbild: Prüfung des Verwaltungsprogramms im Gepäckzentrum (15 min)

Als letzte Aufgabe legt die Schichtleiterin das alte Verwaltungsprogramm des Zentrums vor. Alle Fehler aus den elf Meldungen stecken in einer einzigen Datei. Sehen wir uns zuerst das Ergebnis der Ausführung an.

import gc
import weakref

class Bag:
    stickers = []                          # veränderliche Liste als Klassenattribut

    def __init__(self, code, items=[]):    # Liste als Standardargument
        self.code = code
        self.items = items
        self.partner = None

    def __eq__(self, other):
        return isinstance(other, Bag) and self.code == other.code

    def __hash__(self):
        return hash(self.code)             # Hash aus einem veränderlichen Wert

a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# ['camera'] ['fragile']

shelves = [[]] * 3                         # dreimal dieselbe Liste
shelves[0].append("A1")
print(shelves)
# [['A1'], ['A1'], ['A1']]

calls = [lambda: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 3', 'gate 3', 'gate 3']

lockers = {b: "L7"}
b.code = "B2"                              # Schlüssel nach dem Einlagern geändert
print(Bag("B1") in lockers, Bag("B2") in lockers)
# False False

a.partner, b.partner = b, a                # zwei Koffer, die einander enthalten
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# False
gc.collect()
print(watch() is None)
# True

Wir gehen Zeile für Zeile die Ursachen durch und machen daraus eine Prüfliste.

Hier das korrigierte Programm. Alle Ausgaben sind jetzt so, wie sie gemeint waren.

import weakref

class Bag:
    def __init__(self, code, items=None):
        self.code = code
        self.items = [] if items is None else list(items)
        self.stickers = []
        self._partner = None

    @property
    def partner(self):
        return self._partner() if self._partner is not None else None

    @partner.setter
    def partner(self, other):
        self._partner = weakref.ref(other)

a = Bag("A1")
b = Bag("B1")
a.items.append("camera")
a.stickers.append("fragile")
print(b.items, b.stickers)
# [] []

shelves = [[] for _ in range(3)]
shelves[0].append("A1")
print(shelves)
# [['A1'], [], []]

calls = [lambda g=g: f"gate {g}" for g in (1, 2, 3)]
print([call() for call in calls])
# ['gate 1', 'gate 2', 'gate 3']

lockers = {b.code: "L7"}                   # der Schlüssel ist ein unveränderlicher String
lockers["B2"] = lockers.pop(b.code)        # beim Ändern des Codes wird der Schlüssel umgelagert
b.code = "B2"
print("B1" in lockers, "B2" in lockers, lockers[b.code])
# False True L7

a.partner, b.partner = b, a
watch = weakref.ref(a)
del a, b, lockers
print(watch() is None)
# True

Dass das Übergebene mit items=list(items) kopiert wird, ist ebenfalls die defensive Kopie aus Lektion 4. __eq__ und __hash__ sind aus Bag verschwunden, also werden die Koffer selbst über ihre Identität verglichen, und die Rolle des Schlüssels übernimmt der Code als String.

Die ersten beiden Fehler (Standardargument, Klassenattribut) vergleichen wir auf der Etikettentafel. Bei bug laufen die items-Pfeile beider Instanzen in einer Liste zusammen, und stickers hängt am Kasten des Bauplans (class).

Ein Rückblick auf die zwölf Lektionen, je eine Zeile:

Fall abgeschlossen (10 min)

Geisterkoffer B war ein Koffer, der seinen Hash aus der Nummer no bildete. Nach dem Einlagern wurde bei einer Umsortierung die Nummer überschrieben, und damit änderte sich der Weg zum Fach. Geht man ohne Hash Fach für Fach durch, ist B noch da.

from dataclasses import dataclass

class Bag:
    def __init__(self, no):
        self.no = no
    def __eq__(self, other):
        return isinstance(other, Bag) and self.no == other.no
    def __hash__(self):
        return hash(self.no)

ghost = Bag(3)
lockers = {ghost: "L7"}
ghost.no = 13                                         # Nummer bei der Umsortierung überschrieben
print(ghost in lockers)
# False
print([v for k, v in lockers.items() if k is ghost])  # ohne Hash Fach für Fach durchgehen: da ist er
# ['L7']

@dataclass(frozen=True)
class BagNo:
    no: int

lockers = {BagNo(13): "L7"}                           # unter einem unveränderlichen Schlüssel neu einlagern
print(lockers[BagNo(13)], BagNo(13) in lockers)
# L7 True

• Das Durchgehen mit items() benutzt keinen Hash und findet B deshalb. Dafür dauert es so lange, wie es Fächer gibt.
• Der neue Schlüssel BagNo ist frozen=True, seine Nummer lässt sich nach dem Einlagern nicht mehr ändern. Ändert sich die Nummer, erzeugt man ein neues BagNo und lagert um.

Schließfach L7 geht auf. Bs Gepäck, einen Monat lang eingeschlossen, kommt zum Vorschein, und Han verständigt den Besitzer. Schichtleiterin Do Miran legt das Bündel Etiketten zurück in die Schublade. „Weißt du noch, was ich am ersten Tag gesagt habe? Ein Koffer, viele Etiketten. Jetzt siehst du, wo die Etiketten hängen, wer einen Koffer festhält und in welchem Fach ein Koffer liegt, oder?“ Pin zeigt auf Band 13. Heute dreht dort nichts seine Runden.

Übungen

1. Wie viele Fächer belegt {(1, 2): "A", (2, 1): "B"}? Vergleich für beide Tupel == und hash, sag das Ergebnis voraus und prüfe es dann.
2. Bau den Tag aus 12-2 mit @dataclass(frozen=True) neu und prüfe, wo key.n = 13 abgefangen wird.
3. Korrigiere das fehlerhafte Programm aus 12-4 selbst, ohne in die korrigierte Fassung zu schauen. Notiere bei jeder Korrektur, zu welcher Zeile der Prüfliste sie gehört.