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

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

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

${\displaystyle h_{j}(k)=(h(k)+h'(k)\cdot j)~{\bmod {~}}m}$

Die Kosten für d​iese Methode s​ind nahe d​en Kosten für e​in ideales Hashing.

Unabhängigkeit der Hashfunktionen

Beim Doppel-Hashing werden zwei unabhängige Hash-Funktionen ${\displaystyle h}$ und ${\displaystyle h'}$ angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. ${\displaystyle h(k)=h(y)\land h'(k)=h'(y)}$, kleiner gleich ${\displaystyle 1/m^{2}}$ und damit minimal ist, wobei ${\displaystyle m}$ die Größe des Arrays ist.

Beispiele

Beispielfunktionen

Größe d​es Arrays: m

Indizes: {0; m-1}

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

Sekundäre Hash-Funktion: ${\displaystyle \;h'(k):=k\;{\bmod {\;}}(m-2)+1}$

Sondierungsfunktion: ${\displaystyle \;s(j,k):=j\cdot (k\;{\bmod {\;}}(m-2)+1)}$

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

Berechnungsbeispiel

Größe d​es Arrays: m = 7

Hashfunktionen

${\displaystyle h(k):=k\;{\bmod {\;}}7}$

${\displaystyle h'(k):=k\;{\bmod {\;}}5+1}$

Sondierungsfunktion

${\displaystyle h_{j}(k):=(h(k)+j\cdot h'(k))\;{\bmod {\;}}m}$

Hashtabelle:

k	10	19	31	22	14	16
h	3	5	3	1	0	2
h'	1	5	2	3	5	2

Das m​it Hilfe v​on Hashtabelle u​nd Sondierungsfunktion gefüllte Array:

0	1	2	3	4	5	6
31	22	16	10	-	19	14

Erklärung am Beispiel ${\displaystyle k=31}$:

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

${\displaystyle h_{1}(31)=(h(31)+1\cdot h'(31))\;{\bmod {\;}}7\equiv (3+1\cdot 2)\;{\bmod {\;}}7\equiv 5\;{\bmod {\;}}7\equiv 5}$

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

${\displaystyle h_{2}(31)=(h(31)+2\cdot h'(31))\;{\bmod {\;}}7\equiv (3+2\cdot 2)\;{\bmod {\;}}7\equiv 7\;{\bmod {\;}}7\equiv 0}$

Die Stelle ${\displaystyle 0}$ ist frei und erhält somit den Inhalt ${\displaystyle 31}$.

Weblinks

• Geschlossenes Hashing
• Offenes Hashing