Implicit $O(1)$ Probe Search

Abstract

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.