powered by 
Eine Hash Table findet einen Schlüssel, ohne zu suchen: Eine Hashfunktion rechnet aus, in welchem Bucket er liegen muss. Weil sich zwei Schlüssel einen Bucket teilen können, braucht jede Hash Table einen Plan für Kollisionen, eine Liste je Bucket oder den nächsten freien Platz. Hier steht, wie beide arbeiten, was der Füllgrad damit zu tun hat und wann die Tabelle wächst.
Ein Array findet den Wert an Index 5 sofort, eine Liste von Namen muss man durchsuchen. Eine Hash Table verbindet beides: Sie hat ein Array von \(m\) Buckets, und eine Hashfunktion rechnet aus jedem Schlüssel einen Index von 0 bis \(m - 1\) aus. Dort wird gespeichert, und dort wird später gesucht.
Für ganze Zahlen ist die einfachste Hashfunktion der Rest der Division:
$$ h(k) = k \bmod m $$
Bei 8 Buckets landet 13 in Bucket 5, 21 auch in Bucket 5, 6 in Bucket 6.
Für Strings rechnet man aus allen Zeichen eine Zahl, zum Beispiel so, dass jedes Zeichen den bisherigen Wert mal 31 plus seinen Code ergibt, und nimmt davon den Rest. Wer nur das erste Zeichen nimmt, bekommt für »Anna«, »Alex« und »Ali« denselben Bucket.
Negative Schlüssel. In Java, JavaScript und C ist der Rest einer negativen Zahl negativ: -7 % 8 ergibt −7, kein gültiger Index. Python und Ruby rechnen 1. Wer sicher gehen will, rechnet ((k % m) + m) % m.
Zwei Schlüssel im selben Bucket sind eine Kollision. Sie lassen sich nicht vermeiden: Es gibt mehr mögliche Schlüssel als Buckets. Beim Chaining (separate chaining) hält jeder Bucket eine kleine Liste, und alle Schlüssel, die dort landen, kommen in diese Liste.
Hans Peter Luhn (1896–1964), Ingenieur aus Barmen (heute Wuppertal), später bei IBM in den USA. 1953 schlug er in einer Notiz für IBM vor, Schlüssel mit einer Rechnung auf Buckets zu verteilen und Kollisionen in Listen zu sammeln: die erste Hash Table, mit Chaining.
Von ihm stammt auch die letzte Ziffer jeder Kreditkartennummer, die Prüfziffer nach dem Luhn-Algorithmus: Mit ihr fällt eine falsch getippte Ziffer sofort auf.
insert(k): b ← h(k) if k already in buckets[b]: done (oder Fehler, je nach Aufgabe) append k to the back of buckets[b] count ← count + 1 find(k): return whether k is in buckets[b], with b ← h(k) remove(k): remove k from buckets[h(k)] if it is there
Gesucht wird nur in einem Bucket. Solange die Listen kurz sind, ist das fast so schnell wie ein Array. Sechs Schlüssel in acht Buckets, darunter drei, die alle in Bucket 5 landen:
Und im fertigen Bucket-Array zwei Suchen, eine erfolgreich und eine nicht:
Ohne Listen geht es auch: Jeder Bucket hält höchstens einen Schlüssel. Ist der Bucket \(h(k)\) belegt, probiert man den nächsten, dann den übernächsten, und am Ende des Arrays geht es vorn weiter. Das heißt Linear Probing (open addressing).
insert(k): b ← h(k) while buckets[b] occupied: if buckets[b] == k: done b ← (b + 1) mod m buckets[b] ← k count ← count + 1 find(k): b ← h(k) while buckets[b] occupied: if buckets[b] == k: found b ← (b + 1) mod m not found
Die Suche hört erst an einem leeren Bucket auf, denn bis dahin könnte \(k\) beim Einfügen weitergerutscht sein. Dieselben sechs Schlüssel wie oben:
Und im fertigen Bucket-Array zwei Suchen, eine erfolgreich und eine nicht:
Die Kollisionen in Bucket 5 schieben andere Schlüssel weiter, die selbst gar nicht kollidiert hätten: 6 gehört in Bucket 6, doch dort steht schon 21. So wachsen lange belegte Strecken, Cluster, und die Suche nach 37 muss am Ende fast die ganze Tabelle ansehen.
Entfernen ist bei Linear Probing heikel: Wird ein Bucket einfach geleert, endet die Suche nach einem Schlüssel, der hinter ihm liegt, zu früh. Man markiert ihn deshalb als gelöscht (einen »Grabstein«): Beim Suchen läuft man darüber hinweg, beim Einfügen darf er wieder belegt werden.
Der Füllgrad (load factor) ist die Zahl der Schlüssel geteilt durch die Zahl der Buckets, \(\alpha = n / m\). Er sagt, wie schnell die Tabelle ist:
Deshalb wächst eine Hash Table, wenn der Füllgrad eine Grenze überschreitet, meist 0,75: Sie legt ein Array mit doppelt so vielen Buckets an und fügt jeden Schlüssel neu ein. Kopieren genügt nicht, denn mit \(m\) ändert sich \(h(k) = k \bmod m\), und jeder Schlüssel kommt in einen anderen Bucket. Das heißt Rehashing. Wie beim Vergrößern einer Array List ist es teuer, aber selten.
insert(k): … as above … if count / m > 0.75: old ← buckets m ← 2 · m buckets ← m empty buckets count ← 0 for each key s in old: insert(s)
Hash Tables stecken hinter jedem Hash in Ruby, jedem dict und set in Python, jedem Objekt in JavaScript und jeder HashMap in Java: überall, wo man zu einem Schlüssel schnell einen Wert finden will. Ein Suchbaum kann dasselbe, langsamer, aber er hält die Schlüssel dafür sortiert. Eine Hash Table weiß nichts über die Reihenfolge, nach dem kleinsten Schlüssel muss sie alle Buckets durchsuchen.
Hash in Ruby, dict und set in Python sind fertige Hash Tables, mit Hashfunktion, Kollisionen und Rehashing, ohne dass du davon etwas merkst. Sollen zwei eigene Objekte mit gleichem Inhalt derselbe Schlüssel sein, brauchen sie eine Hashfunktion, die zu ihrer Gleichheit passt: gleiche Schlüssel, gleicher Bucket.
Hash: alle Methoden; der Abschnitt User-Defined Hash Keys zeigt, wie eigene Objekte mit hash und eql? zu Schlüsseln werden.dict und set: die beiden Hash Tables von Python.__hash__: was eine eigene Klasse zusammen mit __eq__ braucht, damit ihre Objekte Schlüssel sein können.