arXiv:2611.04186 · v1

Incremental Open Addressing Has No Time-Space Tradeoff

首次提交 2026-11-03 10:22

版本更新 2026-11-03 10:22

雷达观测 2026-11-04 23:40

摘要

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.

作者备注：46 pages, 4 figures, 1 table