Consider a hash table with 9 slots. The hash function is \(h(k) = k \ mod \…
2014
Consider a hash table with 9 slots. The hash function is \(h(k) = k \ mod \ 9\). The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are
- A.
3, 0, and 1
- B.
3, 3, and 3
- C.
4, 0, and 1
- D.
3, 0, and 2
Attempted by 129 students.
Show answer & explanation
Correct answer: A
Solution: compute h(k)=k mod 9 for each key and then read off chain lengths.
Compute hashes: 5→5, 28→1, 19→1, 15→6, 20→2, 33→6, 12→3, 17→8, 10→1.
Chain lengths by slot (0 through 8): 0, 3, 1, 1, 0, 1, 2, 0, 1.
Maximum chain length = 3 (slot 1).
Minimum chain length = 0 (slots 0, 4, and 7 are empty).
Average chain length (over 9 slots) = total keys 9 ÷ 9 slots = 1.
Therefore the maximum, minimum, and average chain lengths are 3, 0, and 1 respectively.
A video solution is available for this question — log in and enroll to watch it.