ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Minimean optimal key arrangements in hash tables (1995)

Yao, A. C. -C.

Springer

Algorithmica 14 (1995), S. 409-428

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: Assignment problem ; Double hashing ; Hash tables ; Key arrangement ; Retrieval

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract For an open-addressing hash functionh and a setA ofn keys, letCh(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 largen, whenh 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 randomA.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01192048

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit