search
Log In
0 votes
408 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_
Answer 1.647
in DS
edited by
408 views
3
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.
0
why have you considered double hashing formula here? And why not linear probing?
0
This is the formula that is used for open addressing..
1

thanks :)

0

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

0
yes..they should have mentioned which hashing to use
0

http://www.cs.tau.ac.il/~zwick/Adv-Alg-2015/Linear-Probing.pdf

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

0

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

0

thanks @prashant jha 1 @Somoshree Datta 5

most of the questions of test series are incomplete

0

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.😁

0
You are doing calculation mistake

ln(3)= 1.0987..

1.5*1.0987=1.647

1 Answer

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
1 answer
2
1 vote
1 answer
3
344 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 elements, if we used simple uniform hashing?
asked Dec 6, 2016 in DS Vishal Goyal 344 views
...