in Algorithms recategorized by
17,738 views
53 votes
53 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 Algorithms recategorized by
by
17.7k views

3 Comments

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

_____________________________________________________________________________________ 

5
5
What does the meaning of last line of question "searching an item that is not present in table" please someone explain?
0
0

4 Answers

102 votes
102 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

4 Comments

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

2
2
8 votes
8 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.

1 comment

Actually, fifth time it will encounter an empty space and hence say element is not found

Question is not asking for putting the element in the table.

The first (and most upvoted) answer provides the correct explanation.

0
0
4 votes
4 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.

0 votes
0 votes

Another intuition, the search operation in Linear Probing is as;

search(key){
   while(true){
       if(A[i]==key)
           break;
       if(A[i]==NULL)
           break;
    i++;
   }

As they are asking about total comparisons needed to search item that is not present, it is basically we have to search for the longest path to hit NULL. 

This comes out to be 4 + 1 = 5.

 

 

Answer:

Related questions