Uniform Hashing Is Optimal

Andrew Chi-Chih Yao

Abstract

It was conjectured by J. Ullman that uniform hashing is optimal in its expected retrieval cost among all open-address hashing schemes [4]. In this paper, we show that, for any open-address hashing scheme, the expected cost of retrieving a record from a large table that is α-fraction full is at least (1/α) log (1/(1 - α)) + o(1). This proves Ullman's conjecture to be true in the asymptotic sense.
BibTeX
@article{yao1985uniform,
  author = {Andrew Chi-Chih Yao},
  title = {{Uniform Hashing Is Optimal}},
  journal = {J. ACM},
  year = {1985},
  doi = {10.1145/3828.3836},
}

Loading related content...

Figure