Summary: 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^{1/k})\).