chapter

Hash Tables and Collision Resolution Short Notes for GATE DA

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

hash tables and collision resolution short notes

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 .

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

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 - α})

Question 2

Level 1: Warm-up

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 3

Level 1: Warm-up

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.

Question 4

Level 1: Warm-up

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 - α} .

Question 5

Level 1: Warm-up

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 .

Question 6

Level 1: Warm-up

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 7

Level 1: Warm-up

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?

Question 8

Level 1: Warm-up

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

Question 9

Level 1: Warm-up

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

Question 10

Level 1: Warm-up

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?

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

Hash Tables and Collision Resolution Short Notes for GATE DA

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 (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.

hash tables and collision resolution short notes

Quick Revision: Open Addressing and Linear Probing

Key Takeaways

Quick Revision: Probe Complexities

Probe Complexities

Try a question

Login to view the complete short notes

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 Short Notes for GATE DA

Quick Revision: Open Addressing and Linear Probing

Key Takeaways

Quick Revision: Probe Complexities

Probe Complexities

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