Linear Probing with Non-Greedy Insertions

Abstract

Linear probing hash tables classically use a \emph{greedy} insertion strategy, placing a key $u$ in the first available position out of $h(u),h(u)+1,h(u)+2,\dots$. If the hash table is filled to $1-1/x$ full, this results in $\Theta (x^2)$ worst-case expected insertion time. In this paper, we introduce interlinear probing, a simple \emph{non-greedy} insertion strategy that does better without requiring elements to be reordered within the table over time. Given $x$ in advance, the algorithm brings the worst-case expected insertion time (and therefore also the worst-case expected positive query time) down to $O(x\log x)$. We also extend the algorithm to support \emph{negative} queries in worst-case expected time $O(x(\log x{)}^2)$. Moreover, our construction achieves $O(x)$ amortized insertion time, matching that of standard linear probing. Finally, we prove a lower bound showing that any stable insertion strategy for linear probing must incur $\Omega (x\sqrt{\log x})$ worst-case expected time. Combined, our results establish that the optimal worst-case expected insertion time among stable insertion strategies is $x(\log x{)}^{\Theta (1)}$.