Hash Tables and Collision Resolution Practice Questions for GATE DA

Solve 126+ Hash Tables and Collision Resolution practice questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Hash Tables and Collision Resolution

Chapter Roadmap

Hash Tables and Collision Resolution

Master the art of mapping keys to indices and resolving the inevitable collisions with mathematical precision.

Your Learning Journey

Topic 1

Open Addressing and Linear Probing

Keep all elements inside the table. Resolve collisions by probing the next available slot sequentially.

Topic 2

Uniform Hashing and Probe Complexity

Analyze the expected number of probes for successful and unsuccessful searches using probabilistic models.

Open Addressing and Linear Probing

Data Structures > Hash Tables

Open Addressing and Linear Probing

What happens when two keys hash to the same index? Open addressing finds them a new home within the same table.

What you will learn here

Open Addressing

Keeping all elements strictly inside the hash table array.

Linear Probing

Resolving collisions by sequentially checking the next slots.

Tracing and Traps

Step-by-step insertion and avoiding primary clustering.

Hash Tables and Collision Resolution: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

Match the operations with their corresponding expected number of probes for a hash table with load factor $α$ .

List I (Operation):

P. Unsuccessful Search

Q. Insertion

R. Successful Search

List II (Formula):

$\frac{1}{1 - α}$
$\frac{1}{α} ln (\frac{1}{1 - α})$

A.
P-1, Q-1, R-2
B.
P-1, Q-2, R-1
C.
P-2, Q-1, R-1
D.
P-1, Q-2, R-2

Correct Answer:

Step-by-Step Solution

Key idea: This is a match-the-following question testing your ability to map hash table operations to their correct probe complexity formulas.

Step 1: Unsuccessful Search (P). Probing until an empty slot is found. Formula: $\frac{1}{1 - α}$ . Matches 1.

Step 2: Insertion (Q). Probing until an empty slot is found to place the new element. This is identical to an unsuccessful search. Formula: $\frac{1}{1 - α}$ . Matches 1.

Step 3: Successful Search (R). Searching for a key already in the table. Formula: $\frac{1}{α} ln (\frac{1}{1 - α})$ . Matches 2.

Final mapping: P-1, Q-1, R-2.

Common trap: A student might misread the condition for insertion and think it requires a successful search formula, matching Q with 2.

Answer: P-1, Q-1, R-2

Question 2 · Programming, Data Structures and Algorithms MCQ

For a hash table of size $m$ using linear probing, what is the formula for the $i$ -th probe index for a key $x$ , given the base hash function $h (x)$ ?

A.
$(h (x) im es i) (mod m)$
B.
$(h (x) + i^{2}) (mod m)$
C.
$(h (x) + i) (mod m)$
D.
$(h (x) - i) (mod m)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the linear probing formula.

Step 1: Recall that linear probing resolves collisions by checking the next sequential slot.

Step 2: The formula for the $i$ -th probe is the base hash plus the probe number $i$ , all modulo the table size $m$ .

Step 3: This matches $(h (x) + i) (mod m)$ .

Answer: C

Question 3 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason:

Assertion (A): In the worked example with $m = 10$ and $h (x) = 3 x (mod 10)$ , the key 14 is stored at index 4.

Reason (R): The initial hash of 14 is 2, and slots 2 and 3 are occupied.

A.
Both A and R are true, and R is the correct explanation of A.
B.
Both A and R are true, but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the worked example of linear probing.

Step 1: Verify Assertion (A). For key 14, $h (14) = 3 \times 14 (mod 10) = 42 (mod 10) = 2$ . Slot 2 is occupied by key 4. Probe slot 3, occupied by key 1. Probe slot 4, which is empty. So key 14 is stored at index 4. Assertion (A) is true.

Step 2: Verify Reason (R). The initial hash of 14 is indeed 2. Slots 2 and 3 are occupied (by keys 4 and 1, respectively). Reason (R) is true.

Step 3: Check if (R) explains (A). Yes, (R) correctly explains why key 14 ends up at index 4: it hashes to 2, finds slots 2 and 3 occupied, and probes to slot 4.

Both (A) and (R) are true, and (R) is the correct explanation of (A).

Common trap: A student might compute the hash as 42 (forgetting modulo) and think (R) is false. This is a unit mismatch error (not applying modulo).

Answer: A

Question 4 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason:

