Incremental Open Addressing Has No Time-Space Tradeoff

We give an incremental open-addressed hash table with constant worst-case expected time for insertions and positive and negative queries at every load factor, including one. We also obtain new insertion and query bounds for incremental open addressing without reordering.