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

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}$.

17 pages