We consider static dictionaries over the universe
![$U=\{0,1\}^w$](Abs/img1.gif)
on a unit-cost RAM with word size
![$w$](Abs/img2.gif)
. 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$](Abs/img3.gif)
elements
runs in time
![$O(n^{1+\epsilon})$](Abs/img4.gif)
for
![$\epsilon >0$](Abs/img5.gif)
. This paper narrows the
gap between deterministic and randomized algorithms exponentially, from the
factor of
![$n^\epsilon$](Abs/img6.gif)
to an
![$O(\log n)$](Abs/img7.gif)
factor. The algorithm is weakly
non-uniform, i.e. requires certain precomputed constants dependent on
![$w$](Abs/img2.gif)
. 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.