edited by
873 views
1 votes
1 votes

Consider the hashing table with  ‘m’ slots and ‘n’ keys. If the expected number of probes in an unsuccessful search is 3, the expected number of probes in successful search is _____(Up to 2 decimals)

Ans. 1.647

Here by default which hashing should be considered? Linear or Double?

They have solved considering Double hashing with the formula given here in the table

http://cs360.cs.ua.edu/notes/hashing_formulas.pdf

With linear hashing, I am getting around 1.61

 

edited by

1 Answer

0 votes
0 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
1
Ram Swaroop asked Jan 27, 2019
1,261 views
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...
0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4
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...