The Spatial Complexity of Oblivious <i>k</i>-Probe Hash Functions

Abstract

The problem of constructing a dense static hash-based lookup table T for a set of n elements belonging to a universe $U = \{ 0, 1, 2,\cdots , m -1 \}$ is considered. Nearly tight bounds on the spatial complexity of oblivious $O(1)$-probe hash functions, which are defined to depend solely on their search key argument, are provided. This establishes a significant gap between oblivious and nonoblivious search. In particular, the results include the following: • A lower bound showing that oblivious k-probe hash functions require a program size of $\Omega(({n / k}^{2})e^{-k}+\log \log m)$ bits, on average. • A probabilistic construction of a family of oblivious k-probe hash functions that can be specified in $O(n e^{-k} +\log \log m)$ bits, which nearly matches the above lower bound. • A variation of an explicit $O(1)$ time 1-probe (perfect) hash function family that can be specified in $O(n+\log \log m)$ bits, which is tight to within a constant factor of the lower bound.