Tight Bounds for Classical Open Addressing
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913504566444032 |
|---|---|
| author | Bender, Michael A. Kuszmaul, William Zhou, Renfei |
| author_facet | Bender, Michael A. Kuszmaul, William Zhou, Renfei |
| contents | We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to $1 - \varepsilon$, while also supporting $O(1)$ expected-time queries, and $O(\log \log \varepsilon^{-1})$ expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor $1 - \varepsilon$ must incur $Ω(\log \log \varepsilon^{-1})$ expected time per operation.
Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost -- even while maintaining a load factor of $\ge 1 - \varepsilon$ at all times, we can support $O(1)$ queries and $O(\log \log \varepsilon^{-1})$ updates.
Prior to our work, achieving any time bounds of the form $o(\varepsilon^{-1})$ for all of insertions, deletions, and queries simultaneously remained an open question. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11280 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Classical Open Addressing Bender, Michael A. Kuszmaul, William Zhou, Renfei Data Structures and Algorithms We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to $1 - \varepsilon$, while also supporting $O(1)$ expected-time queries, and $O(\log \log \varepsilon^{-1})$ expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor $1 - \varepsilon$ must incur $Ω(\log \log \varepsilon^{-1})$ expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost -- even while maintaining a load factor of $\ge 1 - \varepsilon$ at all times, we can support $O(1)$ queries and $O(\log \log \varepsilon^{-1})$ updates. Prior to our work, achieving any time bounds of the form $o(\varepsilon^{-1})$ for all of insertions, deletions, and queries simultaneously remained an open question. |
| title | Tight Bounds for Classical Open Addressing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.11280 |