Pith. sign in

REVIEW 1 major objections 4 minor 33 references

Locality in Open Addressing Hash Tables

T0 review · 1 major / 4 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 no open-addressing hash table without reordering can achieve expected insertion locality better than Θ(1/ε²) at every load 1−ε, matching the locality profile of linear probing.

desk verdict A genuinely new and mostly rigorous paper: it introduces locality as a formal parameter for immutable open addressing, proves tight lower bounds and matching upper bounds, and explains linear probing's practical edge—but the abstract slightly overstates the formal result by omitting the stateless first-probe assumption. read the letter →

arxiv 2607.16390 v1 pith:JSDWYNJ4 submitted 2026-07-17 cs.DS

Or Zamir This is my paper · ORCID
classification cs.DS MSC 68P0568W40
keywords localityopenaddressinghashtableswithoutreorderinglinearprobingoptimaltransportlowerboundvarianceconcentrationexternalmemorypagesizegreedyschemes
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

The paper introduces a new performance measure for open-addressed hash tables: locality, the geometric distance between the first probed cell and the farthest cell inspected during an operation. It proves a lower bound: in any scheme that never reorders keys, and whose first probe for a key depends only on the key and the table initialization, the expected insertion locality at load 1−ε cannot be o(1/ε²) at every load. This makes linear probing's quadratic locality profile optimal among immutable schemes. It also proves an amortized lower bound of Ω(1/ε) over a full insertion sequence, and derives a necessary page size Ω(1/ε²) for 1+o(1) page span in external memory. Two upper bounds show the lower bounds are nearly tight: with the target load known in advance, every insertion and search can achieve expected cost Õ(1/ε); without that knowledge, a greedy expanding-window scheme achieves optimal expected probe count with quadratic distance growth.

What carries the argument

The load-bearing object is a one-dimensional optimal-transport lower bound (Section 3): for m=(1−ε)n i.i.d. home locations from any distribution on the cycle, the minimum expected total movement to reach distinct cells is Ω(n/ε). It is proved by an interval-overload argument — intervals of length Θ(1/ε²) overflow by Θ(1/ε) particles in expectation — plus a convexity argument showing the uniform distribution minimizes this overload. Section 4 converts this into hashing bounds via the stateless-first-probe assumption. The upper bounds rest on a variance lemma (Lemma 5.1): in any symmetric greedy scheme, Var(|O_t∩I|) ≤ |I| for every fixed set I, proved through Efron–Stein's inequality and a swa

What would settle it

Exhibit any open-addressing scheme without reordering whose first probe is stateless and whose expected insertion locality at load 1−ε is o(ε^{-2}) at every load; even a single such scheme with ε→0 would refute Theorem 4.1. Concretely, simulate any candidate on a cycle with nε²≫1 and measure expected locality for a sequence ε→0 (e.g., ε = n^{-1/4}, n^{-1/3}, n^{-1/2}) to see if it grows slower than ε^{-2}. A cheaper check: numerically compute the optimal transport cost for i.i.d. uniform points on a cycle of size n and verify that it is Ω(n/ε) as ε→0.

Watch

Extended reading notes

Core claim

The central discovery is that locality, not probe count, is the quantity that resists improvement in immutable open addressing. The proof works by reducing hashing to a one-dimensional optimal transport problem: after inserting (1−ε)n random keys, their first-probe locations form i.i.d. points from an arbitrary distribution on the cyclic table, and any distinct final placement must move these points a total expected distance of Ω(n/ε). Since each key's locality radius is at least its displacement, the amortized lower bound follows; an integration argument upgrades it to the all-load o(1/ε²) impossibility. The paper matches these bounds with a variance lemma showing that the occupied set of a

Load-bearing premise

The first probed cell for a key depends only on the key and the table's initialization, never on the keys already inserted; if an algorithm could point its first probe at a currently empty or lightly loaded region, the transport lower bound would not apply.

Editorial extensions

