A hash table with ten buckets with one slot per bucket is shown in the…
1989
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols S₁ to S₇ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
Attempted by 2 students.
Show answer & explanation
Correct answer: 5
To find the maximum comparisons for a missing item, identify the longest sequence of consecutive occupied slots in the hash table.
The sequence starting at index 8 wraps around: S6 (8), S3 (9), S7 (0), and S1 (1) are all occupied. The next slot, index 2, is empty.
Searching for an item hashing to index 8 requires checking indices 8, 9, 0, 1 (4 comparisons) and finally index 2 to confirm absence (1 comparison), totaling 5 comparisons.
A video solution is available for this question — log in and enroll to watch it.