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.