0 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

0

I'm getting 1.64 using double hashing.is there is any case in which we select either linear/double hashing????

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 ?

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

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