Quadratic probing

Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables—when an incoming data's hash value indicates it should be stored in an already-occupied slot or bucket. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.

For a given hash value, the indices generated by linear probing are as follows:

${\displaystyle H+1,H+2,H+3,H+4,...,H+k}$

This method results in primary clustering, and as the cluster grows larger, the search for those items hashing within the cluster becomes less efficient.

An example sequence using quadratic probing is:

${\displaystyle H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}}$

...
Wikipedia