Quadratic Probing Insertions Are $\epsilon^{-(1+o(1))}$

Abstract

First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the form $f(\epsilon^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $\epsilon^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $\epsilon^{-1}$.