927 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 is_

moved
Expected number of probes in open addressing in case of an unsuccessful search = 1/(1-$\alpha$) , where $\alpha$ denotes the load factor i.e. n/m.

So 1/(1-$\alpha$) = 3

Hence, $\alpha$ = 2/3

Now, Expected number of probes in open addressing in case of an successful search = (1/$\alpha$)*ln(1/(1-$\alpha$))

Putting $\alpha$=2/3 in the above formula, we get the expected probes for successful search as 1.647.
why have you considered double hashing formula here? And why not linear probing?
This is the formula that is used for open addressing..

thanks :)

Now I think this question is incomplete , right @Somoshree Datta 5

yes..they should have mentioned which hashing to use

visit this link..they have given this formula for uniform probing, not double hashing..

http://web.ist.utl.pt/fabio.ferreira/material/asa/clrs.pdf

Visit page 210 of CLRS..here also they gave this formula for open addressing..

most of the questions of test series are incomplete I followed the same path using the same logic. Please explain, why am I getting different answer.I  ain't getting 1.647.

1.5*ln(3)=1.098. Please someone explain. Silly thing though.😁  You are doing calculation mistake

ln(3)= 1.0987..

1.5*1.0987=1.647

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

1
380 views