Hashing and Collision Resolution PYQs for GATE CS

Solve 5+ Hashing and Collision Resolution previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Open Addressing Mechanics and Probe Sequences

Table with 11 slots. A key hashes to slot 3, but it is occupied.

Linear probe: 3 → 4 → 5 → 6 → 7

primary clustering consecutive slots fill into a block

secondary clustering two keys hashing to 3 follow the identical path

Consider a hash table with eleven slots, indexed from zero to ten. If we insert a key that hashes to slot three, but slot three is already occupied, we must check another slot. In open addressing, we check slots according to a fixed probe sequence. If the sequence checks slots three, four, five, and six in order, we are using linear probing. This creates primary clustering, where consecutive slots fill up, forming traffic jams. If two different keys both hash to slot three and follow the exact same sequence, they suffer from secondary clustering. In linear and quadratic probing, the probe sequence depends only on the initial hash value, not the key itself. Double hashing avoids this by making the step size a function of the key.

Explain this more simply

Imagine a parking lot where every car has an assigned spot. If your spot is taken, you do not leave the lot. You drive to the next available spot. Primary clustering is what happens when everyone assigned to the front row ends up parking in the back row because the front is full. Secondary clustering is when two different people, assigned to the same spot, follow the exact same driving path to find a new space.

Go one level deeper

The mathematical distinction between these clusterings dictates performance. Primary clustering degrades the expected probe length because the probability of hitting a filled block increases with the block size. Secondary clustering is less severe but still present in linear and quadratic probing because the probe sequence is a deterministic function of the initial hash value. Double hashing eliminates secondary clustering by making the step size a function of the key itself.

Linear Probing Formula and Wrap-around

Table size 11. Key hashes to slot 8. Slots 8, 9, 10 are full.

Probe 0: slot 8 (full) → Probe 1: slot 9 (full) → Probe 2: slot 10 (full) → Probe 3: slot 0 (wrap-around)

h(k, i) = (h(k) + i) mod m

For h(k)=8, m=11: i=0 → 8, i=1 → 9, i=2 → 10, i=3 → 0

Suppose a table has size eleven. A key hashes to slot eight. If slot eight is full, linear probing checks slot nine, then ten, then wraps around to zero, then one. The general formula for the i-th probe is the initial hash plus i, all modulo the table size. For our key, the zero-th probe is eight. The first probe is nine. The second probe is ten. The third probe wraps around to zero. The step size is always exactly one. This constant step is what causes primary clustering, as any key hashing near a filled block will join that block.

Explain this more simply

Think of a circular track with eleven lanes. You start in your assigned lane. If it is blocked, you move to the very next lane. If you reach lane ten and it is blocked, your next step takes you back to lane zero. You never skip a lane.

Go one level deeper

Three-second check: Substitute zero into your formula. If the result is not exactly the initial hash value, your index offset is wrong. The most common error is starting the probe index at one instead of zero. If you start at one, your first check is the initial hash plus one, completely skipping the initial hash slot.

Hashing and Collision Resolution: Solved Questions with Step-by-Step Explanations (5 Problems)

Question 1 · Programming and Data Structures · 2026_Set2 NAT

The keys $5, 28, 19, 15, 26, 33, 12, 17, 10$ are inserted into a hash table using the hash function $h (k) = k mod 9$ . The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is __________. <i>(answer in integer)</i>

Correct Answer:

3.00

Step-by-Step Solution

Insight: Separate chaining appends colliding keys to a linked list at the hashed index; the longest chain is simply the maximum bucket size.

Exam route: Compute $k mod 9$ for all 9 keys, tally the frequencies of each remainder, and pick the maximum frequency.

Learning route:

The hash function is $h (k) = k mod 9$ .

Compute the bucket for each key:

$5 mod 9 = 5$
$28 mod 9 = 1$
$19 mod 9 = 1$
$15 mod 9 = 6$
$26 mod 9 = 8$
$33 mod 9 = 6$
$12 mod 9 = 3$
$17 mod 9 = 8$
$10 mod 9 = 1$

Tallying the remainders:

Index 0: 0 keys
Index 1: 28, 19, 10 (3 keys)
Index 2: 0 keys
Index 3: 12 (1 key)
Index 4: 0 keys
Index 5: 5 (1 key)
Index 6: 15, 33 (2 keys)
Index 7: 0 keys
Index 8: 26, 17 (2 keys)

The maximum number of keys in any bucket is 3 (at index 1).

Thus, the length of the longest chain is 3.

Tempting wrong path: A student might count the total number of collisions instead of the maximum chain length. There are 4 collisions (28 collides with 19, 10 collides with them, 33 collides with 15, 17 collides with 26), leading to an answer of 4. This breaks down because "longest chain" refers to the maximum bucket size, not the sum of collisions.

Generalization: In separate chaining, the chain length at any index is exactly the frequency of that hash value.

