in Algorithms retagged by
1,179 views
1 vote
1 vote
Suppose that a hash table of m slots contains a single element with key k and the rest of the slots are empty. Suppose further that we search r times in the table for various other keys not equal to k. Assuming simple uniform hashing, what is the probability that one of the r searches probes the slot containing the single element stored in the table?
in Algorithms retagged by
1.2k views

4 Comments

Isnt this the answer for the question: what is the probability that atleast one of the r searches probes the slot containing the single element stored in the table?

But here the question asked exactly one search probes the slot containing the single element, isnt it?
0
0

let take an example , n = 10  , r = 3

key (1) is inserted at one of the 10 bucket = 1/10 

the probability that the each key can go into into (9) slots but not the ist one = 9/10  = 1-1/10

3 searches probes  = (9/10*(9/10)*(9/10)

but in the question they want

the probability that one of the r searches probes the slot containing the single element stored in the table

but here we find that for 3 searches  key will not going to one particular slots

therefore   , 1-  (9/10*(9/10)*(9/10)

 

 

 

 

1
1
1 - P(none of the r searches probes the the slot containing the single element)= P(atleast one of the r searches probes the slot containing the single element)

Isnt this true?
0
0

2 Answers

0 votes
0 votes
The question says that when "r" number of searches are performed, each time a key value which is not equal to "k" is searched in the hash table. And since there is only one solitary element in the hash table, all the other slots for key values other than "k" are empty, so there is no need to ever probe into the slot with key value "k".

Hence the probability should be 0.

1 comment

mesut ozil

tumko kya hua hey bhai ??

1
1
0 votes
0 votes

 

they give the condition that one of the r searches probes(colllides)slot containing single element stored in table.they dont give as such exactly one among r searches probes(collides).means even if more than one searches probes(collides) slot.then also the condition is satisfied. the probability should be

$\sum(k=1 to r)\binom{r}{k}.(1/m)^{k}.(1-1/m)^{k}=1-\binom{r}{0}.(1/m)^{0}.(1-1/m)^r=1-(1-1/m)^r$ 

they do not give any tight condition such as exactly.therfore answer should be the above.