Hashing

Question

Consider a hash table with 8 slots that uses chaining for collision resolution .The table is initially empty .what is probability that after 4 keys inserted at least a chain of 3 created?

Comments

Is it $\frac{1}{64}$??

---

I think answer should be 29/512

---

What is your approach?

Answer 1

Case I : All going to one slot

$(\frac{1}{8})^3  \ 1^{st} insertion=1 \ ,  rest = \frac{1}{8}$

Case 2 :Second third or fourth  any one is going to different slot :  

 $ \frac{21}{8^3} \ 1^{st} insertion=1 \ $ then $3_{c_2}*(\frac{1}{8})^2 * \frac{7}{8}$

Case 3 : 1st one is going different and other three insertions are going to one slot :

$ \frac{7}{8^3} \ 1^{st} insertion=1 \ $ then $ \frac{7}{8}*(\frac{1}{8})^2$

Adding all of these : $\frac{1}{8^3} + \frac{21}{8^3} + \frac{7}{8^3}= \frac{29}{8^3}$

Answer 2

For every key, we have 8 choices, So total permutation = 8^4
P(chain of at least 3 is created) = P(chain of 4)+ P(chain of 3)

permutations for a chain of 4 = 8C1  [as we have 8 slots and we have to choose 1 slot for every element]

permutation for a chain of 3 = 4C1 * 8C1 * 7 [here 3 keys will be at the same slot and 1 will be at in one of the remaining 7 slots.]

P(chain of atleast 3 is created) = ( 8 + 4*8*7)/8^4
P = 29/512