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 journalArticlepeer-review

197 Scopus citations

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 Ω(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
Volume23
Issue number4
DOIs
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