The GATE Grind

GATE 2025 DA – Question 18

Programming, Data Structures and Algorithms · Stacks, queues, linked lists, trees and hash tables · 1 mark · Multiple choice

Consider a hash table of size 10 with indices $\{0, 1, \ldots, 9\}$, with the hash function

$$h(x) = 3x \pmod{10},$$

where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: 1, 4, 5, 6, 14, 15. The indices where the keys 14 and 15 are stored are, respectively

  1. 2 and 5
  2. 2 and 6
  3. 4 and 5
  4. 4 and 6

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 4 and 6

Explanation

The hash values are $h(1) = 3$, $h(4) = 12 \bmod 10 = 2$, $h(5) = 15 \bmod 10 = 5$ and $h(6) = 18 \bmod 10 = 8$, so the keys 1, 4, 5 and 6 go to indices 3, 2, 5 and 8. For 14, $h = 42 \bmod 10 = 2$ is taken, 3 is taken, and 4 is free, so 14 is stored at index 4. For 15, $h = 45 \bmod 10 = 5$ is taken and 6 is free, so 15 is stored at index 6.