Optimal Bounds for Open Addressing Without Reordering
2025/01/04 by Martı́n Farach-Colton, Martin Farach-Colton, Andrew Krapivin +4 · 17 voices · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.2501.02305
openalex publication_date 2025/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.
Cited by
Discussions
- "In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table [...] Along the way, we disprove the central conjecture lef [bsky, 19 points, 0 comments]
- Better performance bounds on search in an open addressing hash table, O(log(n)^2)
(I would put !!! But it might be misinterpreted)
Paper
arxiv.org/abs/2501.02305
Write up
www.quantamagazine.org/under [bsky, 12 points, 1 comments]
- Optimal Bounds for Open Addressing Without Reordering [lobsters, 5 points, 5 comments]
- Orig paper posted 2025 Jan 4. Next I need to go hunting for implementations
arxiv.org/abs/2501.02305 [bsky, 4 points, 1 comments]
- Optimal bounds for open addressed hash tables without reordering [hn, 4 points, 0 comments]
- Is anyone aware of implementations of the Tiny Pointers / Krapivin hash table from arxiv.org/abs/2501.02305? Specifically, I'm interested in if the optimal bounds enable performance improvements in th [bsky, 3 points, 0 comments]
- Optimal Bounds for Open Addressing Without Reordering [hn, 3 points, 0 comments]
- The videos from this "Turing" channel seem to be AI generated (or similar), so here's an actual paper: arxiv.org/pdf/2501.02305 [bsky, 2 points, 0 comments]
- arxiv.org/abs/2501.02305 [bsky, 1 points, 0 comments]
- oWo new class of hash tables dropped arxiv.org/abs/2501.02305 [bsky, 0 points, 0 comments]
- arxiv.org/abs/2501.023... [bsky, 0 points, 0 comments]
- For the super curious, here is the new paper: arxiv.org/abs/2501.02305 [bsky, 0 points, 0 comments]
- arxiv.org/pdf/2501.02305 [bsky, 0 points, 0 comments]
- Paper: arxiv.org/abs/2501.02305 [bsky, 0 points, 0 comments]
- Optimal Bounds for Open Addressing Without Reordering https://lobste.rs/s/tb9lr7 #plt [bsky, 0 points, 0 comments]
- "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 prev [bsky, 0 points, 0 comments]
- Holy shit this is dope. arxiv.org/abs/2501.02305 [bsky, 0 points, 0 comments]
Related