Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


16. Hashing



Doppeltes Hashing

Lineares Austesten (wie jedes Hashing-Verfahren) führt zum Ziel, weil es garantiert, daß wir, wenn wir einen bestimmten Schlüssel suchen, jeden Schlüssel betrachten, der durch die Hash-Funktion auf die gleiche Tabellenadresse abgebildet wird (insbesondere den Schlüssel selbst, wenn er in der Tabelle ist). Leider werden beim linearen Austesten auch andere Schlüssel untersucht, speziell dann, wenn sich die Tabelle zu füllen beginnt; im obigen Beispiel erfordert die Suche nach X das Betrachten von G, H und I, wobei keiner dieser Schlüssel den gleichen Wert der Hash-Funktion hatte. Was noch schlimmer ist, das Einfügen eines Schlüssels mit einem Hash-Wert kann eine drastische Erhöhung der Suchzeiten für Schlüssel mit anderen Hash-Werten bewirken: Im Beispiel würde ein Einfügen auf Position 17 beträchtlich erhöhte Suchzeiten für Position 16 bewirken. Diese Erscheinung, die Anhäufung (clustering) genannt wird, kann dazu führen, daß lineares Austesten für fast volle Tabellen sehr langsam abläuft. Abbildung 16.5 zeigt die Bildung von Anhäufungen in einem umfangreicheren Beispiel.

Abbildung 16.5
Abbildung 16.5 Lineares Austesten einer umfangreicheren Datei.

Zum Glück gibt es einen einfachen Weg, wie das Problem des Anhäufens praktisch beseitigt werden kann: Doppeltes Hashing. Die zugrundeliegende Strategie ist die gleiche; der einzige Unterschied ist, daß wir, anstatt der Reihe nach die Eintragungen zu betrachten, die einer Position mit Kollision folgen, eine zweite Hash-Funktion benutzen, um ein festes Inkrement zu erhalten, das für die »Test«-Folge verwendet wird. Dies läßt sich leicht implementieren, indem man am Anfang der Prozedur u:=h2(v) einfügt und in der while-Schleife x:=(x+1) mod M in x:=(x+u) mod M abändert.

Die zweite Hash-Funktion h2 muß mit einiger Sorgfalt gewählt werden, da das Programm andernfalls möglicherweise überhaupt nicht funktioniert. Erstens darf offenbar nicht u=0 gelten, da dies bei Kollision zu einer Endlosschleife führen würde. Zweitens ist es wesentlich, daß M und u zueinander prim sind, da sonst einige der Testfolgen sehr kurz sein könnten (man betrachte den Fall M = 2u). Das läßt sich leicht erreichen, indem man M prim und u < M wählt. Drittens sollte sich die zweite Hash-Funktion von der ersten »unterscheiden«, da andernfalls eine noch etwas kompliziertere Anhäufung auftreten könnte. Eine Funktion der Art h2(k) = M - 2 - k mod (M - 2) würde eine gute Reihe von »zweiten« Hash-Werten erzeugen, doch würde dies vielleicht zu weit gehen, da insbesondere für lange Schlüssel die Kosten für die Berechnung der zweiten Hash-Funktion im Prinzip die Kosten der Suche verdoppeln, nur um durch die Beseitigung der Anhäufung einige Tests einzusparen. In der Praxis ist eine viel einfachere zweite Hash-Funktion ausreichend, wie etwa h2(k) = 8 - (k mod 8). Diese Funktion verwendet nur die letzten drei Bits von k; es könnte zweckmäßig sein, für eine umfangreiche Tabelle einige weitere Bits zu verwenden, obwohl der Effekt, selbst wenn er spürbar ist, in der Praxis nicht entscheidend sein dürfte.

Für unser Beispiel von Schlüsseln erzeugen diese Funktionen die Hash-Werte, die in Abbildung 16.6 angegeben sind. Abbildung 16.7 zeigt die Tabelle, die durch sukzessives Einfügen unserer Beispielschlüssel in eine ursprünglich leere Tabelle bei Anwendung von doppeltem Hashing mit Hilfe dieser Werte erzeugt wird.

