in Algorithms
261 views
0 votes
0 votes
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is $3/4$ and when it is $7/8$.
in Algorithms
261 views

1 Answer

1 vote
1 vote

 the expected number of probes in an unsuccessful search is at most 1/(1 - alpha)

where ɑ = load factor

also 
Given an open-address hash table with load factor  < 1, the expected number of probes in a successful search is at most

$1/\alpha \ln (1/1-\alpha )+1/\alpha$

when load factor is ¾ hence for 1st case max probe is = $1/1-3/4 = 4$ for unsuccessful

and for successful = $4/3\\ln (4) + 4/3 = 3.18 approx$

calculate for 2nd part similarly

reference: Intro to Algorithms: CHAPTER 12: HASH TABLES (ustc.edu.cn)

 

Related questions