Linear probing
In de informatica is linear 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 standaard stapgrootte (meestal 1) verhoogd totdat een positie gevonden is (zolang de hashtabel niet vol 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) mod m, met i = 0,1,2, ... (stapgrootte is hierbij 1)
Linear probing heeft als nadeel dat een lege positie naast een lang aaneengesloten stuk een grotere kans heeft om bezet te worden dan een lege positie naast een korter stuk (of naast een lege positie): lange aaneengesloten stukken hebben een grotere kans om nog langer te worden. Hierdoor worden de items in de hashtabel niet zo goed gespreid als gewenst.
Voorbeeld bewerken
We nemen een hashtabel met plaats voor 11 items met enkele plaatsen al bezet (namelijk 0, 4, 5, 6, 7 en 10) en stapgrootte 1 (in de praktijk is dit de meest gekozen stapgrootte). Dit geeft:
- (h(k) + i) mod 11, met i = 0,1,2, ...
We willen een item invoegen met hashwaarde 54 (dus h(k) = 54). Het invoegen verloopt als volgt:
- (54 + 0) mod 11 = 10, collisie want deze plaats is al bezet
- (54 + 1) mod 11 = 0, collisie
- (54 + 2) mod 11 = 1, geen collisie dus het item kan hier ingevoegd worden.