Tight Analyses of Ordered and Unordered Linear Probing

Linear-probing hash tables have been classically believed to support insertions in time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(x^{2})$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1-1/x$</tex> is the load factor of the hash table. Recent work by Bender, Kuszmaul, and Kuszmaul (FOCS'21), however, has added a new twist to this story: in some versions of linear probing, if the maximum load factor is at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1-1/x$</tex>, then the amortized expected time per insertion will never exceed <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x\ \text{polylog}\ x$</tex> (even in workloads that operate continuously at a load factor of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1-1/x$</tex>). Determining the exact asymptotic value for the amortized insertion time remains open. In this paper, we settle the amortized complexity with matching upper and lower bounds of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(x\log^{1.5}x)$</tex>. Along the way, we also obtain tight bounds for the so-called path surplus problem, a problem in combinatorial geometry that has been shown to be closely related to linear probing. We also show how to extend Bender et al.'s bounds to say something not just about ordered linear probing (the version they study) but also about classical linear probing, in the form that is most widely implemented in practice.