If this is right

  • If the main lower bound is right, linear probing's Θ(1/ε²) expected insertion locality cannot be improved by any no-reordering scheme, so practical gains in probe count must come from non-greedy placement or from knowing the target load.
  • The page-size consequence means immutable external-memory hash tables need B=Ω(1/ε²) to achieve 1+o(1) expected page accesses per operation; the quadratic block-size barrier for space-efficient hashing without reordering is not an artifact of construction.
  • With the target load known in advance, the Õ(1/ε) construction shows the amortized lower bound is essentially tight and can be deamortized: every insertion and search pays the same expected cost.
  • The variance lemma extends to all symmetric probing schemes: any fixed-shift or random-shift symmetric scheme has expected probe count O(log n/ε²) at every load, a weak but all-load uniform guarantee.
  • Without knowing the load, the expanding-window greedy scheme simultaneously achieves the optimal Θ(1/ε) expected probe count and a quadratic distance profile, giving locality O(1/ε²) with high constant probability — though expected locality at that scale remains open.

Reading between the lines

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

  • One testable corollary of the transport lower bound is that any immutable scheme's locality profile is determined almost entirely by the geometry of final placement, not by the probing rule; a scheme that keeps keys hyperlocal after placement could in principle escape the lower bound, but the stateless-first-probe assumption blocks exactly such adaptations.
  • The variance lemma suggests occupied sets in symmetric probing behave like independent Bernoulli cells to first order; a natural next step would be to ask whether higher moments obey similar bounds, which would resolve the open expected-locality question for the expanding-window sampler.
  • In database and cache settings where the target load is rarely known in advance, the all-load lower bound implies that the choice between linear probing and uniform probing is a genuine tradeoff with no free lunch — only knowing ε in advance or allowing reordering/rebuilding changes the picture.
  • The paper's lower bound applies to all no-reordering algorithms, greedy or not; so the open question it leaves is whether non-greedy placement can cut probe count while preserving the quadratic locality — a search space the transport argument does not constrain.
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 / 4 minor

Summary. The paper introduces locality—the maximum geometric distance from the first probed cell to any cell inspected or used—as a complement to probe count for immutable (no-reordering) open-addressing hash tables. The main lower-bound results are: (1) an amortized Ω(1/ε) expected-locality lower bound for any sequence of (1−ε)n insertions, even when ε is known in advance, and (2) an all-load impossibility result stating that no scheme in the stated model can have expected insertion locality o(1/ε²) at every load 1−ε. The lower bounds are obtained from a distribution-free transport theorem (Section 3): i.i.d. home locations from any distribution on Z_n require Ω(n/ε) expected movement to distinct cells. Section 4 reduces the hashing problem to this transport statement and derives an external-memory page-size consequence. The upper-bound half proves a variance lemma for symmetric greedy probing schemes (Section 5), gives a load-oblivious greedy scheme with expected O(1/ε) probes and quadratic probe-distance growth, and gives a multilevel deamortized construction with E[T], E[R] = O(ε^{-1} log³(1/ε)) when the final load is known in advance (Section 6). The paper is candid about open problems, including the gap between first-moment probe bounds and expected locality.

Significance. If the formal theorems are taken as stated, this is a substantial contribution. The lower bound gives a clean, self-contained explanation of why linear probing's quadratic locality profile is optimal among immutable schemes, despite the recent probe-count improvements for no-reordering tables; it also provides a geometric justification for the classical B = Ω(1/ε²) page-size threshold. The proof chain is elegant: the interval-overload inequality, the convexity argument showing that the uniform distribution minimizes expected interval overload, and the hashing reduction are all sound. The variance lemma for symmetric probing schemes is a robust and potentially reusable structural statement. The paper is also appropriately candid about its limitations, explicitly noting the necessity of the stateless-first-probe assumption and the failure of the load-oblivious upper bound to yield an expected-locality guarantee. No fitted parameters or circular benchmarks are involved. Provided the advertised statements are qualified to match the formal model, this is a valuable paper.

major comments (1)
  1. [Abstract / §1.1 / Theorem 4.1] The advertised no-subquadratic-locality theorem is stated more strongly than the formal result. Theorem 4.1 requires both (a) the stateless-first-probe assumption and (b) the profile f to be locally bounded. Section 4 explicitly notes that (a) is necessary: without it, a free-list scheme can first-probe an empty cell, so the abstract's unqualified sentence is false. Assumption (b) is also used essentially in the proof of Theorem 4.1: if f is allowed to be unbounded on a fixed interval [δ0,1], the O(n) insertions at non-small loads cannot be controlled by M0 n, and the integration argument does not go through. Please qualify the abstract and informal theorems so that they match the formal statement and the model.
