recategorized by
867 views
0 votes
0 votes
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.
recategorized by

1 Answer

1 votes
1 votes
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.

Related questions

0 votes
0 votes
0 answers
1
rsansiya111 asked Mar 12, 2022
360 views
Canadian postal codes have the format LDL DLD, where L is always a letter (between A-Z), D is always a digit (0-9), and is always a single space. For example, the postal ...
0 votes
0 votes
1 answer
2
Ram Swaroop asked Jan 27, 2019
1,261 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
0 votes
0 votes
0 answers
3
Rahul_Rathod_ asked Dec 28, 2018
413 views
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
0 votes
0 votes
1 answer
4
Magma asked Dec 27, 2018
472 views
How to solve such kind of questions ? Can anybody tell what's is the concept behind this ?? someone provide me link so that I read it and understand the actual concept