# Hash table chain length probability -Simple uniform hashing

Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that at least a chain of size 3 is created? (Assume simple uniform hashing is used).

1. $m^{–2}$
2. $m^{–4}$
3. $m^{–3}(m–1)$
4. $3m^{–1}$

MY TRY

$P(atleast 3) = P(exactly 4) + P(exactly 3)$

$P(exactly 3) = {m \choose 1}\frac {1}{m^3} \frac {(m-1)}{m}*4 = \frac{4(m-1)}{m^3}$ [choose chaining slot and 4 positions for non-chaining slot ]

$P(exactly 4) = {m \choose 1}\frac {1}{m^4} = \frac {1}{m^3}$

$$P(atleast 3) = \frac {1}{m^3} + \frac{4(m-1)}{m^3} =\frac{4m-3}{m^3}$$

Doesn't match any of the options.

• Are you sure that the question has those four possible answers? Dec 11 '15 at 22:10

Note: Your approach is correct, given that we may assume four pairwise different keys.

If we consider a hashfunction $$h:\mathbb{N}\rightarrow \{1,\ldots,m\}$$ and four pairwise different keys $k_1,k_2,k_3,k_4$, we obtain



• @calmyoursenses: Thanks for accepting my answer and granting the bounty! Regards, Dec 12 '15 at 17:14
• Why term $\frac{m-1}{m^3}$ is multiplied by $4$? Jan 7 '17 at 23:15
• Why to assume four pairwise different keys? Jan 7 '17 at 23:17
• @thor: There are four possibilites, that precisely three keys are mapped to the same hash value while the fourth key is mapped to another hash value. Each of these four possibilities is stated in the last equation chain of the first part of the answer and each if these four possibilities is $\frac{m-1}{m^3}$ Jan 8 '17 at 5:52
• @thor: Correct! I see everything's clear now! :-) Jan 8 '17 at 15:48