Quadratic Probing

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:

$H + 1^2 , H + 2^2 , H + 3^2 , H + 4^2 , ... , H + k^2$

Quadratic probing can be a more efficient algorithm in an open addressing table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune. It also provides good memory caching because it preserves some locality of reference; however, linear probing has greater locality and, thus, better cache performance.

Quadratic function

Let ''h''(''k'') be a hash function that maps an element ''k'' to an integer in , ''m''−1 where ''m'' is the size of the table. Let the ''i''^th probe position for a value ''k'' be given by the function
:$h(k,i) = h(k) + c_1 i + c_2 i^2 \pmod$
where ''c''₂ ≠ 0 (If ''c''₂ = 0, then ''h''(''k'',''i'') degrades to a linear probe). For a given hash table, the values of ''c''₁ and ''c''₂ remain constant.

Examples:
*If $h(k,i) = (h(k) + i + i^2) \pmod$, then the probe sequence will be $h(k), h(k)+2, h(k)+6, ...$
*For ''m'' = 2^''n'', a good choice for the constants are ''c''₁ = ''c''₂ = 1/2, as the values of ''h''(''k'',''i'') for ''i'' in , ''m''−1are all distinct. This leads to a probe sequence of $h(k), h(k)+1, h(k)+3, h(k)+6, ...$ (the triangular numbers) where the values increase by 1, 2, 3, ...
*For prime ''m'' > 2, most choices of ''c''₁ and ''c''₂ will make ''h''(''k'',''i'') distinct for ''i'' in , (''m''−1)/2 Such choices include ''c''₁ = ''c''₂ = 1/2, ''c''₁ = ''c''₂ = 1, and ''c''₁ = 0, ''c''₂ = 1. However, there are only ''m''/2 distinct probes for a given element, requiring other techniques to guarantee that insertions will succeed when the load factor exceeds 1/2.
*For $m = n^p$, where ''m'', ''n'', and ''p'' are integer greater or equal 2 (degrades to linear probe when ''p'' = 1), then $h(k,i) = (h(k) + i + ni^2)\pmod$ gives cycle of all distinct probes. It can be computed in loop as: $h(k, 0) = h(k)$, and $h(k, i+1) = (h(k,i) + 2in+n+1)\pmod$
*For any ''m'', full cycle with quadratic probing can be achieved by rounding up ''m'' to closest power of 2, compute probe index: $h(k,i) = h(k) + ((i^2+i)/2)\pmod$, and skip iteration when $h(k,i)>=m$. There is maximum $roundUp2(m)-m < m/2$ skipped iterations, and these iterations do not refer to memory, so it is fast operation on most modern processors. Rounding up ''m'' can be computed by:

uint64_t roundUp2(uint64_t v)

Limitations

Alternating signs

If the sign of the offset is alternated (e.g. +1, −4, +9, −16, etc.), and if the number of buckets is a prime number $p$ congruent to 3 modulo 4 (e.g. 3, 7, 11, 19, 23, 31, etc.), then the first $p$ offsets will be unique (modulo $p$). In other words, a permutation of 0 through $p-1$ is obtained, and, consequently, a free bucket will always be found as long as at least one exists.

References

{{Reflist

External links

Tutorial/quadratic probing

Hashing
Articles with example C code
Articles with example Java code
Search algorithms