Faster deterministic dictionaries
Rasmus Pagh · 2000
We consider static dictionaries over the universe U = f0; 1g 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+ ) for > 0. This paper narrows the gap between deterministic and randomized algorithms exponentially, from the factor of n 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-o for dynamic dictionaries, which is optimal for a realistic class of deterministic hashing schemes. 1 Introduction We consider the amount of time needed to deterministically construct a static dictionary, i.e. a data structure for storing any subset S of universe U such that lookups (queries of ...