MadeEasy Test Series: Programming & DS - Hashing

Question

Hash table with 6 slots

No of keys=8.

Collisions are resolved by chaining.

Expected no of non empty slots?

Answer 1

EXPECTED NO OF NON EMPTY SLOTS HAVING 'M' KEYS AND 'N' SLOTS IS=N(1-(1-1/N)^M)

HERE M=8 AND N=6

SO NO OF NONEMPETY SLOTS =6(1-(5/6)^8)

                                                  =4.6

Comments

Hey guys. I think the formula is wrong.

Consider that there are 3 keys and 2 slots.

===========================

Answer by above approach = 2.(1 - (1 -  $\frac{1}{2}$ )³ ) = 2. $\frac{7}{8}$  =  $\frac{14}{8}$

==============================

Now, considering the definition of expected value:

Let X denote the number of slots filled.

X:       1         2

P(X):   1/8      6/8

Thus, answer = 1 * 1/8  + 2 * 6/8

                    =  $\frac{13}{8}$

*******************************************

The above computation is wrong since for X=1, P(X) should be 2/8. So, expected val=14/8

---

Understand at your own risk : https://gateoverflow.in/4916/hashing

---

@abcd2. I took the wrong probablity for X=1. Editing the comment.