Pith. sign in

REVIEW 1 major objections 3 minor 20 references

Linear Probing with Non-Greedy Insertions

T0 review · 1 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that a simple non-greedy insertion rule — skip free slots to reserve them for later keys — reduces the worst-case expected insertion time of stable linear probing from Θ(x²) to O(x log x).

desk verdict A genuinely new O(x log x) stable linear-probing insertion strategy whose core proof is sound for power-of-two n; the arbitrary-n extension and the positive-query claim are asserted, not shown. read the letter →

arxiv 2607.17494 v1 pith:4ZHB7QFF submitted 2026-07-20 cs.DS

Andrew Krapivin , William Kuszmaul , Jolyne Wang This is my paper · ORCID
classification cs.DS MSC 68P0568W2068W40
keywords linearprobingnon-greedyinsertionstablehashtableopenaddressingworst-caseexpectedtimeclusteringlayeredrandomhashing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Classical linear probing inserts each key into the first free slot after its hash; at load factor 1−1/x this greedy rule makes worst-case expected insertion time Θ(x²). This paper proves that a simple non-greedy rule — sometimes skip a free slot and keep probing, reserving that slot for later keys — cuts the worst-case expected insertion time to O(x log x), with no element ever moved after placement. The construction fixes the target load x in advance, partitions the circular table into geometrically spaced layers, and routes each insertion probabilistically between the current layer and an overflow layer. If correct, this is the first stable, unidirectional linear-probing scheme to beat quadratic worst-case insertions, and it brings positive queries to the same bound as a byproduct.

What carries the argument

The load-bearing object is the layer partition L_i of one slot every 2^i positions, together with the probabilistic routing rule p_i(δ_i) = min(1, λ x log(2x) δ_i² / 2^i). The layer spacing s_i = 2^i converts the expected number of probes in a layer, Θ(δ_i^{−2}), into a physical cost Θ(s_i/δ_i²); the routing probability is chosen so that cost times probability is Θ(x log x). The companion guarantee is Claim 1: with high probability the overflow layer L_{i+1} receives fewer than half its slots during phase i, which keeps overflow insertions cheap. The definition b(x) = C_0 x log(2x) sets the phase-ending threshold δ_i^* = s_i / b(x), and the correctness argument sums min(n/2^i, n/b(x)) over l

What would settle it

Choose an n that is not a power of two, set x near the largest value satisfying x = o(n/log² n), and simulate the algorithm with a fully random hash, recording the maximum expected insertion time over the first (1−1/x)n insertions. If that maximum grows like x² rather than x log x, the theorem as stated is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: assuming a fully random hash function and x = o(n/log² n), each of the first (1−1/x)n insertions into an n-slot circular table completes in worst-case expected O(x log x) time under the Interleaved Layered Insert algorithm. The algorithm divides the table into layers L_i, where L_i contains every 2^i-th slot, and during phase i routes a new key to active layer L_i with probability min(1, λ x log(2x) δ_i² / 2^i), where δ_i is the current empty fraction of L_i; otherwise it routes to the overflow layer L_{i+1}. By keeping L_{i+1} less than half full with high probability, the expected cost of an overflow insertion is O(2^i) = O(x log x), while the expected cost

Load-bearing premise

The clean geometry of the proof requires n to be a power of two; the paper states without proof that rounding extends the result to arbitrary n, so for general n the O(x log x) insertion bound is not actually established.

Editorial extensions

