1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure that the question has those four possible answers? $\endgroup$ – Anatoly Dec 11 '15 at 22:10
2
+50
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.