The Gateway to Computer Science Excellence
0 votes
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 by Loyal (5.4k points)
edited by | 238 views
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..


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


thanks @prashant jha 1 @Somoshree Datta 5

most of the questions of test series are incomplete

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,141 users