The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
339 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.9k points) | 339 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 (48.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 ?

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,844 answers
91,383 comments
34,722 users