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 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 $...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1994-08, Vol.23 (4), p.738-761
Main Authors: DIETZFELBINGER, M, KARLIN, A, MEHLHORN, K, MEYER AUF DER HEIDE, F, ROHNERT, H, TARJAN, R. E
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer science
control theory
systems
Data processing. List processing. Character string processing
Dictionaries
Exact sciences and technology
Grants
Memory organisation. Data processing
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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}} )$.
ISSN:0097-5397
1095-7111
DOI:10.1137/s0097539791194094