Linear Probing with Non-Greedy Insertions

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\mathrm{/}x$ full, this results in $\mathrm{\Theta }(x^2)$ worst-case expected insertion time. In this note, we show that there is a simple \emph{non-greedy} insertion strategy that does better, and without requiring elements to be reordered within the table over time. Given $x$ in advance, the strategy is able to bring the worst-case expected insertion time down to $O(x\log x)$.