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
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
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.
The symbols, S1 and S7 initially entered using a hashing function with linear probing.
what is the use of this??
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.....
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.
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.