betaFeedback

WorksComputer Science

Incremental Open Addressing Has No Time-Space Tradeoff

Abstract

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)O(1) worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor 11). 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)O(1) amortized expected positive query time together with O(1)O(1) worst-case expected insertion time, a combination that was not previously known to be possible.

Paper details

vlnc:W_wjjtd4mq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…