2026/07/20 by Andrew Krapivin, William Kuszmaul, Jolyne Wang
#cs.DS
Linear probing hash tables classically use a greedy insertion strategy, placing a key u in the first available position out of h(u), h(u) + 1, h(u) + 2, …. If the hash table is filled to 1 - 1/x full, this results in Θ(x2) worst-case expected insertion time. In this note, we show that there is a simple 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).