446 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$.

1 Answer

2 votes
2 votes

 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

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Apr 4, 2019
233 views
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
0 votes
0 votes
0 answers
4