Doppel-Hashing

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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) ~ \bmod ~ m

Die Kosten für diese Methode sind nahe den Kosten für ein ideales Hashing.

Unabhängigkeit der Hashfunktionen[Bearbeiten]

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^2 und damit minimal ist.

Beispiele[Bearbeiten]

Beispielfunktionen[Bearbeiten]

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) := 1+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[Bearbeiten]

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

Erklärung am Beispiel 31: Warum bekommt die 31 den Index 0? Die 10 und die 19 brauchen keine zweite Hash-Funktion (i=0), und der Index von h1 kann direkt genommen werden, da das Array an den Stellen 3 und 5 noch frei ist. Mit h_{1} = 31\;mod\;7 = 3 tritt eine Kollision auf, denn die 3 ist schon belegt. Nun nimmt man die zweite Hash-Funktion:

h(31,1) = (h_{1}(31)+1*h_{2}(31))\;\bmod\;7 = (3+1*2)\;\bmod\;7 = 5\;\bmod\;7 = 5

Die Stelle 5 ist aber auch schon belegt, also geht es weiter mit i=2:

h(31,2) = (h_{1}(31)+2*h_{2}(31))\;\bmod\;7 = (3+2*2)\;\bmod\;7 = 7\;\bmod\;7 = 0

Die Stelle 0 ist frei und somit bekommt die 31 den Index 0.

Weblinks[Bearbeiten]