Optimal Bounds for Open Addressing Without Reordering

Andrew Krapivin; Martin Farach-Colton; William Kuszmaul

REVIEW 5 major objections 4 minor 2 cited by

Optimal Bounds for Open Addressing Without Reordering

T0 review · 5 major / 4 minor · reviewed 2026-08-10 · 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 tight bounds for open-addressed hash tables that never reorder items, showing a greedy scheme reaches O(log² δ⁻¹) worst-case expected probes and settling the classical conjecture that uniform probing is optimal.

desk verdict Settles Yao's conjecture with matching bounds; the central claims hold up and the paper deserves a serious referee after a cleanup pass. read the letter →

arxiv 2501.02305 v2 pith:PJXHVNMU submitted 2025-01-04 cs.DS math.CO

Martin Farach-Colton , Andrew Krapivin , William Kuszmaul This is my paper · ORCID

classification cs.DSmath.CO MSC 68P2068W4068Q25

keywords openaddressinghashtablesprobecomplexityuniformhashinggreedyalgorithmsworst-caseexpectednoreorderingYaoconjecture

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

This paper shows that open-addressed hash tables can be made much faster than the classic uniform-probing design without ever moving already-inserted keys. One non-greedy scheme, elastic hashing, achieves O(1) amortized expected search cost and O(log δ⁻¹) worst-case expected search cost at load factor 1−δ. A greedy scheme, funnel hashing, achieves O(log² δ⁻¹) worst-case expected search cost, and the authors prove matching lower bounds: no greedy scheme can do better, and no no-reordering scheme can keep all keys below Ω(log² δ⁻¹ + log log n) with high probability. Together the upper and lower bounds disprove the long-standing conjecture that uniform probing is optimal for worst-case expected search cost, and they settle the optimal worst-case expected cost for greedy no-reordering tables at Θ(log² δ⁻¹).

What carries the argument

The load-bearing device is a two-dimensional probe sequence folded into one dimension by the injection φ(i,j) = O(i·j²), so a probe at row i and column j costs about i·j² probes. Elastic hashing uses this map to let an insertion probe far down a near-full array and then snap back to an earlier position in a less-full array, decoupling the number of probes made while inserting from the search probe complexity of the key. Funnel hashing instead groups the array into geometrically shrinking subarrays A₁,...,A_α plus a special final array A_{α+1}; a key tries one constant-size block in each subarray in order, and the final array uses a two-choice scheme with buckets of size O(log log n). The lower bounds run on the same structure: they use the monotonicity of expected greedy insertion costs and a compressed-table induction to force each level of slack to contribute a constant to the final insertion's expected cost, producing the sum ∑_{j=1}^{log δ⁻¹} c·j = Θ(log² δ⁻¹).

What would settle it

Fix any greedy open-addressing scheme, set δ = 2⁻ᵏ, and measure the expected probe count of the final insertion for k = 10, 20, 30, … with n large (say n = 2²⁰k). If the measured sequence is eventually below c·k² for every constant c, Theorem 4 is false; if funnel hashing itself is measured, the sequence should track Θ(k²), confirming the claimed exponent.

Watch

Extended reading notes

Core claim

The paper establishes tight bounds for open addressing without reordering. For greedy algorithms, it constructs funnel hashing, which splits the array into geometrically decreasing subarrays and probes one constant-size block in each, then falls back to a small two-choice final array; this gives worst-case expected probe complexity O(log² δ⁻¹) and, with high probability, O(log² δ⁻¹ + log log n). The matching lower bound shows the final insertion in any greedy scheme must take Ω(log² δ⁻¹) expected probes, so Θ(log² δ⁻¹) is the optimal worst-case expected search cost in the greedy setting. For non-greedy schemes, elastic hashing decouples probing during insertion from the position chosen, yielding O(1) amortized and O(log δ⁻¹) worst-case expected search cost, with a matching Ω(log δ⁻¹) lower bound for worst-case expected cost and a matching Ω(log² δ⁻¹ + log log n) high-probability lower bound. The consequence is that uniform probing is not optimal in the worst-case sense, and that open addressing can avoid the coupon-collector bottleneck without reordering.

