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}$


$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.

  • $\begingroup$ Are you sure that the question has those four possible answers? $\endgroup$
    – Anatoly
    Commented Dec 11, 2015 at 22:10

1 Answer 1


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

\begin{align*} &P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)=h(k_4)\right)\\ &\qquad=\frac{1}{m^3}\\ &P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)\neq h(k_4)\right)\\ &\qquad=P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_3)\right)\\ &\qquad= P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_2)\right)\\ &\qquad =P\left(h(k_2)=h(k_3)\right)\cdot P\left(h(k_2)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_4)\right)\\ &\qquad =\frac{m-1}{m^3} \end{align*}

$$ $$

We conclude: \begin{align*} &P(\text{chain length }=4)+P(\text{chain length }=3)\\ &\qquad=\frac{1}{m^3}+4\frac{m-1}{m^3}\\ &\qquad=\frac{4m-3}{m^3} \end{align*}

  • 1
    $\begingroup$ @calmyoursenses: Thanks for accepting my answer and granting the bounty! Regards, $\endgroup$ Commented Dec 12, 2015 at 17:14
  • $\begingroup$ Why term $\frac{m-1}{m^3}$ is multiplied by $4$? $\endgroup$
    – Taylor
    Commented Jan 7, 2017 at 23:15
  • $\begingroup$ Why to assume four pairwise different keys? $\endgroup$
    – Taylor
    Commented Jan 7, 2017 at 23:17
  • 1
    $\begingroup$ @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}$ $\endgroup$ Commented Jan 8, 2017 at 5:52
  • 1
    $\begingroup$ @thor: Correct! I see everything's clear now! :-) $\endgroup$ Commented Jan 8, 2017 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .