You are not logged in to this journal. Log in

Given a set of $n$ elements from the domain $\{ {1, \cdots ,m} \}$, this paper investigates how to arrange them in a table of size $n$, so that searching for an element in the table can be done in constant time. Yao [J. Assoc. Comput. Mach., 28(1981), pp. 615–628] has shown that this cannot be done when the domain is sufficiently large as a function of $n$.This paper gives a constructive solution when the domain $m$ is polynomial in $n$, the number of elements, as well as a nonconstructive proof for $m$ no larger than exponential in ${\operatorname{poly}}(n)$. The authors improve upon a result of Yao and give better bounds on the maximum $m$ for which implicit $O(1)$ probe search can be done. The results are achieved by showing the tight relationship between hashing and certain encoding problems called rainbows. ©1993 Society for Industrial and Applied Mathematics