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
Answer
(D)
Explanation
Compute the home slot \(h(x) = 3x \bmod 10\) of each key in order, moving to the next index whenever a slot is taken.
- \(h(1) = 3\), \(h(4) = 12 \bmod 10 = 2\), \(h(5) = 15 \bmod 10 = 5\) and \(h(6) = 18 \bmod 10 = 8\). All four slots are free.
- \(h(14) = 42 \bmod 10 = 2\). Slot 2 holds 4 and slot 3 holds 1, so 14 goes to slot 4.
- \(h(15) = 45 \bmod 10 = 5\). Slot 5 holds 5, so 15 goes to slot 6.
Option A lists the home slots 2 and 5, which were already occupied when 14 and 15 arrived.
Answer: D