Dynamic perfect hashing: upper and lower bounds

Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, Robert Endre Tarjan

Research output: Contribution to journalArticle

196 Scopus citations


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 Ω(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 Ω(k · n1/k).

Original languageEnglish (US)
Pages (from-to)738-761
Number of pages24
JournalSIAM Journal on Computing
Issue number4
StatePublished - Jan 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Dynamic perfect hashing: upper and lower bounds'. Together they form a unique fingerprint.

  • Cite this

    Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Auf Der Heide, F. M., Rohnert, H., & Tarjan, R. E. (1994). Dynamic perfect hashing: upper and lower bounds. SIAM Journal on Computing, 23(4), 738-761. https://doi.org/10.1137/S0097539791194094