Doppel-Hashing
# 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)~{\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)\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\;{\bmod {\;}}m$ (Divisions-Rest-Methode)

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

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

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

### Berechnungsbeispiel

Größe des Arrays: m = 7

**Hashfunktionen**


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

**Sondierungsfunktion**


    $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 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))\;{\bmod {\;}}7\equiv (3+1\cdot 2)\;{\bmod {\;}}7\equiv 5\;{\bmod {\;}}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))\;{\bmod {\;}}7\equiv (3+2\cdot 2)\;{\bmod {\;}}7\equiv 7\;{\bmod {\;}}7\equiv 0$

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

