Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood

Abstract

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 $\Theta (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-\epsilon$, anti-Robin Hood achieves an expected query time of $\Theta (\log {\epsilon }^{-1})$, which matches the conjectured expected average successful query time for regular quadratic probing, while Robin Hood falls short at $\Theta ({\epsilon }^{-1/2})$. Our analysis generalises to degree-$d$ probing for any $d\ge 1$ with expected query time $O(\max (\log {\epsilon }^{-1},{\epsilon }^{1-2/d}))$ for anti-Robin Hood and $\Theta ({\epsilon }^{-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 {\epsilon }^{-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.