If this is right

  • If Theorem 1 is right, insertion-only stable linear probing reaches O(x log x) worst-case expected insertion time at load 1−1/x, the first sub-Θ(x²) bound of its kind.
  • Because elements never move and probing is in one direction, the same O(x log x) bound applies to queries for keys already inserted.
  • The result separates the cost of clustering from the cost of stability: avoiding reordering no longer forces quadratic worst-case insertions.
  • The near-full-table regime changes from infeasible to nearly linear: a table planned for target load can stop at 1−1/x with per-insertion cost O(x log x).
  • The analysis leaves open whether the extra log factor can be removed; the O(x) target remains unresolved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the n-power-of-two restriction is not merely cosmetic, the theorem as stated overreaches: the Section 2 assertion that 'careful rounding' handles arbitrary n is not accompanied by a proof, and the layer geometry (one slot every 2^i positions) is what makes the uniformity argument work.
  • A concrete next experiment is to run the algorithm with n not a power of two and measure whether the worst-case expected insertion time tracks O(x log x) or reverts to Θ(x²); this would test the missing rounding rather than the core idea.
  • The parameter x is an input; extending the scheme to adaptively learn x from the arrival stream, or to handle a range of loads, is the obvious practical next step.
  • The skip-to-reserve mechanism suggests a broader design principle: sparse reserved slots can absorb overflow without moving keys, which may transfer to other open-addressing variants such as bidirectional probing or cuckoo-style tables with stability constraints.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper proposes a non-greedy insertion strategy for linear probing. The table is partitioned into dyadic layers; in each phase i, a new key is sent to the active layer L_i with probability pi = min(1, λ bx δ_i^2/s_i) and otherwise to the overflow layer L_{i+1}. The analysis shows that with high probability the overflow layer stays at most half full, and the expected insertion cost is O(bx) = O(x log x), provided x = o(n/log^2 n). Theorem 1 states this worst-case expected-time bound for each of the first (1−1/x)n insertions. The proof uses a Chernoff bound for the overflow count and a direct expected-cost calculation.

Significance. If the result holds for all n, it is the first stable (no-reordering), unidirectional linear-probing insertion scheme with sub-Θ(x^2) worst-case expected insertion time, improving to O(x log x). The algorithm is simple and the proof is direct, with explicit inequalities and no hidden fitting of constants; the main technical work is a clean geometric argument controlling overflow between layers. The principal caveat is that the proof as written covers only n a power of two, despite the theorem's general statement, so the significance for arbitrary n is conditional.

major comments (1)
  1. [Section 2 and Theorem 1] Theorem 1 is stated for arbitrary n, but the proof uses exact power-of-two structure: N_i = n/2^i, s_i N_i = n, and the uniformity of the first L_i slot reached by h(u). These are used in the correctness sum and in Claim 1 (p_min = λs/bx, θN = Ω(n/bx)). The only justification for general n is the sentence 'with careful rounding, all of the same arguments also apply for arbitrary n' (Section 2); no rounding is specified and no lemma verifies that the total-free-slot bound and the overflow bound survive. Since Theorem 1 covers all n, this is a load-bearing gap. Either prove the rounding or restrict the theorem to powers of two.
minor comments (3)
  1. [Section 1] The claim that the structure supports 'positive queries' needs a query-algorithm specification. Because non-greedy insertions can leave free slots before an inserted key, the standard linear-probing query (stop at first empty slot) may fail to find a present key. The authors should clarify that positive queries require scanning past empty slots and that negative queries are not supported under the usual semantics.
  2. [Claim 1] The proof writes sums over all r ≥ δ*_i N as if 1/p_r equals sN^2/(λbxr^2) for every r, but for r with p_r = 1 that equality fails. The argument is valid if the sums are understood to range only over r with p_r < 1; please state this explicitly.
  3. [Section 2] The constants C0 and λ are introduced as 'sufficiently large' without explicit values. Since the theorem is asymptotic and uses these constants in thresholds (e.g., the split in the correctness sum and the choice of λ in Claim 1), it would improve reproducibility to state how large they need to be, or at least to make the existence claim precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the O(x log x) bound is a direct consequence of the algorithm's routing probabilities and phase thresholds; the only self-citations are for standard external linear-probing facts.

full rationale

