### Abstract

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 · n^{1/k}).

Original language | English (US) |
---|---|

Pages (from-to) | 738-761 |

Number of pages | 24 |

Journal | SIAM Journal on Computing |

Volume | 23 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 1994 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Dynamic perfect hashing: upper and lower bounds'. Together they form a unique fingerprint.

## Cite this

*SIAM Journal on Computing*,

*23*(4), 738-761. https://doi.org/10.1137/S0097539791194094