# Item

ITEM ACTIONSEXPORT

Released

Other

#### Dynamic Perfect Hashing: Upper and Lower Bounds

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer Auf Der Heide, F., Rohnert, H., & Tarjan, R. E. (1991).
*Dynamic Perfect Hashing: Upper and Lower Bounds*.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AE33-0

##### Abstract

The dynamic dictionary problem is considered: provide an algorithm for storing
a dynamic set, allowing the operations insert, delete, and lookup. A dynamic
perfect hashing strategy is given: a randomized algorithm for the dynamic
dictionary problem that takes O(1) worst-case time for lookups and O(1)
amortized expected time for insertions and deletions; it uses space
proportional to the size of the set stored. Furthermore, lower bounds for the
time complexity of a class of deterministic algorithms for the dictionary
problem are proved. This class encompasses realistic hashing-based schemes that
use linear space. Such algorithms have amortized worst-case time complexity
OMEGA(log n) for a sequence of n insertions and lookups; if the worst-case
lookup time is restricted to k then the lower bound becomes $OMEGA (k^cdot^n
sup 1/k$).