GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
300 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

Please explain the solution.

 

asked in Algorithms by Active (1.8k points)   | 300 views
Answer is B or C???

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

1 Answer

+11 votes
Best answer

Open addressing with linear probing

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

answered by Veteran (47k points)  
selected by

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??


Top Users Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,347 comments
31,011 users