GATE CS 2007 Q40 — Arrays, Stacks and Queues

We are given a hash table of size $N = 7$ (with indices $0$ to $6$) and the hash function:

Since "closed hashing" (also known as open addressing) is used, we resolve collisions using linear probing, where we search sequentially for the next available slot: $h_i(x) = (h(x) + i) \bmod 7$ for $i = 0, 1, 2, \dots$.

Let's insert the keys $1, 3, 8, 10$ step-by-step into an initially empty table:

1. Insert $1$:
   $h(1) = (3 \times 1 + 4) \bmod 7 = 7 \bmod 7 = 0$.
   Slot $0$ is empty. Place $1$ at index $0$.
   Table state: [1, -, -, -, -, -, -]


2. Insert $3$:
   $h(3) = (3 \times 3 + 4) \bmod 7 = 13 \bmod 7 = 6$.
   Slot $6$ is empty. Place $3$ at index $6$.
   Table state: [1, -, -, -, -, -, 3]


3. Insert $8$:
   $h(8) = (3 \times 8 + 4) \bmod 7 = 28 \bmod 7 = 0$.
   Slot $0$ is occupied by $1$ (collision).
   Using linear probing, we try the next slot: $(0 + 1) \bmod 7 = 1$.
   Slot $1$ is empty. Place $8$ at index $1$.
   Table state: [1, 8, -, -, -, -, 3]


4. Insert $10$:
   $h(10) = (3 \times 10 + 4) \bmod 7 = 34 \bmod 7 = 6$.
   Slot $6$ is occupied by $3$ (collision).
   Probing sequence:
   • Try slot $(6 + 1) \bmod 7 = 0$ (occupied by $1$)
   • Try slot $(0 + 1) \bmod 7 = 1$ (occupied by $8$)
   • Try slot $(1 + 1) \bmod 7 = 2$ (empty)
   Place $10$ at index $2$.
   Table state: [1, 8, 10, -, -, -, 3]

Thus, the final contents of the hash table are $1, 8, 10$, −, −, −, $3$, which matches option B.