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

Please explain the solution.

 

asked in Algorithms by Active (1.8k points)   | 280 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

+10 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 (46.2k 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 Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users