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

- $4$
- $5$
- $6$
- $3$

## 3 Answers

### 5 Comments

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

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.