Optimal Bounds for Open Addressing Without Reordering
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912251445772288 |
|---|---|
| author | Farach-Colton, Martin Krapivin, Andrew Kuszmaul, William |
| author_facet | Farach-Colton, Martin Krapivin, Andrew Kuszmaul, William |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Bounds for Open Addressing Without Reordering Farach-Colton, Martin Krapivin, Andrew Kuszmaul, William Data Structures and Algorithms Combinatorics 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. |
| title | Optimal Bounds for Open Addressing Without Reordering |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2501.02305 |