Linear Probing with Non-Greedy Insertions

Andrew Krapivin, William Kuszmaul, Jolyne Wang

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 h…