GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
251 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.7k points)   | 251 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

+9 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 (45.3k 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 ?

Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users