Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables.
Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.
An example sequence using quadratic probing is:
[1] Quadratic probing exhibits better locality of reference than many other hash table such as chaining; however, for queries, quadratic probing does not have as good locality as linear probing, causing the latter to be faster in some settings.
[2] Quadratic probing was first introduced by Ward Douglas Maurer in 1968.
[3] Let h(k) be a hash function that maps an element k to an integer in [0, m−1], where m is the size of the table.
For a given hash table, the values of c1 and c2 remain constant.
[further explanation needed] In other words, a permutation of 0 through
is obtained, and, consequently, a free bucket will always be found as long as at least one exists.