Question

Considering a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions? (note:100 ^ 3 means 100 raised to the power 3)

Answer 1

qjjqjwjwjjwjwjwjjwjwjwjw

Answer 2

Answer:

The probability that the first 3 slots are unfilled after the first 3 insertions is 0.912673.

Step-by-step explanation:

Given : Considering a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing.

To find : What is the probability that the first 3 slots are unfilled after the first 3 insertions?

Solution :

Each item hashed has an equal probability of being placed into a slot.

Probability that first item does not go in any of the first 3 slots is given by,

$P_1=\frac{^{97}C_1}{^{100}C_1}$

$P_1=\frac{97}{100}$

Probability that second item does not go in any of the first 3 slots is given by,

$P_2=\frac{^{97}C_1}{^{100}C_1}$

$P_2=\frac{97}{100}$

Probability that third item does not go in any of the first 3 slots is given by,

$P_3=\frac{^{97}C_1}{^{100}C_1}$

$P_3=\frac{97}{100}$

Probability that the first 3 slots are unfilled after the first 3 insertions is given by,

$P=P_1\times P_2\times P_3$

$P=\frac{97}{100}\times\frac{97}{100}\times \frac{97}{100}$

$P=\frac{97\times97\times 97}{100^3}$

$P=\frac{97^3}{100^3}$

$P=\frac{912673}{1000000}$

$P=0.912673$

Therefore, The probability that the first 3 slots are unfilled after the first 3 insertions is 0.912673.