Quadratic Probing Insertions Are $ε^{-(1+o(1))}$
2026-08-28 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study quadratic probing, a popular method for handling collisions in hash tables used since 1968. They focus on how long it takes to insert items when the table is nearly full, measured by a small parameter ε. Before this work, nobody had proven a clear formula for the expected insertion time as the table gets full. The authors prove that this time grows roughly like ε to the power of -1, resolving a long-standing open question about the method's efficiency.
quadratic probinghash tablescollision resolutionexpected insertion timeload factorasymptotic analysisprobabilistic boundcomputer science data structures
Authors
Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou
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 - ε$, the hash table achieves $O(ε^{-1})$ expected insertion time. But even proving a bound of the form $f(ε^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $ε^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $ε^{-1}$.