Quadratic probing
Uit Wikipedia, de vrije encyclopedia
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:
- mod m, met i = 0,1,2, ... en