TY - JOUR

T1 - Dynamic perfect hashing

T2 - upper and lower bounds

AU - Dietzfelbinger, Martin

AU - Karlin, Anna

AU - Mehlhorn, Kurt

AU - Auf Der Heide, Friedhelm Meyer

AU - Rohnert, Hans

AU - Tarjan, Robert E.

PY - 1994

Y1 - 1994

N2 - 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 Ω(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 Ω(k · n1/k).

AB - 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 Ω(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 Ω(k · n1/k).

UR - http://www.scopus.com/inward/record.url?scp=0028483725&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028483725&partnerID=8YFLogxK

U2 - 10.1137/S0097539791194094

DO - 10.1137/S0097539791194094

M3 - Article

AN - SCOPUS:0028483725

SN - 0097-5397

VL - 23

SP - 738

EP - 761

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -