+28 votes
2.6k views

Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ distinct values are inserted in the table.

1. What is the probability that bucket number $1$ is empty after the $K^{th}$ insertion?
2. What is the probability that no collision has occurred in any of the $K$ insertions?
3. What is the probability that the first collision occurs at the $K^{th}$ insertion?
in DS
edited | 2.6k views
0
c part ?
0
@MiNiPanda

Had it been "Open addressing" only then for part A would it be :

$\frac{n-1}{n}*\frac{n-2}{n-1}*.....*\frac{n-k-1}{n-k}$

?

(as every time we occupy a bucket , the probability will be changed as all slots are equiprobable.)

?

## 3 Answers

+27 votes
Best answer
1. probability that other buckets are selected $= (n-1)/n$
this should happen $k$ times and each of $k$ events are independent so $(n-1)^k/n^k$

2. when $k=1$ prob of no collision $= n/n$
for $k=2$ prob of no collision $= n/n * (n-1)/n$
for $k=k$ prob of no collision $= n/n * (n-1)/n * (n-2)/n ... * (n-k+1)/n$ for $k<=n$
for $k>n$ prob $= 0$

3. prob of collision at $k=1 = (k-1)/n$
prob of collision at $k=2 = n/n * (k-1)/n$
prob of collision at $k=3 = n/n * (n-1)/n * (k-1)/n$
prob of collision at $k=k = n/n * (n-1)/n * (n-2)/n ... * 2/n * (k-1)/n$  for  $k<=n$
for $k>n$  prob $= 1$
by Active (4.1k points)
edited
0

for k=2 prob of no collision = n/n * (n-1)/n

Why is n/n being multiplied?

+1

please xplain part c too

+21
P(Collision at the Kth iteration) = P(No probability till the (K-1)th iteration) * P(Collision at the Kth iteration)

= n/n * (n-1)/n * (n-2)/n ................. (n-(k-2))/n * (k-1)/n
0
@ravi_ssj4

I understood your point. But can't figure out c) in the selected answer. In the selected answer, c) is different.
0
@Habibkhan, here the (c) part as suggested by ravi_ssj4 is correct and not the one in the best answer, right? Please help.
+3

I think c part is:-

n/n * (n-1)/n * (n-2)/n ...  (k-1)/n,

I did not understand how * 2/n  is there in c option?(n/n * (n-1)/n * (n-2)/n ... * 2/n * (k-1)/n for k<=n)

Answer for c part by ravi_ssj4  is also correct

0
Yeah, that's what I said. I think there's an error in the Best Answer. Answer by ravi_ssj4 looks correct not the Best Answer.
0
actually a more general answer for 'c' should be: (n/n) * (n-1)/n * .....* (n-(k-2))/n * (k-1)/n
0
part c is very nicely explain thanks @danish
+1
for partc if k=3 then there will be two possibility of collision (either at the location of first inserted element or at the location of second inserted element ) so for Kth insertion there will be (k-1) positions where collision will be possible so probability will be as specified in best answer
0

For part c) shouldn't this be the answer, Please reply if i am going wrong somewhere,

1) k <= n+1, n/n∗(n−1)/n∗(n−2)/n...∗(n-(k-2))/n∗(k−1)/n

2) k > n+1, 0

because if k > n+1 then the first collision will always happen before the kth insertion. @Danish

+11 votes

We can redefine the above problem using definition of function

we have two set , A={1,2,...k} B={1,2,....n}

Now a hash function maps one element of set A to exactly one element of set B.

Total Mappings=No.of functions from set A to Set B=n^k

1. probability that bucket number 1 is empty after the Kth insertion

Total functions from set A to set B-{1}/All possible functions=(n-1)^k/n^k

2. probability that no collision has occurred in any of the K insertions

Total one-to-one function from set A to set B/All possible functions=P(n,k)/n^k           ,P means permutation

3.probability that the first collision occurs at the Kth insertion

(Total one-to-one function from set A-{k} to set B)*(No of ways kth element can map such that collision occur)/All possible functions=p(n,k-1)*(k-1)/n^k

by Active (4.7k points)
+1 vote
by Active (1.8k points)

+16 votes
3 answers
1
+13 votes
2 answers
2
+14 votes
3 answers
3
+28 votes
4 answers
4
+30 votes
3 answers
5
+23 votes
4 answers
6
+20 votes
2 answers
7