Report Number: CS-TR-79-753
Institution: Stanford University, Department of Computer Science
Title: Should tables by sorted?
Author: Yao, Andrew Chi-Chih
Date: July 1979
Abstract: We examine optimality questions in the following information retrieval problem: Given a set S of n keys, store them so that queries of the form "Is x $\in$ S?" can be answered quickly. It is shown that, in a rather general model including al1 the commonly-used schemes, $\lceil$ lg(n+l) $\rceil$ probes to the table are needed in the worst case, provided the key space is sufficiently large. The effects of smaller key space and arbitrary encoding are also explored.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/753/CS-TR-79-753.pdf