280 views

Using open addressing with linear probing, we sequentially insert three distinct keys k1, k2 and k3 into a hash table of size m. Assuming simple uniform hashing, what is the probability that we will need three probes, when inserting the third key, k3?

1.  3/m
2.  2/m2
3.  3/m2
4.  2/m

P(we need 3 probes)

1st entry : No collosion k1 can be placed in any one of m slots = m/m
2nd entry : Collision m/m * 1/m
3rd Entry : Collosion  m/m *1/m*1/m

Req probability = 1/m2

No bro, it ain't that simple.
$3/m^2$ may be possible answer

Inserting k1 : out of m slot we can choose any one slot i.e. m/m
Inserting k2 : Either it would be in same slot as k1 or just next slot or just previous slot of k1. 3 choices out of m choices. i.e. 3/m
Inserting k3 : Now we have two consecutive keys :

• k1 then k2
• k2 then k1

In both cases k3 will take 3 probes iff it iserted at k1 (as in case 1) or at k2 (as in case 2). So to insert k3 we have only one choice i.e.

Resultant Probability $= \frac{m}{m}.\frac{3}{m}.\frac{1}{m} = \frac{3}{m^2}$

selected

Two possible cases :

@Digvijay_Pandey Can u pls explain

Either it would be in same slot as k1 or just next slot or just previous slot of k1. 3 choices out of m choices.

A little more .

In linear probing .
K1 first occupies a slot , if collision k2 occupies same slot but linked next , if angain collosion k3 occupies same slot with one more linking .

Correct me if wrong

@digvijay.. Why k3 has only one choice
As it can go to k1 or k2, choice should be 2.
@gokou You referring to chaining? Here it is linear probing- when collision happens, next slot is considered next.

@Vaishali We already considered 2 cases- and in each we have 1 way each. So, choice is only 1 for 3rd insertion (we are doing multiplication of the choices in each insertion).

Either it would be in same slot as k1 or just next slot or just previous slot of k1. 3 choices out of m choices. i.e. 3/m

sir if we will take an  element (k2) greater than "m" to insert  , it will automatically refer to the previous slot of " k1" .

so this next slot or just previous slot of k1 should be considered as the same case ??
correct me ?

why for k2 it should be either at k or previous or next of k?? why cant be anywhere else??

1
2