DYNAMIC PERFECT HASHING - UPPER AND LOWER BOUNDS

The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lo okup. A dynamic perfect hashing strategy is given: a randomized algori thm for the dynamic dictionary problem that takes O(1) worst-case time for lookups and O(1) amortized expected time for insertions and delet ions; it uses space proportional to the size of the set stored. Furthe rmore, lower bounds for the time complexity of a class of deterministi c algorithms for the dictionary problem are proved. This class encompa sses realistic hashing-based schemes that use linear space. Such algor ithms have amortized worst-case time complexity OMEGA (log n) for a se quence of n insertions and lookups; if the worst-case lookup time is r estricted to k, then the lower bound becomes OMEGA(k . n1/k).