Verification: Re-checking $28 = 3 \times 9 + 1$ , $19 = 2 \times 9 + 1$ , $10 = 1 \times 9 + 1$ . All correctly map to 1. No other bucket has 3 or more keys.

Question 2 · Programming and Data Structures · 2026_Set1 MSQ

Consider a hash table

P [0, 1, \dots, 10]

that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is

h (x) = (x + 7) mod 11

.

Consider the following sequence of insertions performed on

P

1, 13, 22, 15, 11, 24

Which of the following positions in the hash table is/are empty after these insertions are performed?

A.
0
B.
10
C.
2
D.
1

Correct Answer:

["C"]

Step-by-Step Solution

Insight: Linear probing resolves collisions by sequentially checking the next available slot, wrapping around the table if necessary.

Exam route: Map each key to its initial hash, then shift right one slot at a time upon collision, keeping track of occupied indices to identify the empty ones.

Learning route:

Table size $m = 11$ , indices $0$ to $10$ .

$h (x) = (x + 7) mod 11$ .

Insertions:

1: $h (1) = 8$ . P[8] = 1.
13: $h (13) = 9$ . P[9] = 13.
22: $h (22) = 7$ . P[7] = 22.
15: $h (15) = 0$ . P[0] = 15.
11: $h (11) = 7$ . P[7] full. Probe 8 (full), 9 (full), 10 (empty). P[10] = 11.
24: $h (24) = 9$ . P[9] full. Probe 10 (full), 0 (full), 1 (empty). P[1] = 24.

Occupied slots: 0, 1, 7, 8, 9, 10.

Empty slots: 2, 3, 4, 5, 6.

Checking the options: 0 is occupied, 10 is occupied, 2 is empty, 1 is occupied. Only position 2 is empty.

Tempting wrong path: Assuming index 0 remains empty because no key naturally hashes to it without wrap-around, but 15 hashes to 0 directly. Or assuming index 10 is empty because it is at the end, forgetting that 11 wraps into it.

Generalization: Linear probing clusters can wrap around the end of the array; always apply the modulo operator when incrementing the probe index.

Verification: Count the keys. 6 keys inserted, so exactly 6 slots must be occupied and 5 empty. Our occupied list has 6 distinct slots.

Question 3 · Programming and Data Structures · 2025_Set1 NAT

In a double hashing scheme,

h_{1} (k) = k mod 11

and

h_{2} (k) = 1 + (k mod 7)

are the auxiliary hash functions. The size

m

of the hash table is 11. The hash function for the

i

-th probe in the open address table is

[h_{1} (k) + i h_{2} (k)] mod m

. 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)

Correct Answer:

10.00

Step-by-Step Solution

Insight: Double hashing uses a secondary hash function to determine the step size for probing, avoiding primary clustering.

Exam route: Trace the table state by inserting each key sequentially, then apply the double hashing formula $h (k, i) = [h_{1} (k) + i \cdot h_{2} (k)] mod m$ for the target key until an empty slot is found.

Learning route:

Table size $m = 11$ .

$h_{1} (k) = k mod 11$

$h_{2} (k) = 1 + (k mod 7)$

Insertions:

63: $h_{1} = 8, h_{2} = 1$ . $P (0) = 8$ . Table[8] = 63.
50: $h_{1} = 6, h_{2} = 2$ . $P (0) = 6$ . Table[6] = 50.
25: $h_{1} = 3, h_{2} = 5$ . $P (0) = 3$ . Table[3] = 25.
79: $h_{1} = 2, h_{2} = 3$ . $P (0) = 2$ . Table[2] = 79.
67: $h_{1} = 1, h_{2} = 5$ . $P (0) = 1$ . Table[1] = 67.

Now insert 24:

$h_{1} (24) = 24 mod 11 = 2$

$h_{2} (24) = 1 + (24 mod 7) = 1 + 3 = 4$

Probe sequence for 24:

$i = 0 : (2 + 0 \times 4) mod 11 = 2$ . Occupied by 79.
$i = 1 : (2 + 1 \times 4) mod 11 = 6$ . Occupied by 50.
$i = 2 : (2 + 2 \times 4) mod 11 = 10$ . Empty!

Key 24 is stored at slot 10.

Tempting wrong path: Forgetting the $+ 1$ in $h_{2} (k)$ and using $h_{2} (24) = 24 mod 7 = 3$ . The probes would be $2, (2 + 3) mod 11 = 5, (2 + 6) mod 11 = 8$ . Since 8 is occupied by 63, the next is $(2 + 9) mod 11 = 0$ . This leads to slot 0, which is incorrect because the formula explicitly includes the $+ 1$ to ensure the step size is never 0.

Generalization: In double hashing, $h_{2} (k)$ must never evaluate to 0, which is why formulas often include a $+ 1$ or use a prime modulus.

