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:

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

Quadratic probing is often recommended as an alternative to linear probing because it incurs less clustering. ^[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]

History

Quadratic probing was first introduced by Ward Douglas Maurer in 1968. ^[3] Several subsequent variations of the data structure were proposed in the 1970s in order to guarantee that the probe sequence hits every slot without cycling prematurely. ^{[4] [5]} Quadratic probing is widely believed to avoid the clustering effects that make linear probing slow at high load factors. It serves as the basis for many widely-used high-performance hash-tables ^{[6] [7] [8]} , including Google's open-source Abseil ^[9] hash table. ^[10]

It is conjectured ^{[3] [11]} that quadratic probing, when filled to ${\displaystyle 1-\epsilon }$ full, supports insertions in expected time ${\displaystyle O(\epsilon ^{-1})}$. Proving this, or even proving any non-trivial time bound for quadratic probing remains open. ^[11] The closest result, due to Kuszmaul and Xi, shows that, at load factors of less than ${\displaystyle \approx 0.089}$, insertions take ${\displaystyle O(1)}$ expected time. ^[11]

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}{\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 (in fact, it is a permutation on [0, m−1] ^[12] ). 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+ni^{2}){\pmod {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){\pmod {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){\pmod {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:

uint64_troundUp2(uint64_tv){v--;v|=v>>1;v|=v>>2;v|=v>>4;v|=v>>8;v|=v>>16;v|=v>>32;v++;returnv;}

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}$).^{[ further explanation needed ]} 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.

References

1. Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). Cambridge, Massachusetts London, England: MIT Press. ISBN   978-0-262-53305-8.
2. Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015). "A seven-dimensional analysis of hashing methods and its implications on query processing" . Proceedings of the VLDB Endowment. 9 (3): 96–107. doi:10.14778/2850583.2850585. ISSN   2150-8097.
3. Maurer, W. D. (1968). "Programming Technique: An improved hash code for scatter storage". Communications of the ACM. 11 (1): 35–38. doi: 10.1145/362851.362880 . ISSN   0001-0782.
4. Batagelj, Vladimir (1975-04-01). "The quadratic hash method when the table size is not a prime number". Commun. ACM. 18 (4): 216–217. doi:10.1145/360715.360737. ISSN   0001-0782.
5. Hopgood, F. R. A. (1972-04-01). "The quadratic hash method when the table size is a power of 2". The Computer Journal. 15 (4): 314–315. doi:10.1093/comjnl/15.4.314. ISSN   0010-4620.
6. Chaos, Attractive (2025-08-23), attractivechaos/klib , retrieved 2025-08-24
7. PpHd (2025-08-24), P-p-H-d/mlib , retrieved 2025-08-24
8. "An Extensive Benchmark of C and C++ Hash Tables". An Extensive Benchmark of C and C++ Hash Tables. Retrieved 2025-08-24.
9. "abseil / abseil.io". abseil.io. Retrieved 2025-08-24.
10. "absl/container/internal/raw_hash_set.h - external/github.com/abseil/abseil-cpp - Git at Google". chromium.googlesource.com. Retrieved 2025-08-24.
11. Kuszmaul, William; Xi, Zoe (2024). Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (eds.). "Towards an Analysis of Quadratic Probing". 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs). 297. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 103:1–103:19. doi: 10.4230/LIPIcs.ICALP.2024.103 . ISBN   978-3-95977-322-5.
12. The Art of Computer Science Volume 3 Sorting and Searching, Chapter 6.4, exercise 20, Donald Knuth

External links

• Tutorial/quadratic probing