A hash table with ten buckets with one slot per bucket is shown in the…

Concept

In open addressing with linear probing, a key's probe sequence begins at its home bucket h(k) and advances one bucket at a time, wrapping around modulo the table size m.

A search for a key that is not present stops at the first empty bucket, because an empty bucket on the probe path proves the key was never stored beyond it. The comparisons made for an absent key are therefore the occupied buckets of the run it enters plus the one empty bucket that ends the search, so the worst case over all absent keys is (length of the longest run of consecutive occupied buckets) + 1.

Application

1. Read the occupied buckets from the table: 0 = S7, 1 = S1, 3 = S4, 4 = S2, 6 = S5, 8 = S6 and 9 = S3. Buckets 2, 5 and 7 are empty, and the table size is m = 10.

2. List the maximal runs of consecutive occupied buckets, allowing the wrap-around from bucket 9 to bucket 0: buckets 3-4 (S4, S2) of length 2, bucket 6 (S5) of length 1, and buckets 8, 9, 0, 1 (S6, S3, S7, S1) of length 4.

3. The longest run is 8 -> 9 -> 0 -> 1, of length 4, and the empty bucket that terminates it is bucket 2.

4. An absent key whose home bucket is 8 is compared with S6, S3, S7 and S1, which is four comparisons, and the fifth probe reaches the empty bucket 2, which ends the search.

5. Maximum comparisons = 4 + 1 = 5.

Cross-check

Checking all ten home buckets in turn:

No home bucket needs more than five comparisons, so the maximum number of comparisons needed to search for an item that is not present is 5.