In a double hashing scheme, and are the auxiliary hash functions. The size of the hash table is 11. The hash function for the -th probe in the open address table is . The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24.
The slot at which key 24 gets stored is ________. (Answer in integer)
ANSWER
The key 24 is stored at slot 10.
Official answer: 10 to 11Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)
Compute for the first five keys, which are inserted with no collisions since all slots differ: , , , , .
Table after these insertions: slot 1 = 67, slot 2 = 79, slot 3 = 25, slot 6 = 50, slot 8 = 63; all other slots (0, 4, 5, 7, 9, 10) are empty.
For key 24: .
.
Probe : — occupied by 79, so probing continues.
Probe : — occupied by 50, so probing continues.
Probe : — this slot is empty, so key 24 is stored at slot 10.
KEY IDEA
In double hashing, the probe sequence for a key is for ; since never depends on , each key traces a fixed "skip" sequence through the table until it lands on an empty slot.
WATCH OUT FOR
Forgetting that once a slot is found occupied, the probe sequence must be recomputed with the next value of i (not restarted or incremented incorrectly), and mixing up which key already occupies a slot — leading students to place 24 in slot 6 or slot 2 by mistake.
From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
