Consider a hash table 𝑃[0,1,…,10] that is initially empty. The hash table is…
2026
Consider a hash table 𝑃[0,1,…,10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is ℎ(𝑥)=(𝑥+7) mod 11.
Consider the following sequence of insertions performed on 𝑃:
1,13,22,15,11,24
Which of the following positions in the hash table is/are empty after these insertions are performed?
- A.
0
- B.
10
- C.
2
- D.
1
Attempted by 23 students.
Show answer & explanation
Correct answer: C
The hash table has size 11 (indices 0-10). The hash function is h(x) = (x + 7) mod 11. We use linear probing for collisions.
1. Insert 1: h(1) = (1+7)%11 = 8. Slot 8 is empty. Place 1 at index 8.
2. Insert 13: h(13) = (13+7)%11 = 9. Slot 9 is empty. Place 13 at index 9.
3. Insert 22: h(22) = (22+7)%11 = 7. Slot 7 is empty. Place 22 at index 7.
4. Insert 15: h(15) = (15+7)%11 = 0. Slot 0 is empty. Place 15 at index 0.
5. Insert 11: h(11) = (11+7)%11 = 7. Slot 7 occupied. Probe 8 (occupied), 9 (occupied), 10 (empty). Place 11 at index 10.
6. Insert 24: h(24) = (24+7)%11 = 9. Slot 9 occupied. Probe 10 (occupied), 0 (occupied), 1 (empty). Place 24 at index 1.
Final occupied indices: 0, 1, 7, 8, 9, 10. Empty indices: 2, 3, 4, 5, 6.