Consider a hash table P[0, 1, , 10] that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is h(x) = (x + 7) 11. Consider the following sequence of insertions performed on P: 1, 13, 22, 15, 11, 24. Which of the following positions in the hash table is/are empty after these insertions are performed?

GATE 2026 CS (CS1) – Question 24

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple select

Consider a hash table $P[0, 1, \dots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x) = (x + 7) \bmod 11$. Consider the following sequence of insertions performed on $P$: $1, 13, 22, 15, 11, 24$. Which of the following positions in the hash table is/are empty after these insertions are performed?

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 2

Explanation

Table size $m = 11$, valid indices $0$ to $10$. Linear probing probe sequence: $(h(x) + i) \bmod 11$ for $i = 0, 1, 2, \dots$

Trace insertions:
1. Key 1: $h(1) = (1 + 7) \bmod 11 = 8$. Slot 8 is empty $\implies P[8] = 1$.
2. Key 13: $h(13) = (13 + 7) \bmod 11 = 20 \bmod 11 = 9$. Slot 9 is empty $\implies P[9] = 13$.
3. Key 22: $h(22) = (22 + 7) \bmod 11 = 29 \bmod 11 = 7$. Slot 7 is empty $\implies P[7] = 22$.
4. Key 15: $h(15) = (15 + 7) \bmod 11 = 22 \bmod 11 = 0$. Slot 0 is empty $\implies P[0] = 15$.
5. Key 11: $h(11) = (11 + 7) \bmod 11 = 18 \bmod 11 = 7$. Slot 7 is occupied (22), probe 8 (occupied 1), probe 9 (occupied 13), probe 10 (empty) $\implies P[10] = 11$.
6. Key 24: $h(24) = (24 + 7) \bmod 11 = 31 \bmod 11 = 9$. Slot 9 is occupied (13), probe 10 (occupied 11), probe 0 (occupied 15), probe 1 (empty) $\implies P[1] = 24$.

Occupied slots: $\{0, 1, 7, 8, 9, 10\}$.
Empty slots: $\{2, 3, 4, 5, 6\}$.

Among the options: 0 (occupied), 10 (occupied), 2 (empty), 1 (occupied).
Thus, only position 2 is empty. Option (C) is correct.