The Gateway to Computer Science Excellence
+30 votes

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

  1. $4$
  2. $5$
  3. $6$
  4. $3$
in DS by Loyal (5.8k points)
edited by | 7.2k views
what will be final ans 4 or 5


3 Answers

+65 votes
Best answer
No of comparison in worst case for an element not in hash table is size of largest cluster $+1$. This is because the probe stops as soon as an empty slot is found (we r using linear probing here).

Size of largest cluster is $4$ $(S6, S3, S7, S1)$

No of comparison is  $4 + 1 = 5$

Correct Answer: $B$
by Veteran (60.9k points)
edited by

what if i continuously performs insert and delete then it can be any where , eg say i put s8 by probing it will go to the 3rd position and now i delete the s7 , then in case to search the s8 we have to search the whole list 

right ?

We are asked for the current state only. After insert/delete the state changes.

look at S3 , its on the 10th (9) position .

so we want to search for S3 , we will start from 4th(3) position and look still 6th position (5) .

and declared that its not there (though its there at place 9)


For S3, how you said we'll start at position 3? Assumed mod 10 hashing?

We can't do that. Because then this state would never have come. And deletion in linear probing is not a simple removal. 


Worst case happens when hash goes to slot 8 which is occupied by S6.

The symbols, S1 and S7 initially entered using a hashing function with linear probing.

what is the use of this??

Plzz explain how s7,s6,s3 and s1 are taken as largest clusters ..Arjun sir plzz explain
I think largest cluster is the maximum no. of elements sequentially without an empty slot. Here, if we start searching from s6, after that we get 3 numbers. that is s6,s3,s7 and s0 followed by an empty slot. In other case there are only 2 sequential numbers followed by an empty slot. So, if originally, hash key is found at 8ie s6 but item is not s6, then it will move to further slot till it finds searching item. So, in worst condition,we get 5.
In this case, what will be the minimum number of comparisons for unsuccessful search?
Since it's linear probing, the unsuccesful search can start with looking at the empty slot first. In that case it will take 1 comparision. Isn't that so?
Explanation for this answer please.

ANd what about quadratic probing and double hashing?
@Arjun sir, the last comparison will be done with empty slot?
can any one explain this question clearly and than answer also with simple example ?
why is it largest cluster +1 ?

since in last block we have checked its empty ( either through a special symbol or value) so no comparisions.

please clear .

If someone has confusion about deletion in Linear Probing :

"When a key–value pair is deleted, it may be necessary to move another pair backwards into its cell, to prevent searches for the moved key from finding an empty cell."



In easy words when we delete value when i=0 then we have to put back the value where i=1 in place of i=0 and precess continues.....

+4 votes

We can illustrate it as :

for position 8th when we calculate value of linear probing for First time we can't store value because it is already filled. So,

For 9th position we have to calculate value of probing for the Second time.

For 0th position we have to calculate value of probing for the Third time.

Similarly, for Ist position we have to calculate it for Fourth time but it is also filled previously.

so, for 2nd position when we calculate it for Fifth time place is empty here and value can be putted. 

Maximum number of comparisons is that how many number of probes we have calculated for it.

So, number of probes here are 5 hence the answer.

by Active (2.1k points)
0 votes

Suppose the hash function gives our key the value 8.

=> Go to index number 8.

Index number 8 is already occupied, so check the next index in case our key got linearly probed.

=> Check index 9. Same as above.

=> Check index 0. Same as above.

=> Check index 1. Same as above.

=> Check index 2; it is empty, so if the key were present, it'd be here. => Unsuccessful search.


This took a total number of 5 comparisons.

The number of comparisons for an unsuccessful search in a hash table that uses linear probing = Size of the biggest cluster + 1.

by Loyal (6.6k points)

Related questions

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
50,737 questions
57,324 answers
105,169 users