Data structure: hashing

Question

A hash table has spaces for 50 records. Then the probability of collision before the table is 10% full is_______.

10% of 50 = 5, so we need to find the probability of collision before we insert 5 slots.
*When hash table empty, prob. of collision = 0
*When the hash table has 1 slot filled, prob. of collision = 1/50(2% full)
*When the hash table has 2 slots filled, prob. of collision = 2/50(4% full)
*When the hash table has 3 slots filled, prob. of collision = 3/50(6% full)
*When the hash table has 4 slots filled, prob. of collision = 4/50(8% full)

Final probability = 1/50 + 2/50 + 3/50 + 4/50 = ((4/2)(1+4))/50 = 10/50 = 20/100 = 0.2

If no. of slots  = 100 then probability = 0.45
If no. of slots  = 200 then probability = 0.95     

Why probability of collision is increasing very rapidly? Please give a detailed explanation.

Comments

Probability of collision in $1^{st}$ insertion $= 0$

Probability of collision in $2^{nd}$ insertion $= \frac{1}{50}$

Probability of collision in $3^{rd}$ insertion $= \frac{49}{50} * \frac{2}{50}$

Probability of collision in $4^{th}$ insertion $ = \frac{49}{50} * \frac{48}{50} * \frac{3}{50}$

Probability of collision in $5^{th}$ insertion $= \frac{49}{50} * \frac{48}{50} * \frac{47}{50} * \frac{4}{50}$

Now, adding all these, we get $\text{Required Probability} = 0.1864$

---

@shi197 .. can you please explain why we have multiplied by 49/50

---

Let's take an example, suppose we want to find probability of collision in first $3$ insertions.

Lets say size of hashtable is $10$.

Only the following cases are possible,

$(n_1,n_2,n_3), (n_1,n_2,c_3),(n_1,c_2,n_3),(n_1,c_2,c_3)$

Where $n_i$ and $c_i$ denotes the case of no collision and collision, respectively, in inserting $i^{th}$ item.

$P(n_1,n_2,c_3) = 1*  \frac{9}{10} * \frac{2}{10}$

$P(n_1,c_2,n_3) + P(n_1,c_2,c_3) = P(n_1,c_2) = 1 * \frac{1}{10}$

And $(n_1,n_2,n_3)$ is not a favourable outcome.

Answer 1

This is not correct way of finding the probabilities.

If you follow this method, then probability of collision before the hash table is $10$% full when size of hash table is $500$ comes out to be $2.45$, which is absurd.

Now coming back to the question,

Size of hash table $= 50$

$10$% of $50 = 5$

We've to find probability of collision in first $5$ insertions which is equal to $1 - \text{ probability}$ of no collision in first $5$ insertions.

$\text{Required Probability} = 1 - \frac{50}{50} * \frac{49}{50} * \frac{48}{50} * \frac{47}{50} * \frac{46}{50} = 0.1864$

And the probability for same problem when size is $100$ and $200$ comes out to be $0.3718$ and $0.6256$ respectively.