search
Log In
0 votes
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

 

in Programming
edited by
317 views
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 ......

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