Report Number: CS-TR-85-1038
Institution: Stanford University, Department of Computer Science
Title: Uniform hashing is optimal
Author: Yao, Andrew C.
Date: January 1985
Abstract: It was conjectured by J. Ullman that uniform hashing is optimal in its expected retrieval cost among all open-address hashing schemes (JACM 19 (1972), 569-575). In this paper we show that, for any open-address hashing scheme, the expected cost of retrieving a record from a large table which is alpha-fraction full is at least 1/alpha log 1/1-alpha + o(1). This proves Ullman's conjecture to be true in the asymptotic sense.
http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1038/CS-TR-85-1038.pdf