www.wikidata.de-de.nina.az

Doppel Hashing Beim Doppelstreuwertverfahren oder englisch double hashing handelt es sich um eine Methode zur Realisieru

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 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 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 Bearbeiten

Beispielfunktionen Bearbeiten

Größe des Arrays: m

Indizes: {0; m-1}

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

Sekundäre Hash-Funktion:

Sondierungsfunktion:

Vollständige Doppel-Hash-Funktion:

Berechnungsbeispiel Bearbeiten

Größe des Arrays: m = 7

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 :

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 .

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Uberlaufer in der Hash Tabelle unterzubringen anstatt sie innerhalb der Zelle z B als Liste zu speichern Offene Hash Verfahren konnen Eintrage doppelt belegen und benotigen 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 sekundare Hash Funktion beinhaltet z B s j k j h k displaystyle s j k j cdot h k und die angewendet wird falls der durch die primare Hash Funktion h k displaystyle h k berechnete Index bereits besetzt ist Die vollstandige Hash Funktion lautet dann h k s j k displaystyle h k s j k wobei j die Anzahl bereits ausprobierter Indizes ist d h dass j jedes Mal um 1 erhoht wird wenn ein Index bereits belegt ist Die Sondierungsfunktion s j k displaystyle s j k soll dabei eine Permutation der Indizes der Hash Tabelle bilden Die Folge von Hash Funktionen die nun mittels h displaystyle h und h displaystyle h gebildet werden sieht so aus h j k h k h k j mod m displaystyle h j k h k h k cdot j bmod m Die Kosten fur diese Methode sind nahe den Kosten fur ein ideales Hashing Inhaltsverzeichnis 1 Unabhangigkeit der Hashfunktionen 2 Beispiele 2 1 Beispielfunktionen 2 2 Berechnungsbeispiel 3 WeblinksUnabhangigkeit der Hashfunktionen BearbeitenBeim Doppel Hashing werden zwei unabhangige Hash Funktionen h displaystyle h nbsp und h displaystyle h nbsp angewandt Diese heissen unabhangig wenn die Wahrscheinlichkeit fur eine sogenannte Doppelkollision d h h k h y h k h y displaystyle h k h y land h k h y nbsp kleiner gleich 1 m 2 displaystyle 1 m 2 nbsp und damit minimal ist wobei m displaystyle m nbsp die Grosse des Arrays ist Beispiele BearbeitenBeispielfunktionen Bearbeiten Grosse des Arrays mIndizes 0 m 1 Primare Hash Funktion h k k mod m displaystyle h k k bmod m nbsp Divisions Rest Methode Sekundare Hash Funktion h k k mod m 2 1 displaystyle h k k bmod m 2 1 nbsp Sondierungsfunktion s j k j k mod m 2 1 displaystyle s j k j cdot k bmod m 2 1 nbsp Vollstandige Doppel Hash Funktion h j k k mod m j k mod m 2 1 mod m displaystyle h j k k bmod m j cdot k bmod m 2 1 bmod m nbsp Berechnungsbeispiel Bearbeiten Grosse des Arrays m 7 Hashfunktionen h k k mod 7 displaystyle h k k bmod 7 nbsp h k k mod 5 1 displaystyle h k k bmod 5 1 nbsp Sondierungsfunktion h j k h k j h k mod m displaystyle h j k h k j cdot h k bmod m nbsp Hashtabelle k 10 19 31 22 14 16h 3 5 3 1 0 2h 1 5 2 3 5 2Das mit Hilfe von Hashtabelle und Sondierungsfunktion gefullte Array 0 1 2 3 4 5 631 22 16 10 19 14Erklarung am Beispiel k 31 displaystyle k 31 nbsp k 10 displaystyle k 10 nbsp sowie k 19 displaystyle k 19 nbsp erzeugen keine Kollision und benotigen deshalb nicht die Doppel Hash Funktion h j displaystyle h j nbsp Der Index der Hash Funktion h displaystyle h nbsp kann hier abgelesen werden k 31 displaystyle k 31 nbsp erzeugt eine Kollision im Array an der Stelle 3 displaystyle 3 nbsp weshalb man nun die Doppel Hash Funktion h j displaystyle h j nbsp mit j 1 displaystyle j 1 nbsp h 1 31 h 31 1 h 31 mod 7 3 1 2 mod 7 5 mod 7 5 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 nbsp Die Stelle 5 displaystyle 5 nbsp erzeugt wieder eine Kollision weshalb h j displaystyle h j nbsp nun mit j 2 displaystyle j 2 nbsp aufgerufen wird h 2 31 h 31 2 h 31 mod 7 3 2 2 mod 7 7 mod 7 0 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 nbsp Die Stelle 0 displaystyle 0 nbsp ist frei und erhalt somit den Inhalt 31 displaystyle 31 nbsp Weblinks BearbeitenGeschlossenes Hashing Offenes Hashing Abgerufen von https de wikipedia org w index php title Doppel Hashing amp oldid 200497694