Lektion 2.3

Hashtabellen

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • den abstrakten Datentyp Wörterbuch beschreiben und mit Divisions- und Multiplikationsmethode Hashwerte berechnen,

  • Kollisionen durch Verkettung und durch offene Adressierung mit linearem, quadratischem Sondieren und Doppel-Hashing auflösen,

  • die erwartete Laufzeit aus dem Belegungsfaktor α\alpha ablesen und sagen, unter welcher Annahme die Aussage gilt,

  • erklären, warum man bei offener Adressierung mit Grabsteinen löscht,

  • begründen, warum Einfügen mit Rehashing amortisiert O(1)O(1) erwartete Zeit kostet.

Vorausgesetzt: Arrays und verkettete Listen, Amortisierte Analyse

Eine Hochschule will zu einer Matrikelnummer schnell den Namen finden. Matrikelnummern haben sieben Stellen, im Kurs sitzen aber nur 300 Studierende. Ein Array mit 10710^7 Plätzen, in dem die Nummer selbst der Index ist, fände jeden Namen in O(1)O(1), stünde aber fast vollständig leer. Ein sortiertes Array mit 300 Einträgen spart Platz, aber Suchen kostet O(log⁡n)O(\log n) und Einfügen O(n)O(n).

Die Idee einer Hashtabelle: Man rechnet aus der Matrikelnummer einen Index zwischen 00 und, sagen wir, 499499 aus und legt den Eintrag dort ab. Dann landen manchmal zwei Nummern auf demselben Platz. Diese Lektion zeigt, wie man damit umgeht und warum es im Mittel trotzdem konstant schnell bleibt.

Vermute zuerst

2323 Schlüssel werden zufällig und unabhängig auf 365365 Plätze verteilt, jeder Platz gleich wahrscheinlich. Wie wahrscheinlich landen mindestens zwei auf demselben Platz?

Definition

Wörterbuch, Hashfunktion und Kollision

Ein Wörterbuch (englisch dictionary oder map) ist ein abstrakter Datentyp für eine Menge von Paaren (k,v)(k, v) aus Schlüssel kk und Wert vv, in der jeder Schlüssel höchstens einmal vorkommt. Die Schlüssel stammen aus einer Menge UU, dem Universum. Operationen: insert(k, v)\texttt{insert(k, v)} speichert das Paar und ersetzt einen alten Wert zu kk; search(k)\texttt{search(k)} liefert den Wert zu kk oder meldet, dass kk fehlt; delete(k)\texttt{delete(k)} entfernt das Paar mit Schlüssel kk.

Eine Hashtabelle ist ein Array T[0],…,T[m−1]T[0], \dots, T[m-1] zusammen mit einer Hashfunktion h:U→{0,1,…,m−1}h: U \to \{0, 1, \dots, m-1\}. Ein Paar mit Schlüssel kk wird bei T[h(k)]T[h(k)] gesucht und abgelegt; h(k)h(k) heißt Hashwert von kk. Zwei verschiedene Schlüssel k≠k′k \neq k' mit h(k)=h(k′)h(k) = h(k') bilden eine Kollision.

Ist UU größer als mm, gibt es nach dem Schubfachprinzip immer Kollisionen. In den Beispielen zeigen wir nur die Schlüssel.

Beispiel

Divisionsmethode

Für ganzzahlige Schlüssel k≥0k \ge 0 nimmt die Divisionsmethode den Rest bei der Division durch mm:

h(k)=k mod mh(k) = k \bmod m

Mit m=11m = 11 ist h(10)=10h(10) = 10, h(22)=0h(22) = 0, h(31)=9h(31) = 9, h(4)=4h(4) = 4 und h(15)=4h(15) = 4. Die Schlüssel 44 und 1515 kollidieren.

Schlechte Wahl von mm. Ist m=2pm = 2^p, dann besteht k mod mk \bmod m nur aus den letzten pp Bits von kk. Mit m=16m = 16 landen 32,48,64,8032, 48, 64, 80 alle auf Platz 00. Man wählt mm deshalb meist als Primzahl, die nicht nahe an einer Zweierpotenz liegt.