Load-bearing premise

The lower bound for greedy schemes rests on Lemma 8's assertion that the expected cost of the j-th insertion is monotonically nondecreasing as the table fills; the paper states this follows from greedy behavior but does not prove it, and if this monotonicity failed the threshold argument would not go through.

Editorial extensions

If this is right

Greedy open addressing has optimal worst-case expected search cost Θ(log² δ⁻¹), so uniform probing's Θ(δ⁻¹) worst-case behavior is avoidable even with greedy insertions.
Open addressing without reordering can have constant amortized expected search cost, so reordering is not necessary to beat the coupon-collector bottleneck in amortized terms.
Funnel hashing guarantees with probability 1 − 1/poly(n) that every insertion probes O(log² δ⁻¹ + log log n) slots, and this high-probability worst-case bound is optimal among all no-reordering schemes.
Negative queries in greedy open-addressed tables have the same expected time as insertions, so funnel hashing also gives O(log² δ⁻¹) expected time for unsuccessful searches.

Reading between the lines

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

An extension left implicit is whether the Θ(log² δ⁻¹) greedy optimum persists under adversarial key orders; the lower-bound proofs in Section 5 assume random keys and i.i.d. probe sequences, so an adversary choosing the key sequence could behave differently.
The decoupling idea in elastic hashing—probing many slots that the insertion does not use—may carry over to other allocation problems with coupon-collector bottlenecks, such as load balancing, by charging wasted probes to the insert operation rather than to the subsequent search.
The lower-bound constants in Lemmas 8 and 9 are not optimized; computing the actual constant c for small δ would give practitioners a sense of the crossover where funnel hashing beats double hashing in practice.

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.

Desk Editor's Note

read the letter

The central result here is genuinely new and important: greedy no-reordering hash tables have worst-case expected search cost Theta(log^2 1/delta), not Theta(1/delta), which settles Yao's 1985 conjecture in the unexpected direction. The upper bound (funnel hashing) is simple once you see it: geometrically shrinking blocks of buckets, ending in a special small table. The matching lower bound is the harder piece, and it is mostly sound.

What the paper does well: elastic hashing is a genuinely clever decoupling of insertion probes from search probes, and it gives the first no-reordering scheme with O(1) amortized and O(log 1/delta) worst-case expected search cost, together with a matching general lower bound. The lower-bound technology—compressing the table after freezing a set S and applying Yao again—is clean. Credit where due: the authors also handle related work honestly, citing multilevel adaptive hashing and filter hashing as precursors for the funnel structure and using their own earlier work only for context.

Soft spots, in proportion: the text is sloppy in places. Lemma 8 asserts monotonicity of expected insertion costs q_j without proof. It is true—for greedy insertion, fixing a probe sequence, a superset of occupied slots cannot move the first free slot earlier—but as written it is an unsupported step in a lower bound that carries the whole section. Lemma 9 is also compressed: the induction over n and the "second-layer cost" argument requires the reader to fill in that the compressed table is a valid greedy open-addressing instance and that S is conditioned correctly. I checked this and it goes through, but it is not referee-ready as written. There are local typos (A_{i+2} vs A_{i+1}, "ci log n" for "ci log 1/delta"), and the delta > O(1/n) / delta > O(1/n^{o(1)}) conditions are stated informally. None of this undermines the asymptotic claims.

Bottom line: this deserves serious peer review. It changes the landscape for open addressing, and the proofs are credible. With a cleanup of Lemmas 8 and 9 and a notation pass, it should be accepted. I would bring it to a reading group and would cite it.

Referee Report

5 major / 4 minor