Assertion (A): The expected number of probes for inserting a new element into a hash table with load factor $α = 0.5$ is 2.

Reason (R): Insertion requires finding an empty slot, which is mathematically identical to an unsuccessful search, given by $\frac{1}{1 - α}$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the conceptual link between insertion and unsuccessful search complexities.

Step 1: Verify Assertion (A). The expected probes for insertion with $α = 0.5$ is calculated using the unsuccessful search formula: $E = \frac{1}{1 - α} = \frac{1}{1 - 0.5} = \frac{1}{0.5} = 2$ . Assertion (A) is true.

Step 2: Verify Reason (R). Insertion requires probing until an empty slot is found. This is the exact definition of an unsuccessful search (probing until an empty slot is found to conclude the key is absent). Thus, the formulas are identical. Reason (R) is true.

Step 3: Check if (R) explains (A). Yes, (R) correctly identifies that insertion is identical to an unsuccessful search, which is the exact reason why the formula $\frac{1}{1 - α}$ yields 2 for $α = 0.5$ .

Both (A) and (R) are true, and (R) is the correct explanation of (A).

Common trap: A student might confuse insertion with a successful search, thinking (R) is false because "insertion is a successful operation". This is a unit mismatch of operation types.

Answer: A

Question 5 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason:

Assertion (A): For a hash table with load factor $α = 0.5$ , the expected number of probes for a successful search is 2.

Reason (R): The successful search formula is $\frac{1}{α} ln (\frac{1}{1 - α})$ , which for $α = 0.5$ gives $2 ln (2) \approx 1.39$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing the successful search formula and calculation.

Step 1: Evaluate Assertion (A). For $α = 0.5$ , the expected probes for successful search is:

$E = \frac{1}{0.5} ln (\frac{1}{1 - 0.5}) = 2 ln (2) \approx 2 \times 0.693 = 1.386$

The assertion claims $E = 2$ , which is incorrect. A is FALSE.

Step 2: Evaluate Reason (R). The formula $\frac{1}{α} ln (\frac{1}{1 - α})$ is correct, and the calculation $2 ln (2) \approx 1.39$ is also correct. R is TRUE.

Step 3: Since A is false and R is true, the answer is D.

Common trap: A unit mismatch error occurs if you confuse successful search with unsuccessful search. For $α = 0.5$ , unsuccessful search gives $\frac{1}{1 - 0.5} = 2$ , which matches the assertion. But the question is about successful search.

Question 6 · Programming, Data Structures and Algorithms MCQ

When deleting a key from a hash table that uses linear probing, why is it insufficient to simply mark the slot as completely empty?

A.
It would change the hash function for all remaining keys.
B.
It would immediately trigger a full rehashing of the table.
C.
It would cause the hash table size to decrease automatically.
D.
It would break the probe chain for other keys that collided and were placed further down.

Correct Answer:

Step-by-Step Solution

Key idea: This is a concept recall question about the deletion trap in linear probing.

Step 1: In linear probing, a key that collides is placed in the next available slot.

Step 2: Searching for that key involves probing sequentially from its base hash until the key is found or an empty slot is encountered.

Step 3: If a deleted slot is marked as completely empty, a subsequent search for a key that was placed after it will incorrectly terminate at this "empty" slot, failing to find the key.

Step 4: Therefore, we must use a "tombstone" (deleted marker) instead of a truly empty marker to preserve the probe chain.

Answer: D

Question 7 · Programming, Data Structures and Algorithms MCQ

When inserting keys into a linear probing hash table of size $m = 10$ , what is the minimum number of probes needed to insert a key if the table already has 5 elements?

A.
0
B.
1
C.
5
D.
6

Correct Answer:

Step-by-Step Solution

Key idea: This is a minimum probe count question for linear probing.

Step 1: The table has 5 elements, so 5 slots are occupied and 5 are empty.

Step 2: In the best case, the key hashes directly to an empty slot on the first probe.

Step 3: Minimum probes = 1 (the initial probe finds an empty slot).

The minimum number of probes is 1.

Common trap: A student might think the answer is 5, assuming you need to probe past all existing elements. This ignores the constraint that the key might hash directly to an empty slot.

Answer: 1

Question 8 · Programming, Data Structures and Algorithms MCQ

Match the keys with their final indices in a linear probing hash table of size $m = 10$ with $h (x) = 3 x (mod 10)$ , after inserting keys 2, 5, 12 in that order.

