Dynamic Perfect Hashing: Upper and Lower Bounds
Report ID: TR-310-91Author: Dietzfelbinger, Martin / Mehlhorn, Kurt / Rohnert, Hans / Tarjan, Robert E. / Karlin, Anna R. / Meyer auf der Heide, Friedhelm
Date: 1991-03-00
Pages: 37
Download Formats: |PDF|
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 OMEGA(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 $OMEGA (k^cdot^n sup 1/k$).
- This technical report has been published as
- Dynamic Perfect Hashing: Upper and Lower Bounds. Martin
Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn,
Friedhelm Meyer auf der Heide, Hans Rohnert and
Robert E. Tarjan,
- Proc. 29th Annual IEEE Symp. on Foundations of Computer Science (1988), 524-531 and
- SIAM J. Comput. 23 (1994) 738-761.