Quadratic probing

Quadratic function

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(\mathrm{mod}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)(\mathrm{mod}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 (in fact, it is a permutation on [0, m−1]). 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 exceeds 1/2.
• For ${\displaystyle m=n^p}$, where m, n, and p are integer greater or equal 2 (degrades to linear probe when p = 1), then ${\displaystyle h(k,i)=(h(k)+i+n{i}^2)(\mathrm{mod}m)}$ gives cycle of all distinct probes. It can be computed in loop as: ${\displaystyle h(k,0)=h(k)}$, and ${\displaystyle h(k,i+1)=(h(k,i)+2in+n+1)(\mathrm{mod}m)}$
• For any m, full cycle with quadratic probing can be achieved by rounding up m to closest power of 2, compute probe index: ${\displaystyle h(k,i)=h(k)+((i^2+i)/2)(\mathrm{mod}roundUp2(m))}$, and skip iteration when ${\displaystyle h(k,i)>=m}$. There is maximum ${\displaystyle 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:

<span id="mwvQ"></span><span class="kt" id="mwvg">uint64_t</span><span class="w" id="mwvw"> </span><span class="nf" id="mwwA">roundUp2</span><span class="p" id="mwwQ">(</span><span class="kt" id="mwwg">uint64_t</span><span class="w" id="mwww"> </span><span class="n" id="mwxA">v</span><span class="p" id="mwxQ">){</span> <span class="w" id="mwxg"> </span><span class="n" id="mwxw">v</span><span class="o" id="mwyA">--</span><span class="p" id="mwyQ">;</span> <span class="w" id="mwyg"> </span><span class="n" id="mwyw">v</span><span class="w" id="mwzA"> </span><span class="o" id="mwzQ">|=</span><span class="w" id="mwzg"> </span><span class="n" id="mwzw">v</span><span class="w" id="mw0A"> </span><span class="o" id="mw0Q">>></span><span class="w" id="mw0g"> </span><span class="mi" id="mw0w">1</span><span class="p" id="mw1A">;</span> <span class="w" id="mw1Q"> </span><span class="n" id="mw1g">v</span><span class="w" id="mw1w"> </span><span class="o" id="mw2A">|=</span><span class="w" id="mw2Q"> </span><span class="n" id="mw2g">v</span><span class="w" id="mw2w"> </span><span class="o" id="mw3A">>></span><span class="w" id="mw3Q"> </span><span class="mi" id="mw3g">2</span><span class="p" id="mw3w">;</span> <span class="w" id="mw4A"> </span><span class="n" id="mw4Q">v</span><span class="w" id="mw4g"> </span><span class="o" id="mw4w">|=</span><span class="w" id="mw5A"> </span><span class="n" id="mw5Q">v</span><span class="w" id="mw5g"> </span><span class="o" id="mw5w">>></span><span class="w" id="mw6A"> </span><span class="mi" id="mw6Q">4</span><span class="p" id="mw6g">;</span> <span class="w" id="mw6w"> </span><span class="n" id="mw7A">v</span><span class="w" id="mw7Q"> </span><span class="o" id="mw7g">|=</span><span class="w" id="mw7w"> </span><span class="n" id="mw8A">v</span><span class="w" id="mw8Q"> </span><span class="o" id="mw8g">>></span><span class="w" id="mw8w"> </span><span class="mi" id="mw9A">8</span><span class="p" id="mw9Q">;</span> <span class="w" id="mw9g"> </span><span class="n" id="mw9w">v</span><span class="w" id="mw-A"> </span><span class="o" id="mw-Q">|=</span><span class="w" id="mw-g"> </span><span class="n" id="mw-w">v</span><span class="w" id="mw_A"> </span><span class="o" id="mw_Q">>></span><span class="w" id="mw_g"> </span><span class="mi" id="mw_w">16</span><span class="p" id="mwAQA">;</span> <span class="w" id="mwAQE"> </span><span class="n" id="mwAQI">v</span><span class="w" id="mwAQM"> </span><span class="o" id="mwAQQ">|=</span><span class="w" id="mwAQU"> </span><span class="n" id="mwAQY">v</span><span class="w" id="mwAQc"> </span><span class="o" id="mwAQg">>></span><span class="w" id="mwAQk"> </span><span class="mi" id="mwAQo">32</span><span class="p" id="mwAQs">;</span> <span class="w" id="mwAQw"> </span><span class="n" id="mwAQ0">v</span><span class="o" id="mwAQ4">++</span><span class="p" id="mwAQ8">;</span> <span class="w" id="mwARA"> </span><span class="k" id="mwARE">return</span><span class="w" id="mwARI"> </span><span class="n" id="mwARM">v</span><span class="p" id="mwARQ">;</span> <span class="p" id="mwARU">}</span>

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 ${\displaystyle p}$ congruent to 3 modulo 4 (e.g. 3, 7, 11, 19, 23, 31, etc.), then the first ${\displaystyle p}$ offsets will be unique (modulo ${\displaystyle p}$). In other words, a permutation of 0 through ${\displaystyle p-1}$ is obtained, and, consequently, a free bucket will always be found as long as at least one exists.