List I (Keys): 2, 5, 12

List II (Indices): 6, 5, 7

A.
2-6, 5-5, 12-7
B.
2-7, 5-6, 12-5
C.
2-6, 5-7, 12-5
D.
2-5, 5-6, 12-7

Correct Answer:

Step-by-Step Solution

Key idea: This is a match-the-following question testing the final indices after insertion with linear probing.

Step 1: Insert key 2. $h (2) = 3 \times 2 (mod 10) = 6 (mod 10) = 6$ . Slot 6 is empty. Key 2 is at index 6.

Step 2: Insert key 5. $h (5) = 3 \times 5 (mod 10) = 15 (mod 10) = 5$ . Slot 5 is empty. Key 5 is at index 5.

Step 3: Insert key 12. $h (12) = 3 \times 12 (mod 10) = 36 (mod 10) = 6$ . Slot 6 is occupied by key 2. Probe slot 7, which is empty. Key 12 is at index 7.

Final mapping: 2-6, 5-5, 12-7.

Common trap: A student might not probe correctly for key 12, thinking it goes to index 5 or 6 without checking for collisions. This is a misread condition error.

Answer: 2-6, 5-5, 12-7

Question 9 · Programming, Data Structures and Algorithms MCQ

The expected number of probes for a successful search in a hash table with load factor $α$ is $\frac{1}{α} ln (\frac{1}{1 - α})$ . What is the minimum possible value of this expected number of probes as the table becomes very sparse ( $α \to 0$ )?

A.
0
B.
1
C.
e
D.
\infty

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question testing the limit of the successful search formula as the load factor approaches 0.

Step 1: The formula for the expected number of probes in a successful search is $E = \frac{1}{α} ln (\frac{1}{1 - α}) = \frac{- l n ( 1 - α )}{α}$ .

Step 2: As $α \to 0$ , both the numerator $- ln (1 - α)$ and the denominator $α$ approach 0. This is a $\frac{0}{0}$ indeterminate form.

Step 3: Apply L'Hôpital's rule. The derivative of the numerator with respect to $α$ is $\frac{1}{1 - α}$ . The derivative of the denominator is 1.

Step 4: Evaluate the limit as $α \to 0$ :

$lim_{α \to 0} \frac{\frac{1}{1 - α}}{1} = \frac{1}{1 - 0} = 1$ .

Common trap: A student might ignore the constraint that you always need at least 1 probe to check a slot, and incorrectly guess 0 because $α \to 0$ .

Answer: 1

Question 10 · Programming, Data Structures and Algorithms MCQ

Consider the following statements about hash table probe complexity under uniform hashing:

P: The expected probes for successful search is $\frac{1}{α} ln (\frac{1}{1 - α})$ .

Q: This formula is valid for all $α \geq 0$ .

R: For $α = 0.5$ , the expected probes for successful search is less than for unsuccessful search.

Which of the statements are true?

A.
P only
B.
P and Q only
C.
P and R only
D.
P, Q, and R

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement truth question testing the successful search formula and its constraints.

Step 1: Evaluate statement P. The formula $\frac{1}{α} ln (\frac{1}{1 - α})$ is the standard formula for successful search under uniform hashing. P is TRUE.

Step 2: Evaluate statement Q. The formula requires $α > 0$ (to avoid division by zero in $\frac{1}{α}$ ) and $α < 1$ (to avoid $ln$ of negative or undefined values). At $α = 0$ , the formula is undefined. Q is FALSE.

Step 3: Evaluate statement R. For $α = 0.5$ :

Successful search: $\frac{1}{0.5} ln (\frac{1}{0.5}) = 2 ln (2) \approx 2 \times 0.693 = 1.386$
Unsuccessful search: $\frac{1}{1 - 0.5} = 2$
Since $1.386 < 2$ , R is TRUE.

Answer: P and R only (C)

Common trap: Ignoring the constraint that $α = 0$ makes the formula undefined, leading to the incorrect belief that Q is true.

Try a question

Login to view the complete practice 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

Hash Tables and Collision Resolution Practice Questions for GATE DA

Chapter Roadmap: Hash Tables and Collision Resolution

Hash Tables and Collision Resolution

Your Learning Journey

Open Addressing and Linear Probing

Open Addressing and Linear Probing

What you will learn here

Hash Tables and Collision Resolution: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit