Quadratic probing

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. Let the i^th probe position for a value k be given by the function

${\displaystyle h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod {m}}}$

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 ${\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}$, then the probe sequence will be ${\displaystyle h(k),h(k)+2,h(k)+6,...}$
• For m = 2ⁿ, a good choice for the constants are c₁ = c₂ = 1/2, as the values of h(k,i) for i in [0, m−1] are all distinct. This leads to a probe sequence of ${\displaystyle 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 [0, (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 is exceeds 1/2.

When using quadratic probing, however (with the exception of triangular number cases for a hash table of size ${\displaystyle 2^{n}}$),[1] there is no guarantee of finding an empty cell once the table becomes more than half full, or even before this if the table size is composite,[2] because collisions must be resolved using half of the table at most.

The inverse of this can be proven as such: Suppose a hash table has size ${\displaystyle p}$ (a prime greater than 3), with an initial location ${\displaystyle h(k)}$ and two alternative locations ${\displaystyle h(k)+x^{2}{\pmod {p}}}$ and ${\displaystyle h(k)+y^{2}{\pmod {p}}}$ (where ${\displaystyle 0\leq x}$ and ${\displaystyle y\leq p/2}$). If these two locations point to the same key space, but ${\displaystyle x\neq y}$, then

${\displaystyle h(k)+x^{2}=h(k)+y^{2}{\pmod {p}}}$

${\displaystyle x^{2}=y^{2}{\pmod {p}}}$

${\displaystyle x^{2}-y^{2}=0{\pmod {p}}}$

${\displaystyle (x-y)(x+y)=0{\pmod {p}}}$.

As ${\displaystyle p}$ is a prime number, either ${\displaystyle (x-y)}$ or ${\displaystyle (x+y)}$ must be divisible by ${\displaystyle p}$. Since ${\displaystyle x}$ and ${\displaystyle y}$ are different (modulo ${\displaystyle p}$), ${\displaystyle (x-y)\neq 0}$, and since both variables are greater than zero, ${\displaystyle (x+y)\neq 0}$. Thus, by contradiction, the first ${\displaystyle p/2}$ alternative locations after ${\displaystyle h(k)}$ must be unique, and subsequently, an empty space can always be found so long as at most ${\displaystyle p/2}$ locations are filled (i.e., the hash table is not more than half full).

• Tutorial/quadratic probing