Double hashing

In de informatica is double hashing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een tweede hashfunctie verhoogd totdat een positie gevonden is.

De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel:

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

Voorbeeld

Visuele weergave van de werking van double hashing in het voorbeeld

We nemen een hashtabel met plaats voor 11 items met enkele plaatsen al bezet (namelijk 0, 4, 5, 6, 7 en 10). Dit geeft:

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

We willen een item invoegen met als eerste hashwaarde 22 (dus $h_{1}(k)=22$) en als tweede hashwaarde 4 (dus $h_{2}(k)=4$). Het invoegen verloopt als volgt:

(22 + 0 * 4) mod 11 = 0, collisie want deze plaats is al bezet

(22 + 1 * 4) mod 11 = 4, collisie

(22 + 2 * 4) mod 11 = 8, geen collisie dus het item kan hier ingevoegd worden.

Zie ook

• Linear probing
• Quadratic probing