edited by
1,261 views
0 votes
0 votes
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search is_
Answer 1.647
edited by

1 Answer

1 votes
1 votes
Number of probes in unsuccessful search  = $\displaystyle \frac{1}{1-x}$

Number Of Probes in successful search  = $\displaystyle \frac{1}{x } * \ln \displaystyle \frac{1}{1-x}$

where x= load factor of hash table

since, x = $\displaystyle \frac{n}{m }$

Therefore using above formula , x= $\displaystyle \frac{2}{3 }$ , as no. of probes in unsuccessful  search= 3.

Now using x=$\displaystyle \frac{2}{3 }$ ,  no of probes for successful search  = $\displaystyle \frac{3}{2 } * \ln3$ = 1.647

Related questions

0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
Vishal Goyal asked Dec 6, 2016
669 views
Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’. What is the expected number of colliding pairs of element...
0 votes
0 votes
1 answer
4