WikiDer > Doppeltes hashing

In dem Informatik ist doppeltes hashing eine Möglichkeit, Kollisionen ('Kollisionen') beim Einfügen eines Elements in . zu vermeiden Hash-Tabellen helfen. Beim Einfügen an der durch die Hash-Funktion berechnet nicht möglich ist (weil bereits ein Item vorhanden ist), wird diese Position durch eine zweite Hash-Funktion erhöht, bis eine Position gefunden ist.

Die berechnete Position wird modular m berechnet, wobei m die Größe der Hash-Tabelle ist. Dadurch bleibt der berechnete Wert im blijft Intervall [0, m) von ganzen Zahlen und damit innerhalb der Hash-Tabelle:

${Anzeigestil h(k,i)=(h_{1}(k) i*h_{2}(k))}$ mod m, mit i = 0,1,2, ...

Beispiel

Visuelle Darstellung der Funktionsweise von Double Hashing im Beispiel

Nehmen wir eine Hashtabelle mit Platz für 11 Elemente, wobei einige Plätze bereits belegt sind (nämlich 0, 4, 5, 6, 7 und 10). Das gibt:

${Anzeigestil h(k,i)=(h_{1}(k) i*h_{2}(k))}$ mod 11, mit i = 0,1,2, ...

Wir möchten ein Element mit dem ersten Hashwert von 22 einfügen (also ${displaystyle h_{1}(k)=22}$) und als zweiter Hashwert 4 (so ${Anzeigestil h_{2}(k)=4}$). Das Einfügen erfolgt wie folgt:

(22 0 * 4) mod 11 = 0, Kollision, da dieser Platz bereits belegt ist

(22 1 * 4) mod 11 = 4, Kollision

(22 2 * 4) mod 11 = 8, keine Kollision, daher kann das Element hier eingefügt werden.

Siehe auch

• Linearsonde
• Quadratische Sondierung