Summary. The paper studies open-addressed hash tables that do not reorder inserted elements. It presents two new schemes: elastic hashing, which achieves O(1) amortized and O(log 1/δ) worst-case expected probe complexity without reordering, and funnel hashing, a greedy scheme achieving O(log^2 1/δ) worst-case expected probe complexity. It claims matching lower bounds, including a lower bound of Ω(log^2 1/δ) for all greedy schemes, thereby disproving Yao's 1985 conjecture that uniform probing is optimal in the worst-case expected sense. The paper also gives lower bounds for arbitrary non-reordering schemes: Ω(log 1/δ) worst-case expected and Ω(log^2 1/δ + log log n) high-probability worst-case. The proofs combine decoupling arguments for elastic hashing, a layered bucket structure for funnel hashing, and inductive/compression arguments for lower bounds.

Significance. If the main theorems are correct, the paper resolves a longstanding open problem and provides tight bounds for a basic data-structure question. The conceptual contributions — decoupling insertion probes from search probes and the layered funnel construction — are interesting and likely to influence subsequent work on hashing and load balancing. The paper also makes good use of external benchmarks: Yao's theorem, Vöcking's theorem, and the power-of-two-choices theorem are invoked appropriately. However, the written proofs contain several nontrivial errors and missing justifications, especially in the lower-bound sections, so the results are not yet fully verified in the present form.

major comments (5)

[Section 4, Lemma 8] The proof of Lemma 8 has two problems. First, the monotonicity of q_j is asserted without proof; it is true for greedy schemes via a coupling argument, but since this is load-bearing for the lower bound, it must be stated and proved. Second, the displayed inequality E[Σ q_j] ≥ Σ_{i} (n/2^i) q_{(1-1/2^i)n} is in the wrong direction for a nondecreasing sequence. For example, with n=8, q_1=...=q_3=0, q_4=...=q_8=10, the right side is 70 while the left side is 50. The intended argument requires the reverse inequality, obtained by partitioning the insertions into intervals [(1-1/2^{i-1})n, (1-1/2^i)n] and upper-bounding each q_j by the value at the right endpoint. As written, the proof does not establish Lemma 8, and Lemma 8 is essential for Theorem 4.
[Section 4, Lemma 9] In the final paragraph of the proof, the text says the final insertion must perform 'at least ci log n expected probes' to find slots not in S; this should be ci log δ^{-1}. More importantly, the claim is not immediate from Lemma 8 and needs a proof: for a fixed probe sequence, the index of the first free slot at the final load is at least the index at the time of the (1 - 1/2^i)n-th insertion, so the number of probes landing in S is at least the corresponding number at that earlier time. Without this coupling argument, the additive lower bound on the total cost is unjustified.
[Section 5.2, Theorem 5 proof] The chain '2c = |{Hi : i∈[2c]}| = |{Hi : i∈[2c]}∩[n]| = E[|{Hi : i∈[2c]}∩[n]|]' is invalid: 2c is an upper bound on the number of distinct probes, not an equality, and the intermediate object is random. The correct argument is '2c ≥ E[|{Hi : i∈[2c]}|] ≥ Σ_j q_j', which then yields c = Ω(log δ^{-1}). The intended conclusion is correct, but the proof as written does not go through.
[Section 5.3, Claim 11] There is a reversed inequality in the derivation of the bound on E[|t_i ∩ ∪_{j>i} H^c(k_j)|]. The text concludes |t_i| - |t_i|(nδ/|s_i|)^{1/8} < |t_i|/2 from (nδ/|s_i|)^{1/8} < 1/2, but if a < 1/2, then |t_i|(1-a) > |t_i|/2. Thus the claimed upper bound E[...] < |t_i|/2 does not follow; the preceding expression is close to |t_i| when |s_i| >> nδ. Since Claim 11 is necessary for Theorem 6, this is a load-bearing gap that needs a genuinely reworked proof, not just a typo fix.
[Section 3, proof of Theorem 2 (amortized bound)] The amortized expected probe complexity analysis is not justified. The text asserts that the total expected probe complexity across all keys is at most |A1|·c log δ^{-1} + |A2|·2c log δ^{-1} + ... , but it does not prove a bound on the number of keys that reach each A_i. A key can fail in A_i even after A_i is full, so the number of attempts to A_i is not obviously O(|A_i|); an argument along the lines of 'the number of failures from A_i is at most the number of insertions that arrive after A_i is filled, which is geometrically decreasing' is needed. Without this, the O(log δ^{-1}) amortized claim in Theorem 2 is not established.

