Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-310-91

Authors:

Dietzfelbinger, Martin [1] / Karlin, Anna R. [2] / Mehlhorn, Kurt [3] / Meyer auf der Heide, Friedhelm [4] / Rohnert, Hans [5] / Tarjan, Robert E. [6]

Date:

February 1991

Pages:

37

Download Formats:

[PDF [7]]

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: arandomized

algorithm for the dynamic dictionary problem that takesO(1)

worst-case time for lookups andO(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 ofdeterministicalgorithms for the dictionary problem are

proved. This class encompasses realistic hashing-based schemes that

use linear space. Such algorithms have amortized worst-case time

complexityOMEGA(logn) for a sequence ofninsertions and

lookups; if the worst-case lookup time is restricted tokthen 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

ScienceSIAM J. Comput.23(1994) 738-761.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/33

[2] http://www.cs.princeton.edu/research/techreps/author/428

[3] http://www.cs.princeton.edu/research/techreps/author/136

[4] http://www.cs.princeton.edu/research/techreps/author/443

[5] http://www.cs.princeton.edu/research/techreps/author/177

[6] http://www.cs.princeton.edu/research/techreps/author/384

[7] ftp://ftp.cs.princeton.edu/techreports/1991/310.pdf