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. , und die angewendet wird, falls der durch die primäre Hash-Funktion berechnete Index bereits besetzt ist.

Die vollständige Hash-Funktion lautet dann: , 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 soll dabei eine Permutation der Indizes der Hash-Tabelle bilden.

Die Folge von Hash-Funktionen, die nun mittels und gebildet werden, sieht so aus:

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 und angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. , kleiner gleich und damit minimal ist, wobei die Größe des Arrays ist.

Beispiele

Beispielfunktionen

Größe d​es Arrays: m

Indizes: {0; m-1}

Primäre Hash-Funktion: (Divisions-Rest-Methode)

Sekundäre Hash-Funktion:

Sondierungsfunktion:

Vollständige Doppel-Hash-Funktion:

Berechnungsbeispiel

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

Hashfunktionen
Sondierungsfunktion

Hashtabelle:

k101931221416
h353102
h'152352

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

0123456
31221610-1914

Erklärung am Beispiel :

sowie erzeugen keine Kollision und benötigen deshalb nicht die Doppel-Hash-Funktion . Der Index der Hash-Funktion kann hier abgelesen werden. erzeugt eine Kollision im Array an der Stelle , weshalb man nun die Doppel-Hash-Funktion mit :

Die Stelle erzeugt wieder eine Kollision, weshalb nun mit aufgerufen wird:

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.