minor comments (4)

[Section 2, Lemma 2] In the paragraph after the Chernoff bound, the text says the first 0.27m insertions 'can fill array A_{i+2}'; this should be A_{i+1}, since Case 3 depends on A_{i+1} being 75% full.
[Section 3, Lemma 5] The McDiarmid exponent is written as exp(-|Ai| O(β^2 δ^2)), but the preceding calculation yields exp(-|Ai| O(δ^2/β^2)). The asymptotic conclusion n^{1-o(1)} is unchanged, but the exponent should be corrected.
[Section 3, A_{α+1} implementation] The text says an insertion into C checks 'at most 2 log log n slots', but the probe sequence alternates between two buckets each of size 2 log log n, so the worst-case number of checked slots is 4 log log n. The asymptotic O(log log n) statement is unaffected.
[Section 5.2, notation] The symbol L_j is used both for a set of locations and for individual locations L_i; this makes equations such as 'E[|Li∩vj|]' confusing. Please use separate notation for the set and for individual locations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: central claims are derived from external theorems and internal constructions; self-citations are not load-bearing.

full rationale

The paper's derivation chain is not circular. Theorem 1 is proved from internal lemmas analyzing the elastic-hashing construction directly; no fitted parameter is repackaged as a prediction. Theorem 2's upper bound rests on the funnel-hashing construction plus the externally cited power-of-two-choices theorem [5] and the paper's own probability lemmas. Theorem 4's greedy lower bound is built on Yao's theorem [21] as an external benchmark, together with an induction on compressed tables; the asserted monotonicity of the q_j in Lemma 8 is unproved in the text but follows from set inclusion of occupied slots and is not a circular input. Section 5's lower bounds rely on Vocking's balls-and-bins theorem [20] and capacity arguments, not on the paper's own conclusions. The only self-citations, refs [2] and [3], appear in historical/motivational context and in the remark that Theorem 7's proof mirrors Theorem 5.2 of [3]; the actual log log n argument is supplied in the paper using [20], so the self-citation is not load-bearing. No equation is defined in terms of the quantity it is used to prove, and no fitted quantity is renamed as a prediction.

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

No parameters are fitted to data. The proofs rely on the standard random probing model, Yao's 1985 theorem, the power-of-two-choices theorem, and one monotonicity assertion stated without proof.

assumptions (5)

domain assumption Random probing model: each key's probe sequence is an iid draw from a distribution P (uniform for upper bounds).
This is the standard model from Yao (1985) and is used throughout; Section 5 explicitly assumes the probe sequences are iid random variables.
standard math Yao's theorem (Proposition 7): any greedy open-addressed scheme has amortized expected insertion time Omega(log 1/delta).
Cited as [21] and used as a black box in Lemma 8 to establish the threshold lower bound.
standard math Power-of-two-choices theorem (Theorem 3, [5]): placing m balls into n bins by choosing the emptier of two random bins gives max load m/n + log log n + O(1).
Used in Section 3 to analyze the special array C of funnel hashing.
ad hoc to paper Monotonicity of expected insertion cost for greedy schemes (q_j nondecreasing).
Stated without proof in Lemma 8; it is true because the occupied set grows monotonically, but the paper does not demonstrate it.
domain assumption For lower bounds, keys are sampled uniformly from a large universe so probe sequences are iid.
Section 5: 'we assume that the probe sequences for keys are iid random variables. This is equivalent to assuming that the universe size is a large polynomial and then sampling the keys at random.'

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal Bounds for Open Addressing Without Reordering." pith.science (2026). https://pith.science/paper/PJXHVNMU

@misc{pith2026250102305,
  author       = {Pith},
  title        = {Pith review of: Optimal Bounds for Open Addressing Without Reordering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PJXHVNMU}},
  note         = {Machine review of arXiv:2501.02305}
}

