recategorized by
3,184 views
16 votes
16 votes

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.

recategorized by

2 Answers

Best answer
22 votes
22 votes

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

selected by
1 votes
1 votes
probability of filling next empty slot =(i+1)/m. where previous i elements are filled.

So now inserting k1= mC1 *1/m  =1  .Now considering only next slot after k1 is filled probability=1/m.

for k3 since previous 2 are filled and probability of inserting k3 in next  empty slot=(2+1)/m=3/m.

therefore 1*1/m*3/m=3/m^2.

Related questions

1 votes
1 votes
1 answer
1
s_dr_13 asked Mar 6, 2019
959 views
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful se...
0 votes
0 votes
1 answer
2
tishhaagrawal asked Dec 16, 2023
309 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...
0 votes
0 votes
0 answers
3
Rahul_Rathod_ asked Dec 28, 2018
413 views
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
1 votes
1 votes
0 answers
4
hrcule asked Aug 9, 2018
500 views
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is us...