Uniform Hashing is Optimal

Andrew C. Yao

doi:10.1145/3828.3836

Uniform Hashing is Optimal

Andrew C. Yao

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

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.

Original language	English
Pages (from-to)	687-693
Number of pages	7
Journal	Journal of the ACM (JACM)
Volume	32
Issue number	3
DOIs	https://doi.org/10.1145/3828.3836
State	Published - 1 Jul 1985

Access to Document

10.1145/3828.3836

Cite this

@article{f5c350a993aa44e09b432630579a5713,

title = "Uniform Hashing is Optimal",

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.",

author = "Yao, \{Andrew C.\}",

year = "1985",

month = jul,

day = "1",

doi = "10.1145/3828.3836",

language = "英语",

volume = "32",

pages = "687--693",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery ",

number = "3",

}

TY - JOUR

T1 - Uniform Hashing is Optimal

AU - Yao, Andrew C.

PY - 1985/7/1

Y1 - 1985/7/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0022092527

U2 - 10.1145/3828.3836

DO - 10.1145/3828.3836

M3 - 文章

AN - SCOPUS:0022092527

SN - 0004-5411

VL - 32

SP - 687

EP - 693

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Uniform Hashing is Optimal

Abstract

Access to Document

Other files and links

Fingerprint

Cite this