GATE CSE 1997 | Question: 12

Question

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.

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

Comments

c part ?

---

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

 

?

---

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

Answer 1

For best understanding-

Refer:

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

Answer 2

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