2
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

The best known lower bounds are discussed in Thorup's "Mihai Pǎtraşcu: Obituary and Open Problems", and none preclude deterministic amortized constant-time operations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.