Quick links

Dynamic Perfect Hashing: Upper and Lower Bounds

Report ID:
February 1991
Download Formats:


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
    (1988), 524-531 and
  • SIAM J. Comput. 23 (1994) 738-761.
  • Follow us: Facebook Twitter Linkedin