TY - JOUR AU - Pagh, Rasmus PY - 1999/12/18 Y2 - 2024/03/28 TI - Faster Deterministic Dictionaries JF - BRICS Report Series JA - BRICS VL - 6 IS - 48 SE - Articles DO - 10.7146/brics.v6i48.20118 UR - https://tidsskrift.dk/brics/article/view/20118 SP - AB - We consider static dictionaries over the universe U = {0, 1}^w on a<br />unit-cost RAM with word size w. Construction of a static dictionary with<br />linear space consumption and constant lookup time can be done in linear<br />expected time by a randomized algorithm. In contrast, the best previous<br />deterministic algorithm for constructing such a dictionary with n elements<br />runs in time O(n^(1+epsilon)) for epsilon > 0. This paper narrows the gap between<br />deterministic and randomized algorithms exponentially, from the factor of<br />n^epsilon to an O(log n) factor. The algorithm is weakly non-uniform, i.e. requires<br />certain precomputed constants dependent on w. A by-product of the result<br />is a lookup time vs insertion time trade-off for dynamic dictionaries, which<br />is optimal for a certain class of deterministic hashing schemes. ER -