REVIEW 2 major objections 7 minor 33 references
Tight Analyses of Ordered and Unordered Linear Probing
T0 review · 2 major / 7 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Linear probing's amortized high-load insertion cost is $\Theta(x \log^{1.5} x)$, with matching upper and lower bounds.
desk verdict The path-surplus result is the real deal; the linear-probing theorems close the FOCS'21 gap but lean on black-box lemmas from [4]. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the path-surplus problem: place $\mathrm{Pois}(m^2)$ blue and $\mathrm{Pois}(m^2)$ red dots uniformly in $[0,m]^2$, and define the surplus of a monotone path as the number of blue dots minus red dots beneath it. The lower bound builds a path by recursively splitting a segment and shifting its midpoint by $\pm w_L/\sqrt{\log m}$ according to the surplus of a thin rectangle $R_L$; the rectangles at distinct tree nodes are disjoint, so the induced random walk has independent steps and reaches depth $\Theta(\log m)$ with constant probability. The upper bound discretizes paths by the diagonal lines they cross at scales $d_\ell = m/2^\ell$, then bounds the surplus gain at each level minus two potential functions, the transition potential $\Phi$ and the frame potential $\Psi$, whose sums over all levels are $O(m \log^{0.75} m)$. This geometric bound is transferred to insertion surplus through Poissonization, smoothing, and rescaling, and then to linear probing through crossing-number identities of the form $c_s = \max_{i<s}(\mathrm{surplus}(i,s-1) - \mathrm{free}(i,s-1))$.
What would settle it
Run the path-surplus experiment for $m = 2^8, 2^{10}, \dots, 2^{18}$ and compare the observed maximum surplus against $c m \log^{0.75} m$; if the growth rate is not within a constant factor of that curve, the central geometric claim is wrong. A second check is to implement ordered linear probing with tombstones at load factor $1 - 1/x$ with rebuild window $n/\log^{1.5} x$ and measure the amortized expected insertion time, which should grow as $\Theta(x \log^{1.5} x)$.
Extended reading notes
Core claim
The central discovery is that the expected maximum surplus of a monotone path through an $m \times m$ grid with independent Poisson blue and red dots of density one is $\Theta(m \log^{0.75} m)$, and that this quantity exactly controls the amortized cost of linear probing. For an ordered linear-probing table on $n$ slots with tombstones, rebuild window $R = n/\beta$, and load factor never exceeding $1 - 1/x$, the paper proves that the worst-case amortized expected insertion/deletion time is $\Theta(x \log^{1.5} x + \beta x)$ and the worst-case expected query time is $\Theta(x + x \log^{1.5} x / \beta)$. The two curves cross at $R = \Theta(n/\log^{1.5} x)$, the unique optimal rebuild window, where insertions cost $\Theta(x \log^{1.5} x)$ and queries cost $\Theta(x)$. The same amortized bounds are obtained for classical unordered linear probing under an average-case workload, with the paper noting that the workload restrictions are necessary to avoid forced $\Theta(x^2)$ operations.
Load-bearing premise
The linear-probing results assume that the cited lemmas translating geometric surplus into crossing numbers, and crossing numbers into real operation costs, are correct; if any one of those translation steps has a hidden flaw, the $\Theta(x \log^{1.5} x)$ time bound fails even though the geometric path-surplus theorem stands.
Editorial extensions
If this is right
- At the optimal rebuild window $R = \Theta(n/\log^{1.5} x)$, ordered linear probing achieves worst-case amortized expected insertion/deletion time $\Theta(x \log^{1.5} x)$ and worst-case expected query time $\Theta(x)$ whenever the load factor stays at or below $1 - 1/x$.
- Choosing the rebuild window too short adds a $\beta x$ penalty to insertions; choosing it too long adds an $x \log^{1.5} x / \beta$ penalty to queries, and the two penalties balance exactly at the optimal window.
- The tight path-surplus bound $\Theta(m \log^{0.75} m)$ closes the gap between the prior $m \log \log m$ lower bound and $m \log^{O(1)} m$ upper bound for that problem.
- Classical unordered linear probing, the version most widely implemented, inherits the same amortized bounds under the stated average-case workload, showing that anti-clustering is a general linear-probing phenomenon.
- The workload restrictions for the unordered result are essential: if insertions repeat the same element or queries are adversarial, one can force $\Theta(x^2)$-time operations again.
Reading between the lines
- Beyond the paper, the recursive midpoint-shift construction is effectively a martingale random walk with step $1/\sqrt{\log m}$, so the same technique may give tight logarithmic corrections for other signed path processes, such as last-passage percolation with positive and negative weights.
- The exact location of the optimal rebuild window suggests a concrete engineering heuristic: tombstones should be left in place for roughly $n/\log^{1.5} x$ operations rather than a much shorter window, because tombstone-driven anti-clustering is what keeps insertion costs low.
- The paper proves expectation bounds; a natural next step would be to test concentration of the maximum path surplus by simulation, which the paper's methods do not by themselves settle.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper resolves the path surplus problem, proving that the expected maximum surplus of a monotonic path through an m-by-m grid with independent blue and red Poisson dots is Θ(m log^{0.75} m), and then transfers this result to linear probing. The authors derive matching upper and lower bounds of Θ(x log^{1.5} x) for the amortized expected insertion/deletion time in ordered linear probing with tombstones and rebuild windows, and they obtain analogous bounds for classical unordered linear probing under an average-case workload. The main technical work is a new lower-bound construction based on a recursive random walk and an upper bound using frame decompositions, potential functions, and an entropy-compression argument.
Significance. If the technical gaps discussed below are repaired, this is a significant advance: the path surplus problem is settled with a clean Θ(m log^{0.75} m) bound, and the paper gives the first tight asymptotic characterization of the amortized insertion time for linear probing with tombstones. The path-surplus upper bound is a substantial and largely self-contained contribution, and the idea of isolating three 'core facts' to transfer the analysis from the Poisson path-surplus setting to insertion surpluses is elegant. The linear-probing results are conditional on several lemmas from Bender et al. [4]; this is a legitimate dependency rather than a circularity, but the authors should verify that all hypotheses of those lemmas are met in the exact parameter regime used here.
major comments (2)
- [Section 4.1, Lemmas 4.4 and 3.10, Eq. (12)] The proof of Proposition 4.7 has an independence gap. In the modified insertion-surplus process, Core Fact 1 (Lemma 4.4) establishes independence only for vertical strips. Lemma 3.10, which is used verbatim in the transfer, decomposes the maximum transitional gain into a sum over j of random variables X_j that are argued to be independent because each depends on the dots in a strip between consecutive level-ℓ diagonals. These strips are not vertical, and in the insertion-surplus process a single Poissonized x-column can contribute dots to more than one such diagonal strip (for example, a key that is inserted at time i and deleted at time i' yields two dots in the same column at different times). The independence assertion in Lemma 3.10 therefore does not follow from Lemma 4.4. The authors need either to prove the needed independence for diagonal strips directly in the modified process, or to rework the frame decomposition so that it only relies on vertical-strip independence.
- [Section 6.1, Lemma 6.5, Eq. (36)] The tail bound on the sum ∑_ℓ A_{ℓ,s}K_ℓ is not justified as written. The proof states that this sum is bounded above by a binomial random variable with mean s/4, but A_{ℓ,s} is the event F_ℓ ≤ s + βs/8, and F_ℓ depends on the same sequence of failed deletions K_ℓ. The summands are therefore not independent and are not stochastically dominated by the claimed binomial merely because each conditional mean is at most (s+βs/8)/n. This step is load-bearing for Proposition 6.3 and hence for Theorem 1.4. A martingale or coupling argument is needed to justify the claimed 2^{-Ω(s)} decay.
minor comments (7)
- [Lemma 5.6] The display for t and the subsequent asymptotic bounds are garbled. With the intended t = (x^2/(qβ)) log^{1.5} x, the lower bound should read Ω((x/(β√q)) log^{1.5} x − (x/(qβ)) log^{1.5} x), which yields the claimed Ω(x log^{1.5} x / β) after summing over s. Please correct the typesetting and the intermediate inequalities.
- [Corollary 4.12] In the definition of surplus(O, [j−t,t]), the interval should be [j−t, j], consistent with the surrounding notation.
- [Lemma 3.13] The sentence 'This proves (21), which then implies (18) and (19)' should refer to (18) and (20), since (19) is proved separately by direct calculation.
- [Lemma 3.14] The bound |C_q| ≤ 2^{O(q)+ℓ} does not match the previously stated unary encoding length O(‖Δ(F)‖_1 + 2^ℓ). The correct bound is |C_q| ≤ 2^{O(q + 2^ℓ)}; the subsequent argument still works when α is sufficiently large, but the display should be fixed.
- [Lemma 4.1] The claim that the partial smoothing step 'does not change surplus(P)' is not immediate for arbitrary monotone paths and for dots lying on the path boundary. Please add a formal argument or state the convention used for points on the path.
- [Lemma 3.8] The notation P_0 is used in the telescoping sum near the end of the proof but is not defined; it should denote the set of rigid paths at level 0.
- [Corollary 5.4] There is a typo in 'wort-case'; it should be 'worst-case'.
Circularity Check
No significant circularity: the path-surplus analysis is self-contained, and the linear-probing conversion lemmas from prior work are independent dependencies, not inputs recycled as outputs.
full rationale
The paper's central derivation is self-contained: the tight path-surplus bounds (Theorem 3.1 lower bound and Theorem 3.2 upper bound) are proved directly from Poisson/Chernoff bounds, the explicit random-walk structure of the lower-bound construction, and the potential-function framework of Section 3.2. No parameter is fitted to data, and no theorem is made true by definition. The Insertion Surplus reduction in Sections 4.1 and 4.2 is also explicit: Poissonization, smoothing, and rescaling are justified with quantitative O(t^2/n) or O(1/m^2) error terms, and the lower bound reduces formally to the original path-surplus problem, not to the desired linear-probing conclusion. The final linear-probing theorems (Theorems 1.3 and 1.4) do delegate several conversion steps to Bender et al. [4], including Lemmas 5.1, 5.2, 5.5, 5.8 and Lemma 6.2, and these citations include the current coauthor. However, these are legitimate external dependencies: [4] predates the exact Θ(log^1.5 x) bound, and its lemmas convert crossing numbers to operation costs without assuming the target result. The paper supplies the new quantitative path-surplus and insertion-surplus bounds and feeds them into that cited machinery. A hidden flaw in one of the cited lemmas would be a correctness risk, not circular reasoning, because the present derivation does not reduce to its own output by construction. There is also no renaming of a known result: the Θ(m log^{0.75} m) path-surplus bound and the Θ(x log^{1.5} x) amortized insertion bound are new statements derived through the chain described in the paper. Overall, I find no circular step warranting a nonzero score.
Assumptions & free parameters
assumptions (3)
- domain assumption The hash function h is fully random (uniform and independent for each key).
- domain assumption Bender et al. [4] lemmas converting crossing numbers to operation costs (Lemmas 5.1, 5.2, 5.5, 5.8, and Proposition 3) are correct.
- standard math Standard probabilistic inequalities (Chernoff, Kolmogorov, Azuma, negative association) and Poissonization are valid in the regimes used.
Cite this review
Pith. "Pith review of Tight Analyses of Ordered and Unordered Linear Probing." pith.science (2026). https://pith.science/paper/SMXV5URZ
@misc{pith2026250111582,
author = {Pith},
title = {Pith review of: Tight Analyses of Ordered and Unordered Linear Probing},
year = {2026},
howpublished = {\url{https://pith.science/paper/SMXV5URZ}},
note = {Machine review of arXiv:2501.11582}
}
abstract
Linear-probing hash tables have been classically believed to support insertions in time $\Theta(x^2)$, where $1 - 1/x$ 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 \emph{maximum} load factor is at most $1 - 1/x$, then the \emph{amortized} expected time per insertion will never exceed $x \log^{O(1)} x$ (even in workloads that operate continuously at a load factor of $1 - 1/x$). 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 $\Theta(x \log^{1.5} x)$. 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.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[4]
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering
Michael A Bender, Bradley C Kuszmaul, and William Kuszma ul. Linear probing revisited: Tombstones mark the death of primary clustering. arXiv preprint arXiv:2107.01250, 2021
work page Pith review arXiv 2021
- [1]
-
[2]
Ole Amble and Donald Ervin Knuth. Ordered hash tables. The Computer Journal , 17(2):135–142, January 1974. doi:10.1093/comjnl/17.2.135
-
[3]
Bender, Martin Farach-Colton, Rob Johnson, R ussell Kaner, Bradley C
Michael A. Bender, Martin Farach-Colton, Rob Johnson, R ussell Kaner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Monte s, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. Don’t thrash: How to cache your has h on flash. Proceedings of the VLDB Endowment , 5(11):1627–1637, 2012. doi:10.14778/2350229.2350275
arXiv 2012
-
[5]
Linear probing revisited: Tombstones mark the demise of primary clusterin g
Michael A Bender, Bradley C Kuszmaul, and William Kuszma ul. Linear probing revisited: Tombstones mark the demise of primary clusterin g. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1171–1182. IEEE, 2022
work page 2021
-
[6]
Ioana O Bercea, Lorenzo Beretta, Jonas Klausen, Jakob Bæ k Tejs Houen, and Mikkel Thorup. Locally uniform hashing. arXiv preprint arXiv:2308.14134, 2023
work page Pith review arXiv 2023
-
[7]
Open-sourcing F14 for faster, more memory-efficient has h tables, 25 April 2019
Nathan Bronson and Xiao Shi. Open-sourcing F14 for faster, more memory-efficient has h tables, 25 April 2019. Accessed: 2020-11-06. URL: https://engineering.fb.com/2019/04/25/developer-too ls/f14/
work page 2019
-
[8]
Pedro Celis, Per- ˚ Ake Larson, and J. Ian Munro. Robin Hood hashing (preliminar y report). In 26th Annual Symposium on Foundations of Computer Science (FO CS’85), pages 281–288, Portland, Oregon, USA, 21–23 October 1985. doi:10.1109/SFCS.1985.48
Show all 33 references
-
[9]
Almost rand om graphs with simple hash functions
Martin Dietzfelbinger and Philipp Woelfel. Almost rand om graphs with simple hash functions. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC’03), pages 629–638, San Diego, California, USA, 9–11 June 2003. doi:10.1145/780542.780634
2003
-
[10]
Adam Drozdek and Donald L. Simon. Data Structures in C . PWS, Boston, Massachusetts, USA, 1995
1995
-
[11]
Quotient filters: Approximate membership queries on the GPU
Afton Geil, Martin Farach-Colton, and John D Owens. Quotient filters: Approximate membership queries on the GPU. In Proceedings of the IEEE International Parallel and Distributed Processing Symp osium (IPDPS) , pages 451–462, Vancouver, British Columbia, Canada, 21–25 May 2018....
2018
-
[12]
Notes on “open” addressing, 1963
Don Knuth. Notes on “open” addressing, 1963
1963
-
[13]
The Art of Computer Programming, Volume III: Sorting and Searchin g
Donald Ervin Knuth. The Art of Computer Programming, Volume III: Sorting and Searchin g. Addison-Wesley, 2nd edition, 1998. URL: https://www.worldcat.org/oclc/312994415
1998
-
[14]
Konheim and Benjamin Weiss
Alan G. Konheim and Benjamin Weiss. An occupancy discip line and applications. SIAM Journal on Applied Mathematics , 14(6):1266–1274, November 1966. doi:10.1137/0114101
1966 doi
-
[15]
Robert L. Kruse. Data Structures and Program Design. Prentice-Hall Inc, Englewood Cliffs, New Jersey, USA, 1984. 53
1984
-
[16]
The multiplicative version of azuma’s inequality, with an application to contention analysis
William Kuszmaul and Qi Qi. The multiplicative version of azuma’s inequality, with an application to contention analysis. arXiv preprint arXiv:2102.05077, 2021
2021 arXiv
-
[17]
Lewis and Larry Denenberg
Harry R. Lewis and Larry Denenberg. Data Structures and Their Algorithms . HarperCollins Publishers, New York, New York, USA, 1991
1991
-
[18]
Data Structures and Other Objects Using C++
Michael Main and Walter Savitch. Data Structures and Other Objects Using C++ . Addison-Wesley, Boston, Massachusetts, USA, 2001
2001
-
[19]
Probability and computing: Randomization and probabilistic techniques in algorithms and data analys is
Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analys is. Cambridge university press, 2017
2017
-
[20]
Uniform hashing in constant t ime and optimal space
Anna Pagh and Rasmus Pagh. Uniform hashing in constant t ime and optimal space. SIAM Journal on Computing , 38(1):85–96, 2008. doi:10.1137/060658400
2008 doi
-
[21]
Linear probing with constant independence
Anna Pagh, Rasmus Pagh, and Milan Ruzic. Linear probing with constant independence. In Proceedings 39th Annual ACM Symposium on Theory of Computing (S TOC’07), pages 318–327, San Diego, California, USA, 11–13 June 2007. doi:10.1145/1250790.1250839
2007
-
[22]
Bender, Martin Farach-Colton, and Rob Johnson
Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martin Farach-Colton, and Rob Johnson. Vector quotient filters: Overcoming the time/space trade-off in filter design . In Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data (SIGMO D’21), 20–25 2021
2021
-
[23]
W. W. Peterson. Addressing for random-access storage. IBM Journal of Research and Development , 1(2):130–146, April 1957. doi:10.1147/rd.12.0130
1957 doi
-
[24]
A se ven-dimensional analysis of hashing methods and its implications on query processing
Stefan Richter, Victor Alvarez, and Jens Dittrich. A se ven-dimensional analysis of hashing methods and its implications on query processing. PVLDB – Porceedings of the VLDB Endowment, 9(3):96–107, November 2015. The 42nd International Confe rence on Very Large Data Bases, New...
2015
-
[25]
Algorithms
Robert Sedgewick. Algorithms. Addison-Wesley, Reading, Massachusetts, USA, 1983
1983
-
[26]
Algorithms in C
Robert Sedgewick. Algorithms in C . Addison-Wesley, Reading, Massachusetts, USA, 1990
1990
-
[27]
On universal classes of extremely random constant-time hash functions
Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM Journal on Computing , 33(3):505–543, 2004
2004
-
[28]
Standish
Thomas A. Standish. Data Structures, Algorithms, and Software Principles in C . Addision-Wesley, Reading, Massachusetts, USA, 1995
1995
-
[29]
Sorenson
Jean-Paul Tremblay and Paul G. Sorenson. An Introduction to Data Structures with Applications . McGraw-Hill, 1984
1984
-
[30]
Negative association: definition, properties, and applications
David Wajc. Negative association: definition, properties, and applications. Manuscript, available from https://goo. gl/j2ekqM , 2017
2017
-
[31]
Data Structures and Problem Solving using C++
Mark Allen Weiss. Data Structures and Problem Solving using C++ . Addison-Wesley, Reading, Massachusetts, USA, 2000
2000
-
[32]
Linear probing,
Wikipedia contributors. Linear probing,
-
[2021]
URL: https://en.wikipedia.org/wiki/Lienar_probing
Accessed 31-May-2021. URL: https://en.wikipedia.org/wiki/Lienar_probing. 54
2021
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.