Doppel-Hashing
Beim Doppelstreuwertverfahren oder Doppel-Hashing ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}) 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. <math>\;s(j,k) := j\cdot h'(k)</math>, und die angewendet wird, falls der durch die primäre Hash-Funktion <math>\;h(k)</math> berechnete Index bereits besetzt ist.
Die vollständige Hash-Funktion lautet dann: <math>\;h(k) - s(j,k)</math>, 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 <math>\;s(j,k)</math> soll dabei eine Permutation der Indizes der Hash-Tabelle bilden.
Die Folge von Hash-Funktionen, die nun mittels <math>h</math> und <math>h'</math> gebildet werden, sieht so aus:
<math>h_j(k) = (h(k)+h'(k)\cdot j) ~ \bmod ~ m</math>
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 <math>h</math> und <math>h'</math> angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. <math>h(k)=h(y) \land h'(k)=h'(y)</math>, kleiner gleich <math>1/m^2</math> und damit minimal ist, wobei <math>m</math> die Größe des Arrays ist.
Beispiele
Beispielfunktionen
Größe des Arrays: m
Indizes: {0; m-1}
Primäre Hash-Funktion: <math>h(k) := k\;\bmod\;m</math> (Divisions-Rest-Methode)
Sekundäre Hash-Funktion: <math>\;h'(k) := k \;\bmod\;(m-2) +1</math>
Sondierungsfunktion: <math>\;s(j,k) := j\cdot (k\;\bmod\;(m-2) +1 )</math>
Vollständige Doppel-Hash-Funktion: <math>\;h_j(k) := (k\;\bmod\;m + j\cdot (k\;\bmod\;(m-2)+1)) \bmod m</math>
Berechnungsbeispiel
Größe des Arrays: m = 7
- Hashfunktionen
- <math>h(k) := k\;\bmod\;7 </math>
- <math>h'(k) := k\;\bmod\;5 +1 </math>
- Sondierungsfunktion
- <math>h_j(k) := (h(k)+j\cdot h'(k))\;\bmod\;m </math>
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 <math>k = 31</math>:
<math>k =10</math> sowie <math>k=19</math> erzeugen keine Kollision und benötigen deshalb nicht die Doppel-Hash-Funktion <math>h_j</math>. Der Index der Hash-Funktion <math>h</math> kann hier abgelesen werden. <math>k = 31</math> erzeugt eine Kollision im Array an der Stelle <math>3</math> , weshalb man nun die Doppel-Hash-Funktion <math>h_j</math> mit <math>j=1</math>:
- <math>h_{1}(31) = (h(31)+1\cdot h'(31))\;\bmod\;7 \equiv (3+1\cdot2)\;\bmod\;7 \equiv 5\;\bmod\;7 \equiv 5</math>
Die Stelle <math>5</math> erzeugt wieder eine Kollision, weshalb <math>h_j</math> nun mit <math>j=2</math> aufgerufen wird:
- <math>h_2(31) = (h(31)+2\cdot h'(31))\;\bmod\;7 \equiv (3+2\cdot 2)\;\bmod\;7 \equiv 7\;\bmod\;7 \equiv 0</math>
Die Stelle <math>0</math> ist frei und erhält somit den Inhalt <math>31</math>.