GATE CSE 1989 | Question: 1-vii, ISRO2015-14
in DS retagged by
12,540 views
38 votes
38 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 retagged by
by
12.5k views

2 Comments

what will be final ans 4 or 5
0
0
edited by

_____________________________________________________________________________________ 

3
3

Subscribe to GO Classes for GATE CSE 2022

3 Answers

78 votes
78 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$
edited by

5 Comments

@Arjun sir, the last comparison will be done with empty slot?
0
0
can any one explain this question clearly and than answer also with simple example ?
0
0
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 .
0
0
edited by

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."

----------------------

H(k)=[h(k)+i]%m

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.....

https://en.wikipedia.org/wiki/Linear_probing

1
1
6 votes
6 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.

3 votes
3 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.

Answer:

Related questions