Verification: Check if any earlier key was displaced. Open addressing only places keys in empty slots. 10 is indeed empty.

Question 4 · Programming and Data Structures · 2022 MCQ

Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}$ . Further suppose our hashing scheme uses $h_{1}$ for the odd keys and $h_{2}$ for the even keys. What is the expected number of keys in a slot?

A.
$\frac{m}{n}$
B.
$\frac{n}{m}$
C.
$\frac{2 n}{m}$
D.
$\frac{n}{2 m}$

Correct Answer:

Step-by-Step Solution

Insight: Simple uniform hashing guarantees that every key independently has a $1/ m$ probability of landing in any specific slot, regardless of the deterministic rule used to pick the hash function.

Exam route: Recognize that any simple uniform hash function distributes keys evenly in expectation. The expected load is simply total keys divided by total slots.

Learning route:

Let $X_{i, j}$ be an indicator random variable that is 1 if key $i$ hashes to slot $j$ , and 0 otherwise.

Because both $h_{1}$ and $h_{2}$ are simple uniform hash functions, for any key $k$ , the probability that it maps to slot $j$ is exactly $1/ m$ , whether it uses $h_{1}$ or $h_{2}$ .

Thus, $E [X_{i, j}] = 1/ m$ for all $i \in {1 \dots n}$ .

The total number of keys in slot $j$ is $Y_{j} = \sum_{i = 1}^{n} X_{i, j}$ .

By linearity of expectation:

$E [Y_{j}] = \sum_{i = 1}^{n} E [X_{i, j}] = \sum_{i = 1}^{n} \frac{1}{m} = \frac{n}{m}$ .

Tempting wrong path: Assuming the parity split halves the keys per slot, leading to $n /2 m$ . While half the keys use $h_{1}$ and half use $h_{2}$ , both functions map to the same $m$ slots with probability $1/ m$ , so the total expectation remains $n / m$ .

Generalization: Linearity of expectation holds regardless of dependencies or deterministic routing rules, as long as the marginal probability for each item remains uniform.

Verification: If $n = m$ , expected keys per slot is 1. Formula gives $m / m = 1$ . Matches intuition.

Question 5 · Programming and Data Structures · 2021_Set1 MSQ

Consider a dynamic hashing approach for 4-bit integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3^rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4^th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.
Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

A.
5, 9, 4, 13, 10, 7
B.
9, 5, 10, 6, 7, 1
C.
10, 9, 6, 7, 5, 13
D.
9, 5, 13, 6, 10, 14

Correct Answer:

["C"]

Step-by-Step Solution

Insight: Dynamic hashing with a binary tree resolves collisions by branching on successive higher-order bits only when a leaf node experiences a collision.

Exam route: Decode the tree structure from the diagram to find the required bit patterns for each leaf, then test each option's sequence to see which one perfectly builds that exact tree without extra splits.

Learning route:

The diagram shows a main table of 4 slots indexed by the 2 LSBs ( $b_{1} b_{0}$ ).

Index 0 (00): Empty.
Index 1 (01): Splits on $b_{2}$ . Left child ( $b_{2} = 0$ ) is a leaf. Right child ( $b_{2} = 1$ ) splits on $b_{3}$ .
Index 2 (10): Splits on $b_{2}$ . Left child ( $b_{2} = 0$ ) is a leaf. Right child ( $b_{2} = 1$ ) is a leaf.
Index 3 (11): Leaf.

Test Option C: 10, 9, 6, 7, 5, 13

10 (1010): idx 2. Leaf.
9 (1001): idx 1. Leaf.
6 (0110): idx 2. Collides with 10. Splits on $b_{2}$ . 10 has $b_{2} = 0$ , 6 has $b_{2} = 1$ . Matches diagram!
7 (0111): idx 3. Leaf. Matches diagram!
5 (0101): idx 1. Collides with 9. Splits on $b_{2}$ . 9 has $b_{2} = 0$ , 5 has $b_{2} = 1$ .
13 (1101): idx 1. Collides with 5. Splits on $b_{3}$ . 5 has $b_{3} = 0$ , 13 has $b_{3} = 1$ . Matches diagram!

Tempting wrong path: Selecting a sequence that includes 14 (1110), which hashes to index 2 with $b_{2} = 1$ . This would collide with 6 (0110) at the right child of index 2, forcing an unwanted split on $b_{3}$ , which the diagram does not show.

Generalization: In dynamic hashing, splits are strictly demand-driven; a node only branches when a collision occurs at that exact leaf, using the next available bit.

Verification: Option C perfectly reconstructs the tree without leaving any index empty that should be occupied, and without triggering any unshown splits.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Hashing and Collision Resolution PYQs for GATE CS

Open Addressing Mechanics and Probe Sequences

Linear Probing Formula and Wrap-around

Hashing and Collision Resolution: Solved Questions with Step-by-Step Explanations (5 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit