Minimean optimal key arrangements in hash tables

A. C.C. Yao

doi:10.1007/BF01192048

Minimean optimal key arrangements in hash tables

A. C.C. Yao

Faculty of Electronic and Information Engineering

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

Abstract

For an open-addressing hash function h and a set A of n keys, let Ch(A) be the expected retrieval cost when the keys are arranged to minimize the expected retrieval cost in a full table. It is shown that, asymptotically for large n, when h satisfies a certain doubly dispersive property, as is the case for double hashing, C_h(A)=0(1) with probability 1 - 0(1) for a random A.

Original language	English
Pages (from-to)	409-428
Number of pages	20
Journal	Algorithmica (New York)
Volume	14
Issue number	5
DOIs	https://doi.org/10.1007/BF01192048
State	Published - Nov 1995

Keywords

Assignment problem
Double hashing
Hash tables
Key arrangement
Retrieval

Access to Document

10.1007/BF01192048

Cite this

@article{9d12cc85b08d4d2e84ba3170ed2e59fd,

title = "Minimean optimal key arrangements in hash tables",

abstract = "For an open-addressing hash function h and a set A of n keys, let Ch(A) be the expected retrieval cost when the keys are arranged to minimize the expected retrieval cost in a full table. It is shown that, asymptotically for large n, when h satisfies a certain doubly dispersive property, as is the case for double hashing, Ch(A)=0(1) with probability 1 - 0(1) for a random A.",

keywords = "Assignment problem, Double hashing, Hash tables, Key arrangement, Retrieval",

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

year = "1995",

month = nov,

doi = "10.1007/BF01192048",

language = "英语",

volume = "14",

pages = "409--428",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "5",

}

TY - JOUR

T1 - Minimean optimal key arrangements in hash tables

AU - Yao, A. C.C.

PY - 1995/11

Y1 - 1995/11

N2 - For an open-addressing hash function h and a set A of n keys, let Ch(A) be the expected retrieval cost when the keys are arranged to minimize the expected retrieval cost in a full table. It is shown that, asymptotically for large n, when h satisfies a certain doubly dispersive property, as is the case for double hashing, Ch(A)=0(1) with probability 1 - 0(1) for a random A.

AB - For an open-addressing hash function h and a set A of n keys, let Ch(A) be the expected retrieval cost when the keys are arranged to minimize the expected retrieval cost in a full table. It is shown that, asymptotically for large n, when h satisfies a certain doubly dispersive property, as is the case for double hashing, Ch(A)=0(1) with probability 1 - 0(1) for a random A.

KW - Assignment problem

KW - Double hashing

KW - Hash tables

KW - Key arrangement

KW - Retrieval

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

U2 - 10.1007/BF01192048

DO - 10.1007/BF01192048

M3 - 文章

AN - SCOPUS:34249754372

SN - 0178-4617

VL - 14

SP - 409

EP - 428

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 5

ER -

Minimean optimal key arrangements in hash tables

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this