Beispiel

Multiplikationsmethode

Die Multiplikationsmethode wählt eine Konstante AA mit 0<A<10 < A < 1, multipliziert, behält den Nachkommaanteil und streckt ihn auf mm Plätze. Dabei ist x mod 1=x−⌊x⌋x \bmod 1 = x - \lfloor x \rfloor der Nachkommaanteil von xx und ⌊y⌋\lfloor y \rfloor die größte ganze Zahl ≤y\le y.

h(k)=⌊m⋅(kA mod 1)⌋,oft A=5−12≈0,6180340h(k) = \bigl\lfloor m \cdot (k A \bmod 1) \bigr\rfloor, \qquad \text{oft } A = \tfrac{\sqrt{5} - 1}{2} \approx 0{,}6180340

Für k=100k = 100 und m=16m = 16: 100⋅A≈61,80340100 \cdot A \approx 61{,}80340, der Nachkommaanteil ist 0,803400{,}80340, und 16⋅0,80340≈12,85416 \cdot 0{,}80340 \approx 12{,}854. Also h(100)=12h(100) = 12.

Hier ist mm unkritisch, auch eine Zweierpotenz ist gut, weil alle Bits von kk in den Nachkommaanteil eingehen. Den Wert von AA oben empfiehlt Knuth; schlecht sind Werte nahe an einfachen Brüchen wie 12\frac12.

Kurz geprüft

Welchen Hashwert hat k=1234k = 1234 nach der Divisionsmethode mit m=97m = 97?

Definition

Verkettung und Belegungsfaktor

Bei der Verkettung (englisch chaining) ist T[j]T[j] eine verkettete Liste aller gespeicherten Schlüssel mit Hashwert jj. insert\texttt{insert} fügt vorn in die Liste T[h(k)]T[h(k)] ein (wenn kk schon dort steht, wird nur der Wert ersetzt), search\texttt{search} durchläuft sie, delete\texttt{delete} entfernt den Knoten, mit doppelt verketteten Listen in O(1)O(1), sobald er gefunden ist.

Der Belegungsfaktor einer Tabelle mit mm Plätzen und nn gespeicherten Schlüsseln ist α=n/m\alpha = n/m. Bei Verkettung ist α\alpha die mittlere Listenlänge und darf größer als 11 sein.

Mit h(k)=k mod 11h(k) = k \bmod 11 und den Schlüsseln 10,22,31,4,15,28,17,88,5910, 22, 31, 4, 15, 28, 17, 88, 59 in dieser Reihenfolge entsteht (α=9/11\alpha = 9/11):

PlatzListe
088, 22
459, 15, 4
617, 28
931
1010

Alle übrigen Plätze sind leer. Eine erfolglose Suche nach einem Schlüssel mit Hashwert 44 durchläuft drei Knoten, eine nach Hashwert 11 keinen.

Satz

Erwartete Suchzeit bei Verkettung

Annahme (einfaches gleichverteiltes Hashing): Jeder Schlüssel fällt unabhängig von den anderen mit Wahrscheinlichkeit 1/m1/m auf jeden der mm Plätze, und h(k)h(k) ist in O(1)O(1) berechenbar. Dann kostet eine erfolglose Suche in einer Tabelle mit Verkettung und Belegungsfaktor α\alpha erwartet Θ(1+α)\Theta(1 + \alpha) Zeit. Dasselbe gilt für eine erfolgreiche Suche.

Häufige Fehler

„Eine Hashtabelle sucht in O(1)O(1)“

Der Satz wird oft ohne Bedingungen zitiert, als gelte er für jede Eingabe.

Richtig ist

Im schlechtesten Fall fallen alle nn Schlüssel auf denselben Platz, und eine Suche kostet Θ(n)\Theta(n). O(1)O(1) ist eine erwartete Laufzeit, und sie gilt nur unter einer Annahme über die Verteilung der Hashwerte und nur, wenn α\alpha beschränkt bleibt. Eine Garantie für jede Eingabe gibt ein balancierter Suchbaum mit O(log⁡n)O(\log n).

