The Gateway to Computer Science Excellence

+33 votes

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.

- What is the probability that bucket number $1$ is empty after the $K^{th}$ insertion?
- What is the probability that no collision has occurred in any of the $K$ insertions?
- What is the probability that the first collision occurs at the $K^{th}$ insertion?

+30 votes

Best answer

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

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

- 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 ... * (n-k+2)/n * (k-1)/n $ for $k<=n$

for $k>n+1$ prob $= 0$

+24

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

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

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.

+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

+1

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

+13 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

+8 votes

Given that A hash table contains 'n' buckets, Chaining is used to resolve the collisions and Initially Hash table is Empty.

The Probability that a key value is hashed to a particular bucket is $\frac{1}{n}$

we need to insert K distinct values into the hash table.

there are 'n' buckets, named as bucket 1, bucket 2, bucket 3,..... bucket 'n'

A) What is the probability that bucket number 1 is empty after the K$^{th}$ insertion?

after inserting one value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})}$

after inserting second value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1 ( we don't care even it is collision in other bucket ) , So it lead to $\color{red}{(\frac{n-1}{n})}(\frac{n-1}{n})$

after inserting third value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})^2}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^3}$

after inserting K$^{th}$ value, probability that " bucket 1" is empty = $\color{red}{(\frac{n-1}{n})^{(K-1)}}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^K}$

B) What is the probability that no collision has occurred in any of the K insertions?

for inserting one value in to the hash table, we have 'n' buckets ==> map to any bucket = $\color{red}{n}.\frac{1}{n}$

for inserting second value in to the hash table, we have '(n-1)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{red}{(n-1)}\frac{1}{n}$

for inserting third value in to the hash table, we have '(n-2)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{green}{\frac{(n-1)}{n}}.\color{red}{(n-2)}.\frac{1}{n}$

........

for inserting (K-1)$^{th}$ value in to the hash table, we have '(n-(k-2))' buckets due to the previously mapped bucket we can't use =

$\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-3))}{n}}..\color{red}{(n-(K-2))}\frac{1}{n}$

for inserting K$^{th}$ value in to the hash table, we have '(n-(k-1))' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(n-(K-1))}\frac{1}{n}$

Note :-

if K > n, then there should be collision.

C) What is the probability that the first collision occurs at the K$^{th}$ insertion?

so upto K-1 we don't have any collision... and at K$^{th}$ insertion we have to collision.

for collision at K$^{th}$ insertion, we have to choose any (K-1) buckets which are previously mapped.

= $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(K-1)}\frac{1}{n}$

Note :-

if K = n+1, then it must be collision. So K > n+1 can't be the first collision

The Probability that a key value is hashed to a particular bucket is $\frac{1}{n}$

we need to insert K distinct values into the hash table.

there are 'n' buckets, named as bucket 1, bucket 2, bucket 3,..... bucket 'n'

A) What is the probability that bucket number 1 is empty after the K$^{th}$ insertion?

after inserting one value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})}$

after inserting second value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1 ( we don't care even it is collision in other bucket ) , So it lead to $\color{red}{(\frac{n-1}{n})}(\frac{n-1}{n})$

after inserting third value in to the hash table, what is the probability that " bucket 1" is empty ?

there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})^2}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^3}$

after inserting K$^{th}$ value, probability that " bucket 1" is empty = $\color{red}{(\frac{n-1}{n})^{(K-1)}}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^K}$

B) What is the probability that no collision has occurred in any of the K insertions?

for inserting one value in to the hash table, we have 'n' buckets ==> map to any bucket = $\color{red}{n}.\frac{1}{n}$

for inserting second value in to the hash table, we have '(n-1)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{red}{(n-1)}\frac{1}{n}$

for inserting third value in to the hash table, we have '(n-2)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{green}{\frac{(n-1)}{n}}.\color{red}{(n-2)}.\frac{1}{n}$

........

for inserting (K-1)$^{th}$ value in to the hash table, we have '(n-(k-2))' buckets due to the previously mapped bucket we can't use =

$\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-3))}{n}}..\color{red}{(n-(K-2))}\frac{1}{n}$

for inserting K$^{th}$ value in to the hash table, we have '(n-(k-1))' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(n-(K-1))}\frac{1}{n}$

Note :-

if K > n, then there should be collision.

C) What is the probability that the first collision occurs at the K$^{th}$ insertion?

so upto K-1 we don't have any collision... and at K$^{th}$ insertion we have to collision.

for collision at K$^{th}$ insertion, we have to choose any (K-1) buckets which are previously mapped.

= $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(K-1)}\frac{1}{n}$

Note :-

if K = n+1, then it must be collision. So K > n+1 can't be the first collision

+2 votes

For best understanding-

Refer:

https://math.stackexchange.com/questions/601281/question-on-probability-in-hashing

+2 votes

$a)$ $\dfrac{n-1}{n}$

$b)$ $\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}............\times \dfrac{n-(k-1)}{n}$

$c)$ $\underbrace{\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}.....\times \dfrac{n-(k-2)}{n}}\times \underbrace{\dfrac{k-1}{n}}$

$no\ collisions\ till\ (k-1)\ insertions$ $k^{th}\ insertion$

$But\ k^{th}\ insertion\ must\ collide\ with\ any\ one\ of\ those\ (k-1)\ insertions $

$b)$ $\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}............\times \dfrac{n-(k-1)}{n}$

$c)$ $\underbrace{\dfrac{n}{n}\times \dfrac{n-1}{n}\times \dfrac{n-2}{n}.....\times \dfrac{n-(k-2)}{n}}\times \underbrace{\dfrac{k-1}{n}}$

$no\ collisions\ till\ (k-1)\ insertions$ $k^{th}\ insertion$

$But\ k^{th}\ insertion\ must\ collide\ with\ any\ one\ of\ those\ (k-1)\ insertions $

0 votes

As chaining is used to resolve collision

A. The first element can go anywhere except the first block so P(getting into other boxes except first)=n-1/n

Here block A continues to be empty so probability = n-1/n * n-1/n * ......k times = (n-1/n)^k

B. No collision in k insertions so 1st element can go anywhere similarly 2nd can go to any block except the 1st block

so, probability = 1 * n-1/n * n-2/n * ......* n-k+1/n

C. If 1st collision occurs at k th insertion then probability = 1 * n-1/n * n-2/n * ...... * n-k+2/n * k-1/n

A. The first element can go anywhere except the first block so P(getting into other boxes except first)=n-1/n

Here block A continues to be empty so probability = n-1/n * n-1/n * ......k times = (n-1/n)^k

B. No collision in k insertions so 1st element can go anywhere similarly 2nd can go to any block except the 1st block

so, probability = 1 * n-1/n * n-2/n * ......* n-k+1/n

C. If 1st collision occurs at k th insertion then probability = 1 * n-1/n * n-2/n * ...... * n-k+2/n * k-1/n

52,345 questions

60,484 answers

201,816 comments

95,291 users