Metraipolis › archive › dc_a78038843136

Incremental Open Addressing Has No Time-Space Tradeoff — arXiv:2611.04186

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04186
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:27.793Z
SHA-256 of the archived text
5c2c19546fbc735c5eeae184b0ca9edc2931b54fe8bc842f991d851c00e5d17a
Stable URL of this page
https://metraipolis.com/documento/dc_a78038843136

How to cite

Incremental Open Addressing Has No Time-Space Tradeoff — arXiv:2611.04186 — arXiv (en), https://arxiv.org/abs/2611.04186 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a78038843136 (Metraipolis archive dc_a78038843136, sha256 5c2c19546fbc735c5eeae184b0ca9edc2931b54fe8bc842f991d851c00e5d17a)
BibTeX
@misc{dca78038843136,
  title = {Incremental Open Addressing Has No Time-Space Tradeoff — arXiv:2611.04186},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04186},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a78038843136; sha256 5c2c19546fbc735c5eeae184b0ca9edc2931b54fe8bc842f991d851c00e5d17a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04186. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports $O(1)$ worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor $1$). As an intermediate result, we also revisit the problem of constructing an incremental open-addressed hash table that does not perform reordering (does not move elements around over time). In this setting, we show that it is possible to get $O(1)$ amortized expected positive query time together with $O(1)$ worst-case expected insertion time, a combination that was not previously known to be possible.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04186 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.428Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).