retagged by
1,196 views
1 votes
1 votes
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?
retagged by

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

 

Related questions

1 votes
1 votes
1 answer
1
s_dr_13 asked Mar 6, 2019
960 views
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful se...
0 votes
0 votes
0 answers
2
Rahul_Rathod_ asked Dec 28, 2018
413 views
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
1 votes
1 votes
0 answers
3
hrcule asked Aug 9, 2018
500 views
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is us...