read the original abstract

In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved with as few probes as possible. We show that, even without reordering elements over time, it is possible to construct a hash table that achieves far better expected search complexities (both amortized and worst-case) than were previously thought possible. Along the way, we disprove the central conjecture left by Yao in his seminal paper ``Uniform Hashing is Optimal''. All of our results come with matching lower bounds.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Locality in Open Addressing Hash Tables
cs.DS 2026-07 accept novelty 8.0 of 10

In immutable open addressing, locality Ω(1/ε²) at some load is unavoidable, matching linear probing; with the final load known, Õ(1/ε) per-operation probes and locality are achievable.
Succinct and Fast Tiny Pointer Hash Tables
cs.DS 2026-07 conditional novelty 7.0 of 10

Two practical hash-table designs—Chained-TPHT and Flattened-TPHT—use byte-sized pointers and key quotienting to reach 105.4% and 83.4% space efficiency with constant-time operations and high throughput.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages · cited by 2 Pith papers

[1]

There is no fast single hashing algorithm

Mikl´ os Ajtai, J´ anos Koml´ os, and Endre Szemer´ edi. There is no fast single hashing algorithm. Information Processing Letters, 7(6):270–273, 1978

work page 1978
[2]

Iceberg hashing: Optimizing many hash-table c riteria at once

Michael A Bender, Alex Conway, Mart ´ ın Farach-Colton, W illiam Kuszmaul, and Guido Tagliavini. Iceberg hashing: Optimizing many hash-table c riteria at once. Journal of the ACM , 70(6):1–51, 2023

work page 2023
[3]

Bender, Alex Conway, Mart ´ ın Farach-Colton, William Kuszmaul, and Guido Tagliavini

Michael A. Bender, Alex Conway, Mart ´ ın Farach-Colton, William Kuszmaul, and Guido Tagliavini. Tiny Pointers, pages 477–508. 2023. doi:10.1137/1.9781611977554.ch21

doi:10.1137/1.9781611977554.ch21 2023
[4]

Bender, Martin Farach-Colton, Simai He, Brad ley C

Michael A. Bender, Martin Farach-Colton, Simai He, Brad ley C. Kuszmaul, and Charles E. Leiserson. Adversarial contention resolution for simple c hannels. In SPAA, pages 325–332. ACM, 2005

work page 2005
[5]

Balanced allocations: the heavily loaded case

Petra Berenbrink, Artur Czumaj, Angelika Steger, and Be rthold V¨ ocking. Balanced allocations: the heavily loaded case. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , STOC ’00, page 745–754. Association for Computing Machine ry, 2000. doi:10.1145/335305.335411

work page arXiv
[6]

Reducing the retrieval time of scatter s torage techniques

Richard P Brent. Reducing the retrieval time of scatter s torage techniques. Communications of the ACM , 16(2):105–109, 1973. 21

work page 1973
[7]

Multilevel adaptive ha shing

Andrei Z Broder and Anna R Karlin. Multilevel adaptive ha shing. In Proceedings of the ﬁrst annual ACM-SIAM symposium on Discrete algorithms , pages 43–53, 1990

work page 1990
[8]

External double hashing with choice

Walter A Burkhard. External double hashing with choice. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), pages 8–pp. IEEE, 2005

work page 2005

Show all 21 references

[9]

Space eﬃcient hash tables with worst case constant access time

Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul S pirakis. Space eﬃcient hash tables with worst case constant access time. Theory of Computing Systems , 38(2):229–248, 2005

2005
[10]

Eﬃcient ordering of hash tables

Gaston H Gonnet and J Ian Munro. Eﬃcient ordering of hash tables. SIAM Journal on Computing, 8(3):463–478, 1979

1979
[11]

Notes on “open” addressing

Donald E Knuth. Notes on “open” addressing. Unpublished memorandum, pages 11–97, 1963

1963
[12]

Computer science and its relation to mat hematics