minor comments (4)
  1. [Remark 5.3] The claimed O(ε^{-2} log n) bound for 'any fixed sequence of shifts' is not justified as written when the first k shifts contain duplicates. The proof treats S_k as a set of size k, but if the shifts are not distinct then |S_k| < k, the equality E[|E_t ∩ (h+S_k)|] = εk fails, and the tail probability O(1/(ε²k)) need not hold for a degenerate sequence that repeatedly probes the same cell. Restrict to sequences whose first k probes are distinct, or replace k by |S_k| and adjust the summation.
  2. [Theorem 4.3 / §4.1] The sentence 'in all cache-oblivious schemes' overstates the scope. The result is a lower bound for immutable open addressing with stateless first probe, not for the standard cache-oblivious model. The relation between locality R and page span R/B is also an inequality, not an equality; the proof is clear, but the wording should be aligned with the formal model.
  3. [§2.2 and Algorithm 1] The definition of symmetric greedy mechanisms states that the whole probe sequence is sampled before insertion, while Algorithm 1 is described lazily, sampling phase by phase. These are equivalent, but this equivalence should be stated explicitly to avoid confusion about adaptivity.
  4. [Section 6] The construction assumes that all block sizes divide the table exactly ('assume for simplicity'). Since the results are asymptotic, this is likely harmless, but the rounding details should be acknowledged or deferred to a full version so that the proof is complete for arbitrary n.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; all load-bearing lower and upper bound statements are proved from scratch.

full rationale

The derivation chain is self-contained. Theorem 4.2 (amortized locality lower bound) is derived from the transport lower bound Theorem 3.6, which is proven in Section 3 via Lemma 3.1 (interval overload), Lemma 3.2 (binomial overload), Lemma 3.4 (convexity of g(p)), and Lemma 3.5 (uniform distribution minimizes interval overload). Theorem 4.1 then follows from Theorem 4.2 by a standard integration argument; the only assumptions (stateless first probe and universe ω(n²)) are explicit model assumptions, and the paper itself flags the first as necessary. The upper bounds are also self-contained: Lemma 5.1 proves the interval variance bound for symmetric schemes from the Efron–Stein inequality and a coupling argument, and Corollary 5.2 plus Algorithm 1 prove the O(1/ε) probe bound with R=O(T²); Section 6 proves the known-load upper bound using its own Lemma 6.2 (biased minimum allocation) and Lemma 6.3 (top-block overload). Constants such as A, a, C are universal existence constants chosen sufficiently large in the proofs, not fitted parameters, and no claimed prediction is reused as an input. External benchmarks (linear probing Θ(1/ε²), JP08/BKK22 thresholds, KX24 quadratic probing results) are cited as independent context or comparison, not as load-bearing justifications for the paper's own theorems; there are no self-citations. The only caveat is presentational: the informal abstract claim omits the stateless-first-probe and large-universe qualifications that the formal Theorem 4.1 states, but this is an overstatement of the model, not a circular step.

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

The central claims rest on the no-reordering model, the stateless first-probe assumption, and standard concentration inequalities. The constructions introduce block-size parameters and constants, but no new physical or mathematical entities and no fitted values.

free parameters (5)
  • a (interval length constant in Lemma 3.2)
    Absolute constant chosen sufficiently small so that L=a/ε² and the Berry-Esseen step gives a constant lower tail probability. Not fitted to data.
  • C (nε² threshold in Lemma 3.2)
    Absolute constant chosen sufficiently large to ensure σ² → ∞ for Berry-Esseen. Not empirical.
  • A (window constant in Algorithm 1)
    Absolute constant, chosen large so the one-phase failure probability C4^{-k} is summable. Not fitted.
  • a (sample constant in Algorithm 1)
    Absolute constant, chosen large so the exponential failure term exp(-aε/(2Δ_j)) is small. Not fitted.
  • C (block-size constant in Section 6)
    Absolute constant chosen large so ε²B_k = Cℓ and the failure probabilities η_i, top-block tails are ≤ ε^{10}. Not fitted.
