Dynamic perfect hashing: Upper and lower bounds

M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

77 Scopus citations


A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Ω(log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Ω(kn1/ k).

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Number of pages8
ISBN (Print)0818608773, 9780818608773
StatePublished - 1988
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


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

Cite this