Kuckucks-Hashing
Kuckucks-Hashing (englisch cuckoo hashing) ist ein Algorithmus, der mittels zweier Hashfunktionen den Index in einer Tabelle berechnet, an dem das Element eingefügt werden soll. Er wurde 2001 von Rasmus Pagh und Flemming Friche Rodler entwickelt.[1] Seinen Namen hat er von dem Kuckuck, der seine Eier in fremde Nester legt und dessen Küken die Eier der Wirtseltern aus dem Nest stoßen.
Funktionsweise
Jede der beiden Hashfunktionen berechnet den Index eines einzufügenden Elementes jeweils für eine Tabelle. Zuerst wird geprüft, ob das einzufügende Element mit der Hashfunktion in die Tabelle an der Stelle eingefügt werden kann. Ist das der Fall, dann wird das Element dort eingefügt. Wenn der Platz jedoch schon belegt ist, dann wird mit der zweiten Hashfunktion der Platz in der zweiten Tabelle berechnet und wenn dieser frei ist, dort eingefügt. Ist jedoch der Platz auch belegt, wird das einzufügende Element in die erste Tabelle eingefügt und das Element, das dort vorher war in die zweite Tabelle verschoben. Wenn nun dort wieder eine Kollision auftritt, dann wird das Element von dort wieder in die erste Tabelle verlegt. Ist der Platz in der ersten Tabelle frei ist das Einfügen beendet. Sollte jedoch auch hier wieder ein Element den Platz belegen, dann wird es wieder in die zweite Tabelle verschoben. Dieses Verfahren wiederholt man so lange, bis ein freier Platz gefunden wurde. Es kann jedoch vorkommen, dass die gleiche Tabellenkonstellation wie zu Beginn auftritt, damit gerät das Verfahren dann in einen Zyklus (Endlosschleife). In diesem Fall wird die Tabelle mit neuen Hashfunktionen neu aufgebaut.
Pseudocode
Insert(T1,T2,x):
// key[x] schon in Hashtabelle?
if T1[h1(key[x])]=NIL or key[T1[h1(key[x])]]=key[x] then
T1[h1(key[x])]←x; return
if T2[h2(key[x])]=NIL or key[T2[h2(key[x])]]=key[x] then
T2[h2(key[x])] ←x; return
// nein, dann einfügen
while true do
x↔T1[h1(key[x])] // tausche x mit Pos. in T1
if x=NIL then return
x↔T2[h2(key[x])] // tausche x mit Pos. in T2
if x=NIL then return
Beispiel
Folgende Hashfunktionen sind gegeben:
| k | h(k) | h'(k) |
|---|---|---|
| 20 | 9 | 1 |
| 50 | 6 | 4 |
| 53 | 9 | 4 |
| 75 | 9 | 6 |
| 100 | 1 | 9 |
| 67 | 1 | 6 |
| 105 | 6 | 9 |
| 3 | 3 | 0 |
| 36 | 3 | 3 |
| 39 | 6 | 3 |
| 1. Tabelle für h(k) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| 0 | ||||||||||
| 1 | 100 | 67 | 67 | 67 | 67 | 100 | ||||
| 2 | ||||||||||
| 3 | 3 | 3 | 36 | |||||||
| 4 | ||||||||||
| 5 | ||||||||||
| 6 | 50 | 50 | 50 | 50 | 50 | 105 | 105 | 105 | 50 | |
| 7 | ||||||||||
| 8 | ||||||||||
| 9 | 20 | 20 | 20 | 20 | 20 | 20 | 53 | 53 | 53 | 75 |
| 10 | ||||||||||
| 2. Tabelle für h'(k) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| 0 | 3 | |||||||||
| 1 | 20 | 20 | 20 | 20 | ||||||
| 2 | ||||||||||
| 3 | 36 | 39 | ||||||||
| 4 | 53 | 53 | 53 | 53 | 50 | 50 | 50 | 53 | ||
| 5 | ||||||||||
| 6 | 75 | 75 | 75 | 75 | 75 | 75 | 67 | |||
| 7 | ||||||||||
| 8 | ||||||||||
| 9 | 100 | 100 | 100 | 100 | 105 | |||||
| 10 | ||||||||||
Zyklus
Möchte man nun das Element 6 einfügen, dann gerät man in einen Zyklus. In der letzten Zeile der Tabelle findet sich die gleiche Ausgangssituation wie zu Beginn wieder.
| betrachteter Schlüssel | Tabelle 1 | Tabelle 2 | ||
| alter Wert | neuer Wert | alter Wert | neuer Wert | |
| 6 | 50 | 6 | 53 | 50 |
| 53 | 75 | 53 | 67 | 75 |
| 67 | 100 | 67 | 105 | 100 |
| 105 | 6 | 105 | 3 | 6 |
| 3 | 36 | 3 | 39 | 36 |
| 39 | 105 | 39 | 100 | 105 |
| 100 | 67 | 100 | 75 | 67 |
| 75 | 53 | 75 | 50 | 53 |
| 50 | 39 | 50 | 36 | 39 |
| 36 | 3 | 36 | 6 | 3 |
| 6 | 50 | 6 | 53 | 50 |