Linear Probing with Non-Greedy Insertions
2026-07-20 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a way to put keys into a linear probing hash table, which usually uses a greedy method that places each key at the first free spot it finds. When the table is almost full, this method can take a really long time to insert new keys. The authors propose a different, non-greedy approach that does not require rearranging keys later but still improves the worst-case insertion time significantly. Their method reduces the expected insertion time from roughly the square of a parameter x to about x times the logarithm of x.
linear probinghash tablesgreedy algorithminsertion strategyworst-case analysisexpected timehash functionnon-greedy algorithmalgorithmic complexity
Authors
Andrew Krapivin, William Kuszmaul, Jolyne Wang
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, \ldots$. If the hash table is filled to $1 - 1/x$ full, this results in $Θ(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)$.