imported>SchlurcherBot: Bot: http → https

2026-01-10T21:20:56Z

Bot: http → https

Neue Seite

Beim '''Doppelstreuwertverfahren''' oder '''Doppel-Hashing''' ({{enS|double hashing}}) handelt es sich um eine Methode zur Realisierung eines ''geschlossenen [[Hashfunktion|Hash-Verfahrens]]''.
In geschlossenen Hash-Verfahren wird versucht, Überläufer ''in'' der [[Hashtabelle|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:

{| class="wikitable"
|- class="hintergrundfarbe5"
!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:

{| class="wikitable"
|- class="hintergrundfarbe8"
! 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>.

== Weblinks ==
* [https://www-lehre.inf.uos.de/~ainf/2003/skript/node78.html Geschlossenes Hashing]
* [https://www-lehre.inf.uos.de/~ainf/2004/skript/node78.html Offenes Hashing]

[[Kategorie:Hash]]

Doppel-Hashing - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https