4,981 views
7 votes
7 votes
Consider a hash table with $N$ slots. It is given that the collision resolution technique used in chaining. Assume simple uniform hashing, what is the probability that the last $k$ slots are unfilled after the first $’r’$ insertions?

$A)\left ( 1-\frac{N}{k} \right )^{r}$

$B)\left ( 1-\frac{k}{N} \right )^{r}$

$C)\left ( 1+\frac{N}{k} \right )^{r-1}$

$D)\left ( 1-\frac{k}{N} \right )^{r-1}$

4 Answers

1 votes
1 votes

Here, We are using chaining as a resolution technique so if a collision happens at some place then we will get an extra bucket at that place.

Now here in question, we have N slots and we don't want any insertion in the last K slots, so remaining slots where we can insert value is N-K slots.

First Insertion :

The probability that the first insertion done at N-K slots is, (N-K/N)

 

Second Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) = (N-K/N)^2

 

Third Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N)  * (N-K/N)= (N-K/N)^3

 

so for, rth Insertion :

The probability that the second insertion also done at N-K slots is, (N-K/N) * (N-K/N) * ...... r times= (N-K/N)^r

 

So answer is (N-K/N)^r which is nothing but (1-(K/N))^r Option B

0 votes
0 votes
Option b. Since chaining is used

For 1st insertion  :(N-k) slots will be used  for insertion only  as k  slot to be left unfilled

Similarly for 2nd and 3rd insertion because here in chaining we can use same slot again and again according to hash function there is not chance of collision so (N-k) slot for 2nd 3rd insertion too

Total no of possibility for r insertion =N^r

Therefore probability =(N-k) ^r/N^r
edited by
0 votes
0 votes

Let N=6 , k=2 and r =4;

           

                                                                                            <---------------- k ---------------->

<----------------------------------------------------  N  ---------------------------------------------------->

First insertion :

probability that the last k slot unfilled = 4/6;

Second insertion :

probability that the last k slot unfilled = 4/6*4/6;        [ Since collision resolution is done using chaining]

third insertion:

probability that the last k slot unfilled = 4/6*4/6*4/6;

fourth insertion 

probability that the last k slot unfilled = 4/6*4/6*4/6*4/6;

i.e. probability that the last k slot unfilled after 4th insertion is = (4/6)^4;

     probability that the last k slot unfilled after rth insertion is = (N-k/N)^r;

                                                                                                         = (1 - k/N )^r;

Option B

 

0 votes
0 votes
There are n slots,After r insertion k slots are unfilled ,

for first insertion , i have (n-k)/n options

for second insertion,i have (n-k)/n options because we use chaining for collision resolution

same as for 3,4,5 upto r insertions

so that ((n-k)/n)^r

Ans  B

Related questions

0 votes
0 votes
1 answer
1
tishhaagrawal asked Dec 16, 2023
313 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
0 votes
0 votes
0 answers
3
Desert_Warrior asked Mar 11, 2016
720 views
Consider a hash table with 'm' slots that uses chaining for collision resolution. the table is initially empty. What is probability that after 4 keys are inserted then at...