assumptions (6)
  • standard math Chernoff, Berry-Esseen, Efron-Stein, Chebyshev concentration inequalities
    Used throughout Sections 3, 5, 6; standard and accepted.
  • domain assumption Open addressing without reordering: once a key is stored, it never moves
    This is the model under study (Section 2.1). All results are conditional on this structural restriction.
  • domain assumption Stateless first probe: first probed cell depends only on the key and initialization, not on previously inserted elements
    Explicit assumption in Section 4; necessary for the lower bounds. If violated, an algorithm could adaptively choose sparse regions and beat the locality lower bound.
  • domain assumption Universe size ω(n²)
    Section 4; ensures m random keys are distinct with probability 1−o(1). If |U|=n, the identity hash avoids collisions trivially.
  • domain assumption Symmetric greedy probing model for upper bounds (uniform home, shifts independent of home)
    Section 2.2 and 5.1; the variance lemma and load-oblivious upper bound are proven for this class.
  • domain assumption Block sizes divide the table (technical divisibility)
    Assumed 'for simplicity' in Section 6; standard rounding handles general n without changing asymptotics.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Locality in Open Addressing Hash Tables." pith.science (2026). https://pith.science/paper/JSDWYNJ4

@misc{pith2026260716390,
  author       = {Pith},
  title        = {Pith review of: Locality in Open Addressing Hash Tables},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JSDWYNJ4}},
  note         = {Machine review of arXiv:2607.16390}
}
abstract

Open-addressed hash tables without reordering, such as linear probing and uniform probing, are among the simplest and most widely used data structures. Their performance is traditionally measured by probe count. We study a complementary parameter: locality, defined as the geometric distance from the first probed location to the farthest cell inspected or used. At load factor $1-\varepsilon$, uniform probing achieves the optimal $\Theta(1/\varepsilon)$ probe count among greedy schemes, but has essentially no locality, whereas linear probing is highly local but performs $\Theta(1/\varepsilon^2)$ probes. We show that this quadratic locality scale is fundamental: no open-addressing algorithm without reordering can achieve locality $o(1/\varepsilon^2)$ simultaneously at every load $1-\varepsilon$. We also prove an amortized expected-locality lower bound of $\Omega(1/\varepsilon)$ over any sequence of $(1-\varepsilon)n$ insertions, even when the final load is known in advance. Our lower bound further implies that page size $B=\Omega(1/\varepsilon^2)$ is necessary for $1+o(1)$ expected page span in immutable open addressing. We complement these lower bounds with two upper bounds. When the target load is known in advance, every insertion and every successful or unsuccessful search can be given expected probe count and locality $\widetilde O(1/\varepsilon)$, essentially deamortizing the amortized lower bound. We also give a load-oblivious greedy scheme with optimal expected probe count $\Theta(1/\varepsilon)$ whose $i$-th probe is at distance $O(i^2)$ from the first probe. Its analysis gives a general variance bound for occupied-cell densities in symmetric probing schemes, implying an $O(\log n/\varepsilon^2)$ expected probe bound for every fixed-shift probing sequence and every load $1-\varepsilon$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 1 canonical work pages

  1. [1]

    , title =

    Knuth, Donald E. , title =. 1998 , isbn =

    1998

  2. [2]

    Algorithmica , volume =

    Flajolet, Philippe and Poblete, Patricio and Viola, Alfredo , title =. Algorithmica , volume =. 1998 , doi =

    1998

  3. [3]

    , title =

    Yao, Andrew C.-C. , title =. Journal of the ACM , volume =. 1985 , doi =

    1985

  4. [4]

    and Kuszmaul, William and Zhou, Renfei , title =

    Bender, Michael A. and Kuszmaul, William and Zhou, Renfei , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2025 , doi =. 2503.13628 , archivePrefix =

    arXiv 2025

  5. [5]

    51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , series =

    Kuszmaul, William and Xi, Zoe , title =. 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) , series =. 2024 , doi =

    2024

  6. [6]

    Algorithmica , volume =

    Jensen, Morten Skaarup and Pagh, Rasmus , title =. Algorithmica , volume =. 2008 , doi =

    2008

  7. [7]

    Journal of Algorithms , volume =

    Pagh, Rasmus and Rodler, Flemming Friche , title =. Journal of Algorithms , volume =. 2004 , doi =

    2004

  8. [8]

    Physical Review , volume =

    Tonks, Lewi , title =. Physical Review , volume =. 1936 , doi =

    1936

