Dynamic perfect hashing: Upper and lower bounds

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

doi:10.1109/sfcs.1988.21968

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 proceeding › Conference contribution

78 Scopus citations

Abstract

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 Ω(kn^{1/ k}).

Original language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	Publ by IEEE
Pages	524-531
Number of pages	8
ISBN (Print)	0818608773, 9780818608773
DOIs	https://doi.org/10.1109/sfcs.1988.21968
State	Published - 1988
Externally published	Yes

Publication series

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

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/sfcs.1988.21968

Cite this

@inproceedings{d75e037264eb4e55a70fdc0ab4c6a13f,

title = "Dynamic perfect hashing: Upper and lower bounds",

abstract = "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).",

author = "M. Dietzfelbinger and A. Karlin and K. Mehlhorn and {auf der Heide}, {F. Meyer} and H. Rohnert and Tarjan, {R. E.}",

year = "1988",

doi = "10.1109/sfcs.1988.21968",

language = "English (US)",

isbn = "0818608773",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "Publ by IEEE",

pages = "524--531",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - Dynamic perfect hashing

T2 - Upper and lower bounds

AU - Dietzfelbinger, M.

AU - Karlin, A.

AU - Mehlhorn, K.

AU - auf der Heide, F. Meyer

AU - Rohnert, H.

AU - Tarjan, R. E.

PY - 1988

Y1 - 1988

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0024128562&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024128562&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1988.21968

DO - 10.1109/sfcs.1988.21968

M3 - Conference contribution

AN - SCOPUS:0024128562

SN - 0818608773

SN - 9780818608773

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 524

EP - 531

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

ER -

Dynamic perfect hashing: Upper and lower bounds

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this