GATE DA Hash Tables Previous Year Questions

GATE DA 2025 | Question 18

MCQ · 1 mark · −0.33

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

2 and 5 2 and 6 4 and 5 4 and 6

Explanation

Answer: (D)

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

GATE DA 2024 | Question 21

MCQ · 1 mark · −0.33

Consider performing uniform hashing on an open address hash table with load factor \(\alpha = \frac{n}{m} < 1\), where \(n\) elements are stored in the table with \(m\) slots. The expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\).

Inserting an element in this hash table requires at most ______ probes, on average.

\(\ln\left(\dfrac{1}{1-\alpha}\right)\) \(\dfrac{1}{1-\alpha}\) \(1+\dfrac{\alpha}{2}\) \(\dfrac{1}{1+\alpha}\)

Explanation

Answer: (B)

To insert a key with open addressing, we follow the key's probe sequence until we reach an empty slot and store the key there. An unsuccessful search for the same key follows the same sequence and also stops at the first empty slot, so an insertion makes exactly the probes of an unsuccessful search. Its average cost therefore has the same bound, at most \(\frac{1}{1-\alpha}\) probes.

Options A and C are smaller than this bound for every \(0 < \alpha < 1\), so they understate the cost; they resemble formulas for successful searches. Option D is even below 1, although every insertion probes at least one slot.

Answer: B