Hash Tables and Collision Resolution Previous Year Questions (PYQs) for GATE DA: 2+ Solved Questions with Step-by-Step Solutions

Solve 2+ Hash Tables and Collision Resolution previous year 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 (2 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

Consider a hash table of size

10

with indices

{0, 1, ..., 9}

, with the hash function

h (x) = 3 x (mod 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

A.
$2$ and $5$
B.
$2$ and $6$
C.
$4$ and $5$
D.
$4$ and $6$

Correct Answer:

Step-by-Step Solution

Key idea: This is a hash table tracing question, recognizable because it provides a specific hash function, collision resolution strategy, and a sequence of keys to insert.

Step 1: Understand the hash function and table size. The table has size 10 (indices 0 to 9). The hash function is $h (x) = 3 x (mod 10)$ .

Step 2: Trace the insertion of each key sequentially using linear probing.

Insert 1: $h (1) = 3 (1) (mod 10) = 3$ . Index 3 is empty. Place 1 at index 3.
Insert 4: $h (4) = 3 (4) (mod 10) = 12 (mod 10) = 2$ . Index 2 is empty. Place 4 at index 2.
Insert 5: $h (5) = 3 (5) (mod 10) = 15 (mod 10) = 5$ . Index 5 is empty. Place 5 at index 5.
Insert 6: $h (6) = 3 (6) (mod 10) = 18 (mod 10) = 8$ . Index 8 is empty. Place 6 at index 8.
Insert 14: $h (14) = 3 (14) (mod 10) = 42 (mod 10) = 2$ . Index 2 is occupied (by 4).
Probe 1: $(2 + 1) (mod 10) = 3$ . Index 3 is occupied (by 1).
Probe 2: $(3 + 1) (mod 10) = 4$ . Index 4 is empty. Place 14 at index 4.
Insert 15: $h (15) = 3 (15) (mod 10) = 45 (mod 10) = 5$ . Index 5 is occupied (by 5).
Probe 1: $(5 + 1) (mod 10) = 6$ . Index 6 is empty. Place 15 at index 6.

Step 3: Identify the final indices. Key 14 is at index 4, and key 15 is at index 6.

Answer: D

Question 2 · Programming, Data Structures and Algorithms MCQ

Consider performing uniform hashing on an open address hash table with load
factor

α = \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 - α}

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

A.
$ln (\frac{1}{1 - α})$
B.
$\frac{1}{1 - α}$
C.
$1 + \frac{α}{2}$
D.
$\frac{1}{1 + α}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a probe complexity question, recognizable because it asks for the expected number of probes for a specific hash table operation under the uniform hashing assumption.

Step 1: Recall the mechanics of insertion in open addressing. To insert a new element, the algorithm must find an empty slot in the hash table.

Step 2: Relate insertion to search operations. Finding an empty slot is logically identical to an unsuccessful search, which probes sequentially until it finds an empty slot (indicating the key is not present).

Step 3: Apply the uniform hashing formula. The problem states that the expected number of probes for an unsuccessful search is at most $\frac{1}{1 - α}$ .

Step 4: Conclude the complexity. Since the insertion process requires exactly the same probing sequence as an unsuccessful search, its expected number of probes is also $\frac{1}{1 - α}$ .

Answer: B

A question from this chapter

Question 1

Consider a hash table of size 10 with indices {0, 1, ..., 9}, with the hash function h (x) = 3 x (mod 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

Question 2

Consider performing uniform hashing on an open address hash table with load factor α = \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 - α} . Inserting an element in this hash table requires at most ______ probes, on average.

Free preview ends here

Login to view the complete previous-year 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 Previous Year Questions (PYQs) for GATE DA: 2+ 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 (2 Problems)

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit

A question from this chapter

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