Hashtabellen
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 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 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 Plätzen, in dem die Nummer selbst der Index ist, fände jeden Namen in , stünde aber fast vollständig leer. Ein sortiertes Array mit 300 Einträgen spart Platz, aber Suchen kostet und Einfügen .
Die Idee einer Hashtabelle: Man rechnet aus der Matrikelnummer einen Index zwischen und, sagen wir, 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.
Schlüssel werden zufällig und unabhängig auf Plätze verteilt, jeder Platz gleich wahrscheinlich. Wie wahrscheinlich landen mindestens zwei auf demselben Platz?
Wörterbuch, Hashfunktion und Kollision
Ein Wörterbuch (englisch dictionary oder map) ist ein abstrakter Datentyp für eine Menge von Paaren aus Schlüssel und Wert , in der jeder Schlüssel höchstens einmal vorkommt. Die Schlüssel stammen aus einer Menge , dem Universum. Operationen: speichert das Paar und ersetzt einen alten Wert zu ; liefert den Wert zu oder meldet, dass fehlt; entfernt das Paar mit Schlüssel .
Eine Hashtabelle ist ein Array zusammen mit einer Hashfunktion . Ein Paar mit Schlüssel wird bei gesucht und abgelegt; heißt Hashwert von . Zwei verschiedene Schlüssel mit bilden eine Kollision.
Ist größer als , gibt es nach dem Schubfachprinzip immer Kollisionen. In den Beispielen zeigen wir nur die Schlüssel.
Divisionsmethode
Divisionsmethode
Für ganzzahlige Schlüssel nimmt die Divisionsmethode den Rest bei der Division durch :
Mit ist , , , und . Die Schlüssel und kollidieren.
Schlechte Wahl von . Ist , dann besteht nur aus den letzten Bits von . Mit landen alle auf Platz . Man wählt deshalb meist als Primzahl, die nicht nahe an einer Zweierpotenz liegt.
Multiplikationsmethode
Multiplikationsmethode
Die Multiplikationsmethode wählt eine Konstante mit , multipliziert, behält den Nachkommaanteil und streckt ihn auf Plätze. Dabei ist der Nachkommaanteil von und die größte ganze Zahl .
Für und : , der Nachkommaanteil ist , und . Also .
Hier ist unkritisch, auch eine Zweierpotenz ist gut, weil alle Bits von in den Nachkommaanteil eingehen. Den Wert von oben empfiehlt Knuth; schlecht sind Werte nahe an einfachen Brüchen wie .
Welchen Hashwert hat nach der Divisionsmethode mit ?
Verkettung und Belegungsfaktor
Bei der Verkettung (englisch chaining) ist eine verkettete Liste aller gespeicherten Schlüssel mit Hashwert . fügt vorn in die Liste ein (wenn schon dort steht, wird nur der Wert ersetzt), durchläuft sie, entfernt den Knoten, mit doppelt verketteten Listen in , sobald er gefunden ist.
Der Belegungsfaktor einer Tabelle mit Plätzen und gespeicherten Schlüsseln ist . Bei Verkettung ist die mittlere Listenlänge und darf größer als sein.
Mit und den Schlüsseln in dieser Reihenfolge entsteht ():
| Platz | Liste |
|---|---|
| 0 | 88, 22 |
| 4 | 59, 15, 4 |
| 6 | 17, 28 |
| 9 | 31 |
| 10 | 10 |
Alle übrigen Plätze sind leer. Eine erfolglose Suche nach einem Schlüssel mit Hashwert durchläuft drei Knoten, eine nach Hashwert keinen.
Erwartete Suchzeit bei Verkettung
Annahme (einfaches gleichverteiltes Hashing): Jeder Schlüssel fällt unabhängig von den anderen mit Wahrscheinlichkeit auf jeden der Plätze, und ist in berechenbar. Dann kostet eine erfolglose Suche in einer Tabelle mit Verkettung und Belegungsfaktor erwartet Zeit. Dasselbe gilt für eine erfolgreiche Suche.
Wir zeigen den erfolglosen Fall. Sei die Länge der Liste . Für jeden der gespeicherten Schlüssel ist die Wahrscheinlichkeit, auf Platz zu fallen, . Wegen der Linearität des Erwartungswerts ist .
Eine erfolglose Suche nach berechnet in und durchläuft die ganze Liste . Weil nicht gespeichert ist, ist nach der Annahme unabhängig von den gespeicherten Schlüsseln und gleichverteilt. Die erwartete Länge der durchlaufenen Liste ist also , und die erwartete Zeit .
Für die erfolgreiche Suche zählt man ähnlich die Schlüssel, die nach dem gesuchten in dessen Liste eingefügt wurden, und erhält im Mittel untersuchte Knoten; diesen Teil führen wir hier nicht aus.
„Eine Hashtabelle sucht in “
„Eine Hashtabelle sucht in “
Der Satz wird oft ohne Bedingungen zitiert, als gelte er für jede Eingabe.
Im schlechtesten Fall fallen alle Schlüssel auf denselben Platz, und eine Suche kostet . ist eine erwartete Laufzeit, und sie gilt nur unter einer Annahme über die Verteilung der Hashwerte und nur, wenn beschränkt bleibt. Eine Garantie für jede Eingabe gibt ein balancierter Suchbaum mit .
Offene Adressierung
Bei offener Adressierung stehen alle Schlüssel in der Tabelle selbst, also ist . Die Hashfunktion bekommt einen zweiten Parameter, den Versuch , und die Sondierfolge gibt an, in welcher Reihenfolge Plätze ausprobiert werden. Sie soll jeden der Plätze genau einmal enthalten. Mit Hilfsfunktionen in die Plätze und :
- Lineares Sondieren: .
- Quadratisches Sondieren: .
- Doppel-Hashing: .
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 2 | |
| 4 | 2 | |
| 5 | 3 | |
| 6 | 3 | |
| 7 | 1 | |
| 8 | 0 | |
| 9 | 1 | |
| 10 | 2 | |
| 11 | 2 | |
| 12 | 3 | |
| 13 | 2 | |
| 14 | 3 | |
| 15 | 1 |
markiert einen freien Platz; wird nur für fehlende Schlüssel aufgerufen. Die Suche darf an einem freien Platz aufhören: Wäre gespeichert, hätte es spätestens dort abgelegt.
Neun Schlüssel in elf Plätzen
Neun Schlüssel in elf Plätzen
, , eingefügt werden . Zuerst lineares Sondieren; die letzte Spalte gibt den Zustand nach dem Schritt als Menge der belegten Plätze an.
| Schritt | sondierte Plätze | landet auf | belegt danach | ||
|---|---|---|---|---|---|
| 1 | 10 | 10 | 10 | 10 | 10 |
| 2 | 22 | 0 | 0 | 0 | 0, 10 |
| 3 | 31 | 9 | 9 | 9 | 0, 9, 10 |
| 4 | 4 | 4 | 4 | 4 | 0, 4, 9, 10 |
| 5 | 15 | 4 | 4, 5 | 5 | 0, 4, 5, 9, 10 |
| 6 | 28 | 6 | 6 | 6 | 0, 4, 5, 6, 9, 10 |
| 7 | 17 | 6 | 6, 7 | 7 | 0, 4 bis 7, 9, 10 |
| 8 | 88 | 0 | 0, 1 | 1 | 0, 1, 4 bis 7, 9, 10 |
| 9 | 59 | 4 | 4, 5, 6, 7, 8 | 8 | 0, 1, 4 bis 10 |
Dieselbe Folge mit quadratischem Sondieren und mit Doppel-Hashing, :
| quadratisch: sondierte Plätze | Doppel-Hashing: sondierte Plätze | ||
|---|---|---|---|
| 10 | 10 | 1 | 10 |
| 22 | 0 | 3 | 0 |
| 31 | 9 | 2 | 9 |
| 4 | 4 | 5 | 4 |
| 15 | 4, 5 | 6 | 4, 10, 5 |
| 28 | 6 | 9 | 6 |
| 17 | 6, 7 | 8 | 6, 3 |
| 88 | 0, 1 | 9 | 0, 9, 7 |
| 59 | 4, 5, 8 | 10 | 4, 3, 2 |
Endzustand:
| Platz | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| linear | 22 | 88 | – | – | 4 | 15 | 28 | 17 | 59 | 31 | 10 |
| quadratisch | 22 | 88 | – | – | 4 | 15 | 28 | 17 | 59 | 31 | 10 |
| Doppel-Hashing | 22 | – | 59 | 17 | 4 | 15 | 28 | 88 | – | 31 | 10 |
Bei quadratisch: , , . Bei mit Doppel-Hashing: , , .
Linear und quadratisch enden hier zufällig in derselben Tabelle, aber braucht linear fünf Versuche statt drei. Lineares Sondieren bildet lange zusammenhängende Blöcke belegter Plätze (hier bis und über das Ende hinweg ), 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 teilen aber weiter ihre ganze Folge (sekundäres Clustering). Beim Doppel-Hashing hängt auch die Schrittweite vom Schlüssel ab.
Wann die Sondierfolgen alle Plätze treffen
(a) Doppel-Hashing: Die Folge für trifft genau dann alle Plätze, wenn . Bei prim genügt , wie bei .
(b) Quadratisches Sondieren: Ist eine Primzahl, dann sind die Plätze für paarweise verschieden. Sind höchstens Plätze belegt, findet also stets einen freien.
(a) Zwei Versuche treffen denselben Platz genau dann, wenn die Zahl teilt. Ist der ggT gleich , muss dann teilen, unmöglich wegen . Ist der ggT , treffen und denselben Platz, denn ist ein Vielfaches von .
(b) Angenommen, treffen denselben Platz. Dann teilt die Zahl . Weil prim ist, teilt einen der Faktoren (Lemma von Euklid). Aber und , Widerspruch. Die ersten Versuche treffen also verschiedene Plätze, und bei höchstens belegten ist einer davon frei.
Eine Tabelle hat Plätze, und für einen Schlüssel ist und . Wie viele verschiedene Plätze besucht seine Sondierfolge beim Doppel-Hashing?
Erwartete Versuche bei offener Adressierung
Annahme (gleichverteiltes Hashing): Die Sondierfolge jedes Schlüssels ist mit gleicher Wahrscheinlichkeit jede der Anordnungen der Plätze, unabhängig von den anderen Schlüsseln. Dann braucht eine erfolglose Suche bei Belegungsfaktor im Erwartungswert höchstens so viele Versuche:
Sei die Zahl der Versuche einer erfolglosen Suche. Mindestens Versuche () braucht sie genau dann, wenn die ersten besuchten Plätze belegt sind. Der erste ist mit Wahrscheinlichkeit belegt; ist er es, ist der zweite gleichverteilt unter den übrigen Plätzen, von denen belegt sind, und so weiter. Wegen für folgt . Für eine Zufallsvariable mit Werten in ist , und mit der geometrischen Reihe
Löschen durch Leeren des Platzes
Löschen durch Leeren des Platzes
In der linearen Tabelle oben wird gelöscht, indem Platz wieder wird. Danach sucht jemand : Versuch ist Platz mit dem Schlüssel , Versuch ist Platz , und der ist frei. meldet „fehlt“, obwohl auf Platz steht. Der geleerte Platz hat die Sondierfolge von unterbrochen.
Man setzt beim Löschen einen Grabstein, einen besonderen Wert . Die Suche behandelt ihn wie einen belegten Platz mit falschem Schlüssel und sucht weiter; nur beendet sie. Einfügen darf einen Grabstein überschreiben, nachdem die Suche bestätigt hat, dass der Schlüssel fehlt: mit landet so auf Platz . 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.
Rehashing ist amortisiert billig
Eine Tabelle beginnt leer mit Plätzen. Wird nach einer Einfügung (eine feste Schranke, etwa ), 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 Einfügungen insgesamt höchstens Schlüssel neu eingefügt. Kostet jedes Einfügen bei erwartet , so kosten die Einfügungen zusammen erwartet , also amortisiert je Einfügung.
Beweisidee: wie beim dynamischen Array, die Kosten der Umbauten bilden eine geometrische Reihe.
Es gebe Umbauten (ohne Umbau ist nichts zu zeigen). Der -te () findet bei Plätzen statt, sobald , und fügt höchstens Schlüssel neu ein. Weil der letzte Umbau stattfand, gilt am Ende , und , weil jeder Umbau von einer eigenen Einfügung ausgelöst wird. Zusammen werden höchstens so viele Schlüssel neu eingefügt:
Zusammenfassung
Ein Wörterbuch speichert Paare aus Schlüssel und Wert. Eine Hashtabelle legt den Schlüssel bei ab; Kollisionen sind unvermeidlich, schon bei wenigen Schlüsseln (Geburtstagsparadoxon).
Divisionsmethode mit prim und fern von Zweierpotenzen; Multiplikationsmethode , bei der beliebig sein darf.
Verkettung: eine Liste je Platz. Unter einfachem gleichverteiltem Hashing kostet Suchen erwartet mit .
Offene Adressierung: Sondierfolge linear, quadratisch oder mit Doppel-Hashing; Doppel-Hashing braucht .
Unter gleichverteiltem Hashing braucht eine erfolglose Suche erwartet höchstens Versuche. Lineares Sondieren ist wegen primären Clusterings bei hohem deutlich schlechter.
Löschen bei offener Adressierung setzt Grabsteine, sonst brechen Suchfolgen ab.
Rehashing verdoppelt , wenn eine Schranke übersteigt. Das kostet einzeln , amortisiert je Einfügung.
Alle -Aussagen sind Erwartungswerte unter Annahmen; im schlechtesten Fall kostet Suchen .
Übungen
Berechne nach der Multiplikationsmethode mit und den Hashwert von .
Eine leere Tabelle hat Plätze, und lineares Sondieren. Eingefügt werden nacheinander . Auf welchem Platz landet ?
Eine Tabelle mit Doppel-Hashing hat Plätze. Welche zweite Hashfunktion sorgt dafür, dass die Sondierfolge jedes Schlüssels alle Plätze trifft?
Eine Hashtabelle beginnt leer mit Plätzen. Wird nach einer Einfügung , wird 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 Schlüssel eingefügt werden?
Eine Tabelle mit offener Adressierung und Grabsteinen hat Plätze. Abwechselnd wird ein neuer Schlüssel eingefügt und ein vorhandener gelöscht, sodass stets höchstens 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 je Operation sind.