The paper's central derivation is self-contained. The routing probability p_i = min(1, λ bx δ_i^2 / s_i) is an explicit design choice, and the expected-cost computation Θ(s_i/δ_i^2)·p_i = O(bx) = O(x log x) follows by algebra from that definition, not by fitting a parameter to a target result. The phase threshold δ*_i = s_i/bx is similarly defined and then used consistently in Claim 1 and the correctness sum; the sum ∑ min(n/2^i, n/bx) ≤ n/x is a genuine inequality for sufficiently large C0, not an identity imported from the conclusion. The classical Θ(x^2) lower bound and the tombstone-based O(x) facts are cited to [BKK21], which includes an author of this paper, but those facts are standard, externally established, and not load-bearing for the new construction; no uniqueness theorem or prior result is invoked to force the algorithm's form. The only notable gap is external to circularity: the paper assumes n is a power of two and asserts that 'with careful rounding, all of the same arguments also apply for arbitrary n' without supplying the rounding or verifying that the layer geometry (|L_i| = n/2^i, s_i N_i = n) survives. That is a correctness/completeness concern, not a reduction of the claimed bound to its own inputs, so it does not raise the circularity score.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The O(x log x) claim rests on two hand-chosen sufficiently-large constants (C0, λ), the fully-random-hash model, the classic Knuth clustering bound, the power-of-two table size, and the theorem condition x = o(n/log^2 n). No entities are invented beyond the algorithmic layers.

free parameters (2)
  • C0 = unspecified sufficiently large constant
    Appears in b_x = C0 x log(2x); large enough required for the correctness bound (free slots ≤ n/x) and for the sum split at 4 log_2 x.
  • λ = unspecified sufficiently large constant
    Controls routing probability p_i and is required to be large for Claim 1 (E[O_i] ≤ N/32 and the concentration exponent −Ω(θN)).
assumptions (5)
  • domain assumption Fully random hash function h: U→[n]
    Section 2. All probabilistic claims (uniform first-layer slot, Knuth clustering bound, independence in Claim 1) rely on uniform independent hashing.
  • domain assumption Knuth linear-probing clustering bound: expected probes in a table with empty fraction δ is Θ(1/δ^2)
    Section 4, 'An insertion into L_i will examine Θ(δ_i^{-2}+1) expected slots in L_i'; cited to [Knu63, BKK21].
  • ad hoc to paper n is a power of 2 (or the asserted 'careful rounding' works)
    Section 2. Enables the exact layer partition and uniform spacing; the paper does not prove the rounding.
  • domain assumption x = o(n/log^2 n) and x known in advance
    Theorem 1; the algorithm needs x to set b_x and phase thresholds, and the proof uses the bound to make failure probabilities ≤ 1/n^2.
  • standard math MGF concentration bound for geometric random variables: for 0≤θ≤p/4, E[e^{θG}] ≤ exp(2θ/p)
    Claim 1 proof. Standard Chernoff-type bound; not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear Probing with Non-Greedy Insertions." pith.science (2026). https://pith.science/paper/4ZHB7QFF

