Faster Deterministic Dictionaries

Rasmus Pagh

December 1999

Abstract:

We consider static dictionaries over the universe $U=\{0,1\}^w$ on a unit-cost RAM with word size $w$. Construction of a static dictionary with linear space consumption and constant lookup time can be done in linear expected time by a randomized algorithm. In contrast, the best previous deterministic algorithm for constructing such a dictionary with $n$ elements runs in time $O(n^{1+\epsilon})$ for $\epsilon >0$. This paper narrows the gap between deterministic and randomized algorithms exponentially, from the factor of $n^\epsilon$ to an $O(\log n)$ factor. The algorithm is weakly non-uniform, i.e. requires certain precomputed constants dependent on $w$. A by-product of the result is a lookup time vs insertion time trade-off for dynamic dictionaries, which is optimal for a realistic class of deterministic hashing schemes.

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.