Hash Tables and Collision Resolution Practice Questions for GATE DA: 5+ Solved Questions with Step-by-Step Solutions

Solve 5+ 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 (5 Problems)

Question 1 · 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 2 · 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 3 · Programming, Data Structures and Algorithms MCQ

In a hash table that uses open addressing for collision resolution, where are the elements stored?

A.
In external linked lists attached to the array
B.
Strictly inside the hash table array
C.
In a separate overflow file
D.
In a dynamically allocated tree structure

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct definition recall question about open addressing.

Step 1: Recall the definition of open addressing. In open addressing, all elements are stored strictly inside the hash table array itself.

Step 2: Contrast this with separate chaining, which uses external linked lists.

Answer: B

Question 4 · Programming, Data Structures and Algorithms MCQ

What is the term for the phenomenon in linear probing where contiguous blocks of occupied slots form, causing subsequent insertions to take longer?

A.
Primary clustering
B.
Secondary clustering
C.
Hash flooding
D.
Load factor overflow

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct definition recall question about a specific performance degradation phenomenon in linear probing.

Step 1: Recall that linear probing checks sequential slots.

Step 2: When multiple keys hash to nearby indices, they merge into a single large contiguous block of occupied slots.

Step 3: This specific phenomenon is called "primary clustering". It increases the average probe length for both successful and unsuccessful searches.

Answer: A

Question 5 · Programming, Data Structures and Algorithms MCQ

In a hash table of size $m = 10$ using linear probing, if a collision occurs and the current probe is at index $9$ , what is the next index that will be probed?

A.
$10$
B.
$0$
C.
$1$
D.
$8$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the linear probing formula with wrap-around.

Step 1: The linear probing formula is $h_{i} (x) = (h (x) + i) (mod m)$ .

Step 2: The modulo $m$ operation ensures that when the probe reaches the end of the array (index $m - 1$ ), it wraps around to the beginning (index $0$ ).

Step 3: Here, $m = 10$ . The next index after $9$ is $(9 + 1) (mod 10) = 10 (mod 10) = 0$ .

Answer: B

A question from this chapter

Question 1

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

Question 2

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

Question 3

In a hash table that uses open addressing for collision resolution, where are the elements stored?

Question 4

What is the term for the phenomenon in linear probing where contiguous blocks of occupied slots form, causing subsequent insertions to take longer?

Question 5

In a hash table of size m = 10 using linear probing, if a collision occurs and the current probe is at index 9, what is the next index that will be probed?

Free preview ends here

Login to view the complete practice questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Hash Tables and Collision Resolution Practice Questions for GATE DA: 5+ Solved Questions with Step-by-Step Solutions

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 (5 Problems)

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

A question from this chapter

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