Abbildung 16.6
Abbildung 16.6 Doppelte Hash-Funktion (M=19).

Abbildung 16.7
Abbildung 16.7 Doppeltes Hashing.

Die durchschnittliche Anzahl der Elemente, die bei einer erfolgreichen Suche betrachtet werden, ist für dieses Beispiel etwas größer als beim linearen Austesten: 35/17 rund 2,05. In einer weniger dicht gefüllten Tabelle tritt jedoch weit weniger Anhäufung auf, wie Abbildung 16.8 zeigt. In diesem Beispiel treten doppelt so viele Anhäufungen auf wie beim linearen Austesten (Abbildung 16.5) oder, was dasselbe ist, die Anhäufungen sind im Durchschnitt etwa halb so lang.

Abbildung 16.8
Abbildung 16.8 Doppeltes Hashing in einer umfangreicheren Tabelle.

Eigenschaft 16.3 Doppeltes Hashing erfordert im Durchschnitt weniger Tests als lineares Austesten.

Die exakte Formel für die durchschnittliche Zahl der Tests, die bei doppeltem Hashing mit einer »unabhängigen« zweiten Hash-Funktion ausgeführt werden, lautet 1/(1-Alpha) für erfolglose und -ln(1 - Alpha)/Alpha für erfolgreiche Suche. (Diese Formeln sind das Ergebnis einer tiefgehenden mathematischen Analyse und sind für große Alpha noch nicht einmal überprüft worden.) Die oben empfohlene einfachere, leicht berechenbare zweite Hash-Funktion verhält sich nicht ganz so gut, doch auch mit ihr kommt man diesem Ergebnis recht nahe, besonders dann, wenn genügend viele Bits verwendet werden, damit der Wertebereich M möglichst nahekommt. In der Praxis bedeutet das, daß man für eine gegebene Anwendung bei doppeltem Hashing eine kleinere Tabelle verwenden kann, um die gleichen Suchzeiten zu erhalten wie beim linearen Austesten; die durchschnittliche Anzahl der Tests beträgt weniger als fünf für eine erfolglose Suche, wenn die Tabelle zu weniger als 80% gefüllt ist, und weniger als fünf für eine erfolgreiche Suche, wenn die Tabelle zu weniger als 99% gefüllt ist. w.z.b.w.

Methoden der offenen Adressierung können in einer dynamischen Situation, wo eine möglicherweise nicht vorhersagbare Anzahl von Einfüg- und Löschoperationen in Hash-Tabellen auszuführen ist, unzweckmäßig sein. Erstens stellt sich die Frage, wie groß die Tabelle sein sollte. Es müßte abgeschätzt werden, wieviel Einfügungen zu erwarten sind, doch das Verhalten verschlechtert sich drastisch, wenn sich die Tabelle zu füllen beginnt. Eine gebräuchliche Lösung für dieses Problem besteht darin, in gewissen (sehr großen) Abständen alles erneut durch eine Hash-Funktion in eine größere Tabelle abzubilden. Zweitens muß beim Löschen mit Vorsicht vorgegangen werden: Ein Datensatz kann nicht einfach aus einer Tabelle entfernt werden, die mit linearem Austesten oder doppeltem Hashing erzeugt wurde. Der Grund hierfür ist, daß spätere Einfügungen in die Tabelle diesen Datensatz übersprungen haben können und eine Suche nach solchen Datensätzen dann bei der Lücke abbricht, die der gelöschte Datensatz hinterlassen hat. Ein Weg zur Lösung dieses Problems ist, einen weiteren speziellen Schlüssel zu verwenden, der als Platzhalter für Suchvorgänge dienen kann, jedoch als eine leere Position für Einfügungen identifiziert und gespeichert werden kann. Beachten Sie, daß bei der getrennten Verkettung weder die Größe der Tabelle noch das Löschen ein besonderes Problem war.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]