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

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

Quick Revision: Open Addressing and Linear Probing

Quick Revision

Key Takeaways

1. Open Addressing

All elements reside strictly inside the hash table array.
No external linked lists or pointers.

2. Linear Probing

Resolves collisions by checking the next sequential slot.
Formula: $h_{i} (x) = (h (x) + i) (mod m)$ .
Wraps around to index 0 after reaching $m - 1$ .

3. Deletion Trap

Cannot mark deleted slots as empty.
Must use tombstones to preserve probe chains.

4. Primary Clustering

Contiguous blocks of occupied slots form clusters.
Degrades performance significantly as clusters grow.

Quick Revision: Probe Complexities

Quick Revision

Probe Complexities

1. Unsuccessful Search & Insertion

Finding an empty slot.

E [probes] = \frac{1}{1 - α}

2. Successful Search

Finding an existing key.

E [probes] = \frac{1}{α} ln (\frac{1}{1 - α})

3. Crucial Conditions

Insertion complexity equals unsuccessful search complexity.
Formulas are only valid when $α < 1$ .

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 short notes in this unit

chapter

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

Hash Tables and Collision Resolution short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questi

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 short 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