Hash table

Question

A Hash table has space for 100 records. Then the probability of collision before the table is 10% full is?

A 0.45
B 0.5
C 0.3
D 0.34 (approximately)

Comments

Sir,
For the first time there will be no collision because all the slot is empty.
Now, once the first slot is filled, after then to fill the next key in the slot there is chances of collision by 1/100.
For the next key, 2/100.
So 1/100 + 2/100+.............+9/100.
= .01+.02+.03+.......+.08+.09= .45

---

a?....

---

answer is a.

---

i think it should be 0.45

Answer 1

Table has 100 slots. So, for 10% filling it must take 10 slots. Now, the question is like this- collision before 10% full. This should mean the first collision happened before the 10th entry is made. So, the first collision can happen from 2nd entry (for 1st entry there won't be a collision) to 10th entry. So required probability

$ = \frac{100.1}{100^2} + \frac{100.99.2}{100^3} + \frac{100.99.98.3}{100^4} + \dots + \frac{100.99.98\dots 92.9}{100^{10}}\\ \approx 0.37$

---

Can also be found as 1 - Probability of no collision for first 10 entries.

$ = 1 - \frac{100.99.98.97.96.95.94.93.92.91}{100^{10}} \approx 0.37$

Comments

@Arjun sir, can you please show the probability for filling 100 items into the 100 slots with no collisions?  I tried using $1-\frac{100!}{100^{100}}$ but it doesn't look right.

---

sir it is said that collision before 10 th entry so why we are including 10th entry that is 91/100 im not getting it please help ?

---

@Arjun sir, i need to ask you what’s wrong with the approach 1/100 + 2/100 + 3/100…… because your solution 100/100^2 + 100*99*2/100^3 …….…...suggests that there will be a collision at any one of the entries, be it at first, second, third or anyone else, but the second approach of yours (1 – (100*99*98*97…./100^10)) suggests that there can be collision at anytime, in any possible scenario.

Answer 2

When hash table is empty, there is no collision

When in hash table 1 slot is full collision=$\frac{1}{100}$

When in hash table 2 slot is full collision=$\frac{2}{100}$

......................................

When in hash table 9 th slot is full collision=$\frac{9}{100}$

So, before the hash table 10% full the probability of collision is =$\frac{1}{100}+\frac{2}{100}+.........\frac{9}{100}=\frac{45}{100}$

Answer 3

To find the probability of collision for the first 10 records, we need to sum up the individual probabilities of collision for each record.

P(collision for first 10 records) = P(collision for first record) + P(collision for second record) + ... + P(collision for tenth record)

P(collision for first 10 records) = 0 + 1/100 + 2/100 + ... + 9/100

This can be simplified as: P(collision for first 10 records) = (1/100)(1 + 2 + 3 + ... + 9)

The sum of the first 9 positive integers is given by the formula n(n+1)/2, where n is the number of terms.

Therefore, P(collision for first 10 records) =

(1/100)(9(9+1)/2)

= (1/100)(9*10/2)

= 45/100

= 0.45