Dynamic perfect hashing: upper and lower bounds
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 524-531
- https://doi.org/10.1109/sfcs.1988.21968
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 Omega (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 Omega (kn/sup 1/k/).Keywords
This publication has 2 references indexed in Scilit:
- Storing a dynamic sparse tablePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984