Tight Analyses of Ordered and Unordered Linear Probing

Mark Braverman, William Kuszmaul

Linear-probing hash tables have been classically believed to support insertions in time $\hat{I}˜(x^2)$, where $1-1/x$ is the load factor of the hash table. Recent work by Bender, Kusz…