Quadratic probing

In de informatica is quadratic probing 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 kwadratische functie verhoogd totdat een positie gevonden is of totdat na een aantal keer nog geen positie gevonden is (deze methode garandeert namelijk niet dat een mogelijk nog lege positie ook gevonden wordt).

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(k)+c_{1}i+c_{2}i^{2})$ mod m, met i = 0,1,2, ... en $c_{2}\neq 0$

Voorbeeld

Visuele weergave van de werking van quadratic probing 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), $c_{1}=0$ en $c_{2}=1$ (in de praktijk is dit ook de meest gekozen setting). Dit geeft:

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

We willen een item invoegen met hashwaarde 48 (dus h(k) = 48). Het invoegen verloopt als volgt:

(48 + $0^{2}$) mod 11 = 4, collisie want deze plaats is al bezet

(48 + $1^{2}$) mod 11 = 5, collisie

(48 + $2^{2}$) mod 11 = 8, geen collisie dus het item kan hier ingevoegd worden.

Zie ook

• Linear probing
• Double hashing