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_i(k) = (h(k)-h'(k)\cdot j) ~ \bmod ~ 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) \and h'(k)=h'(y)$ gleich 1 / m² und damit minimal ist.

Beispiele

Beispielfunktionen

Größe des Arrays: m

Indizes: {0; m-1}

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

Sekundäre Hash-Funktion: $\;h'(k) := k\;\bmod\;(m-2)$

Sondierungsfunktion: $\;s(j,k) := j\cdot k\;\bmod\;(m-2)$

Vollständige Doppel-Hash-Funktion: $\;dh(j,k) := k\;\bmod\;m - j\cdot (k\;\bmod\;(m-2))$

Berechnungsbeispiel

Größe des Arrays: m = 7

Hashfunktionen

$h_{1}(k) := k\;\bmod\;7$

$h_{2}(k) := 1+(k\;\bmod\;5)$

Sondierungsfunktion 

$h(k,i) := (h_{1}(k)+ih_{2}(k))\;\bmod\;m$

Hashtabelle:

k	10	19	31	22	14	16
h1	3	5	3	1	0	2
h2	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

Weblinks

• Geschlossenes Hashing
• Offenes Hashing