#Hashing

Question

Consider a hash table with m slots that uses open addressing with linear probing. The table is initially empty. A key k1 is inserted into the table, followed by keyk2, and then keyk3.What is the probability that the total number of probes while inserting these keys is at least 4?

Answer 1

Probe is how many empty or occupied position are to be "Looked-up" before actually inserting an element.

There are $2$ cases for which total number of probes while inserting these keys is at least $4$ :

• In terms a collision

$\rightarrow$ $M$ ways to decide for $K1$ ($1$ Probe Done)

$\rightarrow$ Now, only $1$ way for $K2$ to collide with $K1$ (In this case $2$ Probes)

$\rightarrow$ Now, $K3$ can go anywhere ( $4$ Probes Done)

Hence, Probability for this case = $\frac{m}{m} * \frac{1}{m} *\frac{m}{m}$ = $\frac{1}{m}$

• In terms of No collision occurs

$\rightarrow$  $M$ ways to decide for $K1$ ( $1$ Probe Done)

$\rightarrow$  Now, $K2$ can go anywhere other than $K1$ and having $m -1$ ways to decide (In this case $1$ Probe)

$\rightarrow$  Now, $K3$ can go to either $K1$ or $K2$ ( $4$ Probes Done)

Hence, Probability for this case = $\frac{m}{m}*\frac{m-1}{m}*\frac{2}{m}$ = $\frac{2(m-1)}{m^{2}}$

---

Hence, Total Probability comes out to be = $\frac{2(m-1)}{m^{2}} + \frac{1}{m}$

Comments

Question is asking us to find 

the probability that the total number of probes while inserting these keys is at least 4?

but this is probability of exactly 4.

I'm getting maximum of 6 probes. Why are we not considering other conditions?

---

@kapil @gabbar  i am not getting how k3 is probability = m/m (collision)

or  2/m( without collision)  plz help????????

---

case1: insert fiist key 1 probe.now insert k2 in same location 2 probes with probability 1/m ... now if  you enter k3 at any location there must be atleast 1 probe...

 

case1: 2 keys are inserted into distinct location having total 2 probes. now need more 2 probes.

now for k3 we must need to generate collision so having only 2 choices...

hope this helps!

Answer 2

To insert 3 elements at least 3 probes will be required if no collision happened

$P(X \geq 4) = 1 - P(X = 3)$

$P(X = 3) = \frac{m}{m} \times \frac{m-1}{m} \times \frac{m-2}{m} = \frac{m^2 -3m +2}{m^2}$

$\therefore P(X \geq 4) = 1 - P(X = 3) = 1 - \frac{m^2 -3m +2}{m^2}$

$= \frac{3m-2}{m^2}$