Beim Doppelstreuwertverfahren oder Doppel-Hashing (englisch double hashing) handelt es sich um eine Methode zur Realisierung eines geschlossenen Hash-Verfahrens.
In geschlossenen Hash-Verfahren wird versucht, Überläufer in der Hash-Tabelle unterzubringen, anstatt sie innerhalb der Zelle (z. B. als Liste) zu speichern. (Offene Hash-Verfahren können Einträge doppelt belegen und benötigen daher keine Sondierung.)
Achtung: Wie es im Artikel Hashtabelle unter „Varianten des Hashverfahrens“ steht, werden die Bezeichnungen „offenes“ bzw. „geschlossenes Hashing“ auch in genau umgekehrter Bedeutung verwendet.
Um dies umzusetzen, verwendet man beim Doppel-Hashing eine Sondierungsfunktion, die eine sekundäre Hash-Funktion beinhaltet, z. B. , und die angewendet wird, falls der durch die primäre Hash-Funktion berechnete Index bereits besetzt ist.
Die vollständige Hash-Funktion lautet dann: , wobei j die Anzahl bereits „ausprobierter“ Indizes ist, d. h., dass j jedes Mal um 1 erhöht wird, wenn ein Index bereits belegt ist.
Die Sondierungsfunktion soll dabei eine Permutation der Indizes der Hash-Tabelle bilden.
Die Folge von Hash-Funktionen, die nun mittels und gebildet werden, sieht so aus:
Die Kosten für diese Methode sind nahe den Kosten für ein ideales Hashing.
Unabhängigkeit der Hashfunktionen
Beim Doppel-Hashing werden zwei unabhängige Hash-Funktionen und angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. , kleiner gleich und damit minimal ist, wobei die Größe des Arrays ist.
Beispiele
Beispielfunktionen
Größe des Arrays: m
Indizes: {0; m-1}
Primäre Hash-Funktion: (Divisions-Rest-Methode)
Sekundäre Hash-Funktion:
Sondierungsfunktion:
Vollständige Doppel-Hash-Funktion:
Berechnungsbeispiel
Größe des Arrays: m = 7
- Hashfunktionen
- Sondierungsfunktion
Hashtabelle:
k |
10 |
19 |
31 |
22 |
14 |
16
|
h |
3 |
5 |
3 |
1 |
0 |
2
|
h' |
1 |
5 |
2 |
3 |
5 |
2
|
Das mit Hilfe von Hashtabelle und Sondierungsfunktion gefüllte Array:
0 |
1 |
2 |
3 |
4 |
5 |
6
|
31 |
22 |
16 |
10 |
- |
19 |
14
|
Erklärung am Beispiel :
sowie erzeugen keine Kollision und benötigen deshalb nicht die Doppel-Hash-Funktion . Der Index der Hash-Funktion kann hier abgelesen werden. erzeugt eine Kollision im Array an der Stelle , weshalb man nun die Doppel-Hash-Funktion mit :
Die Stelle erzeugt wieder eine Kollision, weshalb nun mit aufgerufen wird:
Die Stelle ist frei und erhält somit den Inhalt .
Weblinks