For faster navigation, this Iframe is preloading the Wikiwand page for Quadratic probing.

Quadratic probing

Uit Wikipedia, de vrije encyclopedie

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

Voorbeeld

Visuele weergave van de werking van quadratic probing in het 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), en (in de praktijk is dit ook de meest gekozen setting). Dit geeft:

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 + ) mod 11 = 4, collisie want deze plaats is al bezet
(48 + ) mod 11 = 5, collisie
(48 + ) mod 11 = 8, geen collisie dus het item kan hier ingevoegd worden.

Zie ook

{{bottomLinkPreText}} {{bottomLinkText}}
Quadratic probing
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Wikiwand 2.0 is here 🎉! We've made some exciting updates - No worries, you can always revert later on