# MadeEasy Test Series: Programming & DS - Hashing

317 views

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
0
PLSS EXPLAIN THESE CASES THEORETICALLY IF POSSIBLE BOTH OF THEM
0
I'm getting 1.64 using double hashing.is there is any case in which we select either linear/double hashing????
0

plzz explain the concept of  both linear and double if possible

0

@Hira Thakur

I don't know how to know when to use the linear and double hashing formula.. :P :/

1
By default most of the times linear only ( in GATE they should mention which method they are following ), i seen alot of questions from Madeeasy are ambiguous, and they ask something in question but the solution has something else.

@mini and @hira did you applyling the formula or something else to find answer for this question ?

i didn't understood how that formula derived can you elaborate ?
0

@Shaik Masthan

I searched for the derivation of these formulae in many places but couldn't get a good one.. In one of the places it was written that the derivation is tough so they didn't do it..

0
ok
0

so we have to remember them ......

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

1
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