recategorized by
17,662 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$
recategorized by

4 Answers

Best answer
102 votes
102 votes
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
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.

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

12 votes
12 votes
4 answers
1
makhdoom ghaya asked Nov 30, 2016
2,656 views
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
48 votes
48 votes
2 answers
3
Kathleen asked Sep 23, 2014
22,544 views
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$then the o...
31 votes
31 votes
6 answers
4
Kathleen asked Sep 18, 2014
19,270 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...