@misc{pith2026260717494,
  author       = {Pith},
  title        = {Pith review of: Linear Probing with Non-Greedy Insertions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4ZHB7QFF}},
  note         = {Machine review of arXiv:2607.17494}
}
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 $\Theta(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)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 1 linked inside Pith

  1. [1]

    https://abseil.io/

    Google's Abseil C++ library. https://abseil.io/. Accessed: 2020-11-06

    2020

  2. [2]

    Ordered hash tables

    Ole Amble and Donald Ervin Knuth. Ordered hash tables. The Computer Journal , 17(2):135--142, January 1974

    1974

  3. [3]

    Bender, Alex Conway, Martin Farach - Colton, William Kuszmaul, and Guido Tagliavini

    Michael A. Bender, Alex Conway, Martin Farach - Colton, William Kuszmaul, and Guido Tagliavini. Iceberg hashing: Optimizing many hash-table criteria at once. J. ACM , 70(6):40:1--40:51, 2023

    2023

  4. [4]

    Bender, Bradley C

    Michael A. Bender, Bradley C. Kuszmaul, and William Kuszmaul. Linear probing revisited: Tombstones mark the demise of primary clustering. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 1171--1182. IEEE , 2021

    2021

  5. [5]

    Robin hood hashing

    Pedro Celis. Robin hood hashing . University of Waterloo, 1986

    1986

  6. [6]

    Ian Munro

    Pedro Celis, Per - ke Larson, and J. Ian Munro. Robin Hood hashing (preliminary report). In 26th Annual Symposium on Foundations of Computer Science (FOCS'85) , pages 281--288, Portland, Oregon, USA, 21--23 October 1985

    1985

  7. [7]

    https://en.cppreference.com/w/cpp/container/unordered_map

    cpppreference std::unordered\_map. https://en.cppreference.com/w/cpp/container/unordered_map. Accessed: 2020-11-06

    2020

  8. [8]

    https://github.com/gcc-mirror/gcc/blob/master/libstdc\ Accessed: 2020-11-06

    gcc-mirror/gcc libstdc++-v3 unordered\_map.h. https://github.com/gcc-mirror/gcc/blob/master/libstdc\ Accessed: 2020-11-06

    2020

Show all 20 references
  1. [9]

    De dictionariis dynamicis pauco spatio utentibus (lat

    Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P a tra s cu. De dictionariis dynamicis pauco spatio utentibus (lat. on dynamic dictionaries using little space). In Latin American Symposium on Theoretical Informatics (LATIN) , pages 349--361. Springer, 2006

    2006

  2. [10]

    https://engineering.fb.com/2019/04/25/developer-tools/f14/

    Facebook's F14 hash table. https://engineering.fb.com/2019/04/25/developer-tools/f14/. Accessed: 2020-11-06

    2019

  3. [11]

    Optimal bounds for open addressing without reordering

    Mart \' n Farach-Colton, Andrew Krapivin, and William Kuszmaul. Optimal bounds for open addressing without reordering. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 594--605. IEEE, 2024

    2024

  4. [12]

    Greedy open addressing revisited: Beyond yao’s lower bound

    Mart \' n Farach-Colton, Andrew Krapivin, and William Kuszmaul. Greedy open addressing revisited: Beyond yao’s lower bound. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1116--1127, 2026

    2026

  5. [13]

    Notes on ``open'' addressing, 1963

    Don Knuth. Notes on ``open'' addressing, 1963

    1963

  6. [14]

    Scalable Hash Tables

    Tobias Maier. Scalable Hash Tables . PhD thesis, Dissertation, Karlsruhe, Karlsruher Institut f \"u r Technologie (KIT), 2021, 2022

    2021

  7. [15]

    Warpspeed: A high-performance library for concurrent gpu hash tables

    Hunter McCoy and Prashant Pandey. Warpspeed: A high-performance library for concurrent gpu hash tables. In 2026 Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX) , pages 15--30. SIAM, 2026

    2026

  8. [16]

    Bender, Alex Conway, Martin Farach - Colton, William Kuszmaul, Guido Tagliavini, and Rob Johnson

    Prashant Pandey, Michael A. Bender, Alex Conway, Martin Farach - Colton, William Kuszmaul, Guido Tagliavini, and Rob Johnson. Iceberght: High performance hash tables through stability and low associativity. Proc. ACM Manag. Data , 1(1):47:1--47:26, 2023

    2023

  9. [17]

    A seven-dimensional analysis of hashing methods and its implications on query processing

    Stefan Richter, Victor Alvarez, and Jens Dittrich. A seven-dimensional analysis of hashing methods and its implications on query processing. PVLDB , 9(3):96--107, 2015

    2015

  10. [18]

    Hashing with linear probing and referential integrity

    Peter Sanders. Hashing with linear probing and referential integrity. CoRR , abs/1808.04602, 2018

    2018 arXiv

  11. [19]

    Uniform hashing is optimal

    Andrew C Yao. Uniform hashing is optimal. Journal of the ACM (JACM) , 32(3):687--693, 1985

    1985

  12. [20]

    Locality in open addressing hash tables

    Or Zamir. Locality in open addressing hash tables

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.