Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood
Provides theoretical performance guarantees for quadratic probing and related schemes, resolving long-standing open questions for practitioners using open-addressing hash tables.
The paper analyzes quadratic probing hash tables using smoothed analysis, showing that anti-Robin Hood ordering achieves expected query time Θ(log ε⁻¹) at load factor 1-ε, matching conjectured optimal performance, while Robin Hood ordering yields Θ(ε⁻¹/²). For degree-d probing, anti-Robin Hood achieves O(max(log ε⁻¹, ε^{1-2/d})) and Robin Hood Θ(ε⁻¹/ᵈ). It also proves that almost all fixed-offset degree-d probing sequences achieve O(log ε⁻¹) expected query time under anti-Robin Hood.
Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees remain poorly understood. In this paper, we revisit quadratic probing through the lens of a smoothed variant in which each key follows a random probe sequence where its $k$th probe is expected at offset $Θ(k^2)$. This is simultaneously a toy model for better understanding regular quadratic probing and a natural hashing scheme in its own right. We analyse smoothed quadratic probing for both Robin Hood ordering and anti-Robin Hood ordering and reveal a surprising separation: At load factor $1-\varepsilon$, anti-Robin Hood achieves an expected query time of $Θ(\log \varepsilon^{-1})$, which matches the conjectured expected average successful query time for regular quadratic probing, while Robin Hood falls short at $Θ(\varepsilon^{-1/2})$. Our analysis generalises to degree-$d$ probing for any $d \ge 1$ with expected query time $O(\max(\log \varepsilon^{-1}, \varepsilon^{1-2/d}))$ for anti-Robin Hood and $Θ(\varepsilon^{-1/d})$ for Robin Hood. Finally, we go beyond smoothed analysis: using the probabilistic method, we show that for every $d \ge 2$, almost every random fixed-offset degree-$d$ probing sequence achieves expected query time $O(\log \varepsilon^{-1})$ under anti-Robin Hood ordering, simultaneously over all admissible table sizes and load factors. Thus, while quadratic probing itself remains elusive, we prove that essentially all quadratic-probing-like fixed-offset schemes achieve the ideal performance under the anti-Robin Hood ordering.