A hash table with 10 buckets with one slot per bucket is depicted here. The…
2018
A hash table with 10 buckets with one slot per bucket is depicted here. The symbols, 51 to 57 are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is
Index | Value |
0 | 57 |
1 | 51 |
2 | |
3 | 54 |
4 | 52 |
5 | |
6 | 55 |
7 | |
8 | 56 |
9 | 53 |
- A.
4
- B.
5
- C.
6
- D.
3
Attempted by 218 students.
Show answer & explanation
Correct answer: B
Linear probing searches sequentially from the hash index until an empty slot is found. The maximum comparisons occur when searching for a non-existent item that hashes to the beginning of the longest cluster of occupied slots. The hash table has a cluster at indices 8, 9, 0, and 1 (wrapping around), which has a length of 4. Searching for an item hashing to index 8 requires probing indices 8, 9, 0, and 1 (all occupied) before finding the empty slot at index 2. This results in 4 comparisons for occupied slots + 1 comparison for the empty slot = 5 total comparisons. Other clusters are shorter (indices 3-4 and index 6), yielding fewer comparisons.
A video solution is available for this question — log in and enroll to watch it.