Donald E Knuth. Computer science and its relation to mat hematics. The American Mathematical Monthly, 81(4):323–343, 1974

1974
[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]

More analysis of double hashing

George Lueker and Mariko Molodowitch. More analysis of double hashing. In Proceedings of the twentieth annual ACM symposium on Theory of computing , pages 354–359, 1988

1988
[15]

Double hashing wit h multiple passbits

Paul M Martini and Walter A Burkhard. Double hashing wit h multiple passbits. International Journal of Foundations of Computer Science , 14(06):1165–1182, 2003

2003
[16]

Analysis and design of algorithms: double hashing and paral lel graph searching

Mariko Molodowitch. Analysis and design of algorithms: double hashing and paral lel graph searching. University of California, Irvine, 1990

1990
[17]

Techniques for collision re solution in hash tables with open addressing

J Ian Munro and Pedro Celis. Techniques for collision re solution in hash tables with open addressing. In Proceedings of 1986 ACM Fall joint computer conference , pages 601–610, 1986

1986
[18]

Hashing with linear probing and referen tial integrity

Peter Sanders. Hashing with linear probing and referen tial integrity. arXiv preprint arXiv:1808.04602, 2018

2018 arXiv
[19]

A note on the eﬃciency of hashing functio ns

Jeﬀrey D Ullman. A note on the eﬃciency of hashing functio ns. Journal of the ACM (JACM) , 19(3):569–575, 1972

1972
[20]

How asymmetry helps load balancing

Berthold V¨ ocking. How asymmetry helps load balancing . Journal of the ACM (JACM) , 50(4):568–589, 2003

2003
[21]

Uniform hashing is optimal

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

1985

Pith tools

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

[1] [1]

There is no fast single hashing algorithm

Mikl´ os Ajtai, J´ anos Koml´ os, and Endre Szemer´ edi. There is no fast single hashing algorithm. Information Processing Letters, 7(6):270–273, 1978

work page 1978

[2] [2]

Iceberg hashing: Optimizing many hash-table c riteria at once

Michael A Bender, Alex Conway, Mart ´ ın Farach-Colton, W illiam Kuszmaul, and Guido Tagliavini. Iceberg hashing: Optimizing many hash-table c riteria at once. Journal of the ACM , 70(6):1–51, 2023

work page 2023

[3] [3]

Bender, Alex Conway, Mart ´ ın Farach-Colton, William Kuszmaul, and Guido Tagliavini

Michael A. Bender, Alex Conway, Mart ´ ın Farach-Colton, William Kuszmaul, and Guido Tagliavini. Tiny Pointers, pages 477–508. 2023. doi:10.1137/1.9781611977554.ch21

doi:10.1137/1.9781611977554.ch21 2023

[4] [4]

Bender, Martin Farach-Colton, Simai He, Brad ley C

Michael A. Bender, Martin Farach-Colton, Simai He, Brad ley C. Kuszmaul, and Charles E. Leiserson. Adversarial contention resolution for simple c hannels. In SPAA, pages 325–332. ACM, 2005

work page 2005

[5] [5]

Balanced allocations: the heavily loaded case

Petra Berenbrink, Artur Czumaj, Angelika Steger, and Be rthold V¨ ocking. Balanced allocations: the heavily loaded case. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , STOC ’00, page 745–754. Association for Computing Machine ry, 2000. doi:10.1145/335305.335411

work page arXiv

[6] [6]

Reducing the retrieval time of scatter s torage techniques

Richard P Brent. Reducing the retrieval time of scatter s torage techniques. Communications of the ACM , 16(2):105–109, 1973. 21

work page 1973

[7] [7]

Multilevel adaptive ha shing

Andrei Z Broder and Anna R Karlin. Multilevel adaptive ha shing. In Proceedings of the ﬁrst annual ACM-SIAM symposium on Discrete algorithms , pages 43–53, 1990

work page 1990

[8] [8]

External double hashing with choice

Walter A Burkhard. External double hashing with choice. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), pages 8–pp. IEEE, 2005

work page 2005