Show all 33 references
  1. [9]

    Alder, B. J. and Wainwright, T. E. , title =. The Journal of Chemical Physics , volume =. 1957 , doi =

    1957

  2. [10]

    , title =

    Forrester, Peter J. , title =. 2010 , isbn =

    2010

  3. [11]

    2017 , eprint =

    Serfaty, Sylvia , title =. 2017 , eprint =. doi:10.48550/arXiv.1709.04089 , url =

    2017 doi arXiv

  4. [12]

    Networks and Heterogeneous Media , volume =

    Maury, Bertrand and Roudneff-Chupin, Aude and Santambrogio, Filippo and Venel, Juliette , title =. Networks and Heterogeneous Media , volume =. 2011 , doi =

    2011

  5. [13]

    Lagrangian Discretization of Crowd Motion and Linear Diffusion , journal =

    Leclerc, Hugo and M. Lagrangian Discretization of Crowd Motion and Linear Diffusion , journal =. 2020 , doi =

    2020

  6. [14]

    Concentration Inequalities , booktitle =

    Boucheron, St. Concentration Inequalities , booktitle =. 2004 , doi =

    2004

  7. [15]

    Communications of the ACM , volume =

    Aggarwal, Alok and Vitter, Jeffrey Scott , title =. Communications of the ACM , volume =. 1988 , doi =

    1988

  8. [16]

    Using Hashing to Solve the Dictionary Problem (in External Memory) , booktitle =

    Iacono, John and P. Using Hashing to Solve the Dictionary Problem (in External Memory) , booktitle =. 2012 , doi =

    2012

  9. [17]

    Optimal Hashing in External Memory , booktitle =

    Conway, Alex and Farach-Colton, Mart. Optimal Hashing in External Memory , booktitle =. 2018 , doi =

    2018

  10. [18]

    Communications of the ACM , volume =

    Maurer, Ward Douglas , title =. Communications of the ACM , volume =. 1968 , doi =

    1968

  11. [19]

    Hopgood, F. R. A. and Davenport, J. , title =. The Computer Journal , volume =. 1972 , doi =

    1972

  12. [20]

    , title =

    Ecker, A. , title =. The Computer Journal , volume =. 1974 , doi =

    1974

  13. [21]

    Communications of the ACM , volume =

    Batagelj, Vladimir , title =. Communications of the ACM , volume =. 1975 , doi =

    1975

  14. [22]

    , title =

    Radke, Charles E. , title =. Communications of the ACM , volume =. 1970 , doi =

    1970

  15. [23]

    and Leiserson, Charles E

    Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , title =. 2009 , isbn =

    2009

  16. [24]

    2000 , isbn =

    Weiss, Mark Allen , title =. 2000 , isbn =

    2000

  17. [25]

    Quadratic Probing , howpublished =

  18. [26]

    Proceedings of the 19th International Symposium on Distributed Computing (DISC) , series =

    Purcell, Chris and Harris, Tim , title =. Proceedings of the 19th International Symposium on Distributed Computing (DISC) , series =. 2005 , doi =

    2005

  19. [27]

    String Processing and Information Retrieval , series =

    Askitis, Nikolas and Zobel, Justin , title =. String Processing and Information Retrieval , series =. 2005 , doi =

    2005

  20. [28]

    and Kuszmaul, William and Zhou, Renfei , title =

    Bender, Michael A. and Kuszmaul, William and Zhou, Renfei , title =. Proceedings of the 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2024 , doi =. 2409.11280 , archivePrefix =

    2024 arXiv

  21. [29]

    Optimal Bounds for Open Addressing Without Reordering , booktitle =

    Farach-Colton, Mart. Optimal Bounds for Open Addressing Without Reordering , booktitle =. 2024 , doi =. 2501.02305 , archivePrefix =

    2024 arXiv

  22. [30]

    Greedy Open Addressing Revisited: Beyond Yao's Lower Bound , booktitle =

    Farach-Colton, Mart. Greedy Open Addressing Revisited: Beyond Yao's Lower Bound , booktitle =. 2026 , doi =

    2026

  23. [31]

    and Pandey, Prashant , title =

    Chesetti, Yuvaraj and Shi, Benwei and Phillips, Jeff M. and Pandey, Prashant , title =. Proceedings of the ACM on Management of Data , volume =. 2025 , doi =

    2025

  24. [32]

    and Kuszmaul, Bradley C

    Bender, Michael A. and Kuszmaul, Bradley C. and Kuszmaul, William , title =. Proceedings of the 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2022 , doi =. 2107.01250 , archivePrefix =

    2021 arXiv

  25. [33]

    Theoretical Computer Science , volume =

    Dietzfelbinger, Martin and Weidling, Christoph , title =. Theoretical Computer Science , volume =. 2007 , doi =

    2007

Pith tools

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