Hash Tables and Collision Resolution Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

Hash Tables and Collision Resolution notes for GATE DA: 22 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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.

Open Addressing: Finding a Home in the Same Table

Core Concept

Open Addressing: Finding a Home in the Same Table

Unlike separate chaining, where collisions create linked lists outside the table, open addressing keeps all elements strictly inside the hash table array.

When a collision occurs, we probe (search) for the next available empty slot within the table itself.

The Probe Sequence

The probe sequence is defined by a function $h (x, i)$ which gives the index to check on the $i$ -th probe.

$h (x, 0)$ is the initial hash.
If occupied, we check $h (x, 1)$ , then $h (x, 2)$ , and so on.
We stop when we find an empty slot or exhaust the table.

Core Principle

Every element resides directly in the array. There are no external pointers or linked nodes.

Linear Probing: The Simplest Probe Sequence

Core Concept

Linear Probing: The Simplest Probe Sequence

Linear probing is the most straightforward open addressing technique. If a collision occurs at index $h (x)$ , we simply check the next index: $(h (x) + 1) (mod m)$ , then $(h (x) + 2) (mod m)$ , and so on, wrapping around to the beginning of the table if we reach the end.

The Formula

h_{i} (x) = (h (x) + i) (mod m) for i = 0, 1, 2, \dots

How it Works

Calculate the initial index $h (x)$ .
If the slot is empty, insert the key.
If the slot is occupied, move to the next index sequentially: $+ 1, + 2, + 3 \dots$
Wrap around using modulo $m$ when you reach the end of the array.

Hash Tables and Collision Resolution: Solved Questions with Step-by-Step Explanations (2 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

More notes in this unit

chapter

Hash Tables and Collision Resolution Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

Hash Tables and Collision Resolution notes for GATE DA: 22 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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?

Free preview ends here

Login to view the complete notes

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