HackerPapers

arXiv:2501.02305cs.DS

Optimal Bounds for Open Addressing Without Reordering

Martin Farach-Colton, Andrew Krapivin, William Kuszmaul

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms math.COCombinatorics

On Hacker News

Linked by 7 identifiable commenters in 7 comments across 3 threads, from Feb 2025 to Dec 2025. Found in 2 HN submissions from Feb 2025 to May 2025. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Speeding Up Hash Tables 1 comment
  2. Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table 1 comment

    • I was hoping they'd have a discussion of the algorithm itself. Quanta is usually good about making these sorts of things approachable. In any case, the full paper is here [1] if you don't want to scroll through the Wired article. [1] https://arxiv.org/abs/2501.02305

      mNovakView on HNParent context

  3. Undergraduate shows that searches within hash tables can be much faster 5 comments

    • This is the correct (2025) paper. https://arxiv.org/abs/2501.02305

      something98View on HNParent context

    • Skimming the paper [1], the key difference they used is that their hash table insertion algorithm will probe further than the first empty slot, instead of greedily filling the first empty slot it finds. They combine this with a clever probing sequence which provably finds empty…

      orlpView on HNParent context

    • That is the paper Krapivin read in ~2023 and inspired him. The actual paper with the breakthrough is from January 2025: https://arxiv.org/abs/2501.02305.

      gieldView on HNParent context

    • This is the actual paper: https://arxiv.org/abs/2501.02305

      sd9View on HNParent context

    • The dereference table allows allocations to fail: https://arxiv.org/pdf/2501.02305#:~:text=If%20both%20buckets... (the text fragment doesn't seem to work in a PDF, it's the 12th page, first paragraph)

      kaathewiseView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.