Doppel-Hashing

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. $s (j, k) := j \cdot h^{'} (k)$ , und die angewendet wird, falls der durch die primäre Hash-Funktion $h (k)$ berechnete Index bereits besetzt ist.

Die vollständige Hash-Funktion lautet dann: $h (k) - s (j, k)$ , 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 $s (j, k)$ soll dabei eine Permutation der Indizes der Hash-Tabelle bilden.

Die Folge von Hash-Funktionen, die nun mittels $h$ und $h^{'}$ gebildet werden, sieht so aus:

$h_{j} (k) = (h (k) + h^{'} (k) \cdot j) mod m$

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 $h$ und $h^{'}$ angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. $h (k) = h (y) \land h^{'} (k) = h^{'} (y)$ , kleiner gleich $1 / m^{2}$ und damit minimal ist, wobei $m$ die Größe des Arrays ist.

Beispiele

Beispielfunktionen

Größe des Arrays: m

Indizes: {0; m-1}

Primäre Hash-Funktion: $h (k) := k mod m$ (Divisions-Rest-Methode)

Sekundäre Hash-Funktion: $h^{'} (k) := k mod (m - 2) + 1$

Sondierungsfunktion: $s (j, k) := j \cdot (k mod (m - 2) + 1)$

Vollständige Doppel-Hash-Funktion: $h_{j} (k) := (k mod m + j \cdot (k mod (m - 2) + 1)) mod m$

Berechnungsbeispiel

Größe des Arrays: m = 7

Hashfunktionen: $h (k) := k mod 7$; $h^{'} (k) := k mod 5 + 1$

Sondierungsfunktion: $h_{j} (k) := (h (k) + j \cdot h^{'} (k)) mod m$

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 $k = 31$ :

$k = 10$ sowie $k = 19$ erzeugen keine Kollision und benötigen deshalb nicht die Doppel-Hash-Funktion $h_{j}$ . Der Index der Hash-Funktion $h$ kann hier abgelesen werden. $k = 31$ erzeugt eine Kollision im Array an der Stelle $3$ , weshalb man nun die Doppel-Hash-Funktion $h_{j}$ mit $j = 1$ :

h_{1} (31) = (h (31) + 1 \cdot h^{'} (31)) mod 7 \equiv (3 + 1 \cdot 2) mod 7 \equiv 5 mod 7 \equiv 5

Die Stelle $5$ erzeugt wieder eine Kollision, weshalb $h_{j}$ nun mit $j = 2$ aufgerufen wird:

h_{2} (31) = (h (31) + 2 \cdot h^{'} (31)) mod 7 \equiv (3 + 2 \cdot 2) mod 7 \equiv 7 mod 7 \equiv 0

Die Stelle $0$ ist frei und erhält somit den Inhalt $31$ .

Doppel-Hashing

Unabhängigkeit der Hashfunktionen

Beispiele

Beispielfunktionen

Berechnungsbeispiel

Weblinks