<p>The best known lower bounds are discussed in <a href="https://dl.acm.org/citation.cfm?id=2447737" rel="nofollow noreferrer">Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"</a>, and none preclude deterministic amortized constant-time operations.</p>

CC BY-SA 4.0
2014-06-07T19:21:48.340Z
2019-11-04T05:20:55.150Z
2019-11-04T05:20:55.150Z
jbapple
<p>There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash table with (possibly amortized) worst-case O(1) lookups, insertions, and deletions?</p>

<p>Thanks!</p>

<ds.data-structures><lower-bounds>
Lower bounds on simple hash table operations?
templatetypedef
# Lower bounds on simple hash table operations?

(Asked by: username_0 on 2014-06-07)

There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash table with (possibly amortized) worst-case O(1) lookups, insertions, and deletions?

Thanks!

**Tags:** ds.data-structures, lower-bounds


---

## 1 answers

### Answer by username_1 on 2014-06-07. Score: 5 | Accepted answer

The best known lower bounds are discussed in [Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems"](https://dl.acm.org/citation.cfm?id=2447737), and none preclude deterministic amortized constant-time operations.


---