Definition

Offene Adressierung

Bei offener Adressierung stehen alle Schlüssel in der Tabelle selbst, also ist α≤1\alpha \le 1. Die Hashfunktion bekommt einen zweiten Parameter, den Versuch i=0,1,…,m−1i = 0, 1, \dots, m-1, und die Sondierfolge h(k,0),h(k,1),…,h(k,m−1)h(k, 0), h(k, 1), \dots, h(k, m-1) gibt an, in welcher Reihenfolge Plätze ausprobiert werden. Sie soll jeden der mm Plätze genau einmal enthalten. Mit Hilfsfunktionen h1,h2h_1, h_2 in die Plätze und h1(k)=k mod mh_1(k) = k \bmod m:

  • Lineares Sondieren: h(k,i)=(h1(k)+i) mod mh(k, i) = (h_1(k) + i) \bmod m.
  • Quadratisches Sondieren: h(k,i)=(h1(k)+i2) mod mh(k, i) = (h_1(k) + i^2) \bmod m.
  • Doppel-Hashing: h(k,i)=(h1(k)+i⋅h2(k)) mod mh(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m.
ZeileEinrückungAnweisung
10function hashInsert(T, k)\texttt{function hashInsert(T, k)}
21for i = 0 to m-1\texttt{for i = 0 to m-1}
32j = h(k, i)\texttt{j = h(k, i)}
42if T[j] == nil\texttt{if T[j] == nil}
53T[j] = k\texttt{T[j] = k}
63return j\texttt{return j}
71error "Tabelle voll"\texttt{error "Tabelle voll"}
80function hashSearch(T, k)\texttt{function hashSearch(T, k)}
91for i = 0 to m-1\texttt{for i = 0 to m-1}
102j = h(k, i)\texttt{j = h(k, i)}
112if T[j] == nil\texttt{if T[j] == nil}
123return nil\texttt{return nil}
132if T[j] == k\texttt{if T[j] == k}
143return j\texttt{return j}
151return nil\texttt{return nil}

nil\texttt{nil} markiert einen freien Platz; hashInsert\texttt{hashInsert} wird nur für fehlende Schlüssel aufgerufen. Die Suche darf an einem freien Platz aufhören: Wäre kk gespeichert, hätte hashInsert\texttt{hashInsert} es spätestens dort abgelegt.

Beispiel

Neun Schlüssel in elf Plätzen

m=11m = 11, h1(k)=k mod 11h_1(k) = k \bmod 11, eingefügt werden 10,22,31,4,15,28,17,88,5910, 22, 31, 4, 15, 28, 17, 88, 59. Zuerst lineares Sondieren; die letzte Spalte gibt den Zustand nach dem Schritt als Menge der belegten Plätze an.

Schrittkkh1(k)h_1(k)sondierte Plätzelandet aufbelegt danach
11010101010
2220000, 10
3319990, 9, 10
444440, 4, 9, 10
51544, 550, 4, 5, 9, 10
6286660, 4, 5, 6, 9, 10
71766, 770, 4 bis 7, 9, 10
88800, 110, 1, 4 bis 7, 9, 10
95944, 5, 6, 7, 880, 1, 4 bis 10

Dieselbe Folge mit quadratischem Sondieren und mit Doppel-Hashing, h2(k)=1+(k mod 10)h_2(k) = 1 + (k \bmod 10):

kkquadratisch: sondierte Plätzeh2(k)h_2(k)Doppel-Hashing: sondierte Plätze
1010110
22030
31929
4454
154, 564, 10, 5
28696
176, 786, 3
880, 190, 9, 7
594, 5, 8104, 3, 2

Endzustand:

Platz012345678910
linear2288––4152817593110
quadratisch2288––4152817593110
Doppel-Hashing22–59174152888–3110

Bei 5959 quadratisch: 4+0=44 + 0 = 4, 4+1=54 + 1 = 5, 4+4=84 + 4 = 8. Bei 8888 mit Doppel-Hashing: 00, 0+9=90 + 9 = 9, (0+18) mod 11=7(0 + 18) \bmod 11 = 7.

Linear und quadratisch enden hier zufällig in derselben Tabelle, aber 5959 braucht linear fünf Versuche statt drei. Lineares Sondieren bildet lange zusammenhängende Blöcke belegter Plätze (hier 44 bis 1010 und über das Ende hinweg 0,10, 1), und jeder Schlüssel, der in einen Block fällt, läuft bis zu dessen Ende und verlängert ihn: primäres Clustering. Quadratisches Sondieren springt aus dem Block heraus; Schlüssel mit gleichem h1(k)h_1(k) teilen aber weiter ihre ganze Folge (sekundäres Clustering). Beim Doppel-Hashing hängt auch die Schrittweite vom Schlüssel ab.

Satz

Wann die Sondierfolgen alle Plätze treffen

(a) Doppel-Hashing: Die Folge (h1(k)+i h2(k)) mod m(h_1(k) + i\, h_2(k)) \bmod m für i=0,…,m−1i = 0, \dots, m-1 trifft genau dann alle mm Plätze, wenn ggT⁡(h2(k),m)=1\operatorname{ggT}(h_2(k), m) = 1. Bei mm prim genügt 1≤h2(k)≤m−11 \le h_2(k) \le m - 1, wie bei h2(k)=1+(k mod (m−1))h_2(k) = 1 + (k \bmod (m-1)).

(b) Quadratisches Sondieren: Ist mm eine Primzahl, dann sind die Plätze für i=0,1,…,m−12i = 0, 1, \dots, \frac{m-1}{2} paarweise verschieden. Sind höchstens m−12\frac{m-1}{2} Plätze belegt, findet hashInsert\texttt{hashInsert} also stets einen freien.

Kurz geprüft

Eine Tabelle hat m=12m = 12 Plätze, und für einen Schlüssel ist h1(k)=5h_1(k) = 5 und h2(k)=4h_2(k) = 4. Wie viele verschiedene Plätze besucht seine Sondierfolge beim Doppel-Hashing?

Satz

Erwartete Versuche bei offener Adressierung

Annahme (gleichverteiltes Hashing): Die Sondierfolge jedes Schlüssels ist mit gleicher Wahrscheinlichkeit jede der m!m! Anordnungen der Plätze, unabhängig von den anderen Schlüsseln. Dann braucht eine erfolglose Suche bei Belegungsfaktor α=n/m<1\alpha = n/m < 1 im Erwartungswert höchstens so viele Versuche:

E[Versuche]≤11−αE[\text{Versuche}] \le \frac{1}{1 - \alpha}
Häufige Fehler

Löschen durch Leeren des Platzes

In der linearen Tabelle oben wird 1515 gelöscht, indem Platz 55 wieder nil\texttt{nil} wird. Danach sucht jemand 5959: Versuch 11 ist Platz 44 mit dem Schlüssel 44, Versuch 22 ist Platz 55, und der ist frei. hashSearch\texttt{hashSearch} meldet „fehlt“, obwohl 5959 auf Platz 88 steht. Der geleerte Platz hat die Sondierfolge von 5959 unterbrochen.

Richtig ist

Man setzt beim Löschen einen Grabstein, einen besonderen Wert DEL\texttt{DEL}. Die Suche behandelt ihn wie einen belegten Platz mit falschem Schlüssel und sucht weiter; nur nil\texttt{nil} beendet sie. Einfügen darf einen Grabstein überschreiben, nachdem die Suche bestätigt hat, dass der Schlüssel fehlt: 2626 mit h1(26)=4h_1(26) = 4 landet so auf Platz 55. Weil Grabsteine bei der Suche wie belegte Plätze zählen, baut man die Tabelle nach vielen Löschungen neu auf. Bei Verkettung gibt es das Problem nicht.

Satz

Rehashing ist amortisiert billig

Eine Tabelle beginnt leer mit m0m_0 Plätzen. Wird nach einer Einfügung α>αmax⁡\alpha > \alpha_{\max} (eine feste Schranke, etwa 12\frac12), legt man eine Tabelle mit doppelt so vielen Plätzen und einer dazu passenden Hashfunktion an und fügt alle Schlüssel neu ein (Rehashing). Dann werden bei nn Einfügungen insgesamt höchstens 3n3n Schlüssel neu eingefügt. Kostet jedes Einfügen bei α≤αmax⁡\alpha \le \alpha_{\max} erwartet O(1)O(1), so kosten die nn Einfügungen zusammen erwartet O(n)O(n), also amortisiert O(1)O(1) je Einfügung.

Zusammenfassung

  • Ein Wörterbuch speichert Paare aus Schlüssel und Wert. Eine Hashtabelle legt den Schlüssel kk bei T[h(k)]T[h(k)] ab; Kollisionen sind unvermeidlich, schon bei wenigen Schlüsseln (Geburtstagsparadoxon).

  • Divisionsmethode h(k)=k mod mh(k) = k \bmod m mit mm prim und fern von Zweierpotenzen; Multiplikationsmethode ⌊m(kA mod 1)⌋\lfloor m (kA \bmod 1) \rfloor, bei der mm beliebig sein darf.

  • Verkettung: eine Liste je Platz. Unter einfachem gleichverteiltem Hashing kostet Suchen erwartet Θ(1+α)\Theta(1 + \alpha) mit α=n/m\alpha = n/m.

  • Offene Adressierung: Sondierfolge linear, quadratisch oder mit Doppel-Hashing; Doppel-Hashing braucht ggT⁡(h2(k),m)=1\operatorname{ggT}(h_2(k), m) = 1.

  • Unter gleichverteiltem Hashing braucht eine erfolglose Suche erwartet höchstens 11−α\frac{1}{1-\alpha} Versuche. Lineares Sondieren ist wegen primären Clusterings bei hohem α\alpha deutlich schlechter.

  • Löschen bei offener Adressierung setzt Grabsteine, sonst brechen Suchfolgen ab.

  • Rehashing verdoppelt mm, wenn α\alpha eine Schranke übersteigt. Das kostet einzeln Θ(n)\Theta(n), amortisiert O(1)O(1) je Einfügung.

  • Alle O(1)O(1)-Aussagen sind Erwartungswerte unter Annahmen; im schlechtesten Fall kostet Suchen Θ(n)\Theta(n).

Übungen

Aufgabe 1Numerisch

Berechne nach der Multiplikationsmethode mit m=16m = 16 und A≈0,618034A \approx 0{,}618034 den Hashwert von k=42k = 42.

Aufgabe 2Numerisch

Eine leere Tabelle hat m=7m = 7 Plätze, h1(k)=k mod 7h_1(k) = k \bmod 7 und lineares Sondieren. Eingefügt werden nacheinander 14,21,8,714, 21, 8, 7. Auf welchem Platz landet 77?

Aufgabe 3Multiple Choice

Eine Tabelle mit Doppel-Hashing hat m=16m = 16 Plätze. Welche zweite Hashfunktion sorgt dafür, dass die Sondierfolge jedes Schlüssels alle 1616 Plätze trifft?

Aufgabe 4Numerisch

Eine Hashtabelle beginnt leer mit m=8m = 8 Plätzen. Wird nach einer Einfügung α>12\alpha > \frac12, wird mm verdoppelt und alle Schlüssel (einschließlich des gerade eingefügten) werden neu eingefügt. Wie viele Neueinfügungen durch Rehashing gibt es insgesamt, wenn 4040 Schlüssel eingefügt werden?

Aufgabe 5Freitext

Eine Tabelle mit offener Adressierung und Grabsteinen hat mm Plätze. Abwechselnd wird ein neuer Schlüssel eingefügt und ein vorhandener gelöscht, sodass stets höchstens m/2m/2 Schlüssel gespeichert sind. Erkläre, warum erfolglose Suchen mit der Zeit trotzdem immer länger werden können, und schlage eine Abhilfe vor, deren Kosten amortisiert O(1)O(1) je Operation sind.