Collision Handling Using Chaining in DSA C++ - Execution Trace

Concept Flow - Collision Handling Using Chaining

Insert key

↓

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

Yes→Create new linked list with key

↓

Insert key

↓

Bucket not empty?

No→Traverse linked list

↓

Insert key at list end

↓

Done

When inserting a key, compute its hash index. If the bucket is empty, create a new linked list and insert the key. If not, add the key at the end of the existing linked list to handle collisions.

Execution Sample

DSA C++

hashTable[hash(key)].push_back(key);

Insert a key into the hash table using chaining by adding it to the linked list at the computed hash index.

Execution Table

Step	Operation	Hash Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert key=10	10 % 5 = 0	[]	Create new list with 10	[10]	0: 10 -> null 1: null 2: null 3: null 4: null
2	Insert key=15	15 % 5 = 0	[10]	Add 15 at end	[10, 15]	0: 10 -> 15 -> null 1: null 2: null 3: null 4: null
3	Insert key=7	7 % 5 = 2	[]	Create new list with 7	[7]	0: 10 -> 15 -> null 1: null 2: 7 -> null 3: null 4: null
4	Insert key=20	20 % 5 = 0	[10, 15]	Add 20 at end	[10, 15, 20]	0: 10 -> 15 -> 20 -> null 1: null 2: 7 -> null 3: null 4: null
5	Insert key=12	12 % 5 = 2	[7]	Add 12 at end	[7, 12]	0: 10 -> 15 -> 20 -> null 1: null 2: 7 -> 12 -> null 3: null 4: null
6	Insert key=5	5 % 5 = 0	[10, 15, 20]	Add 5 at end	[10, 15, 20, 5]	0: 10 -> 15 -> 20 -> 5 -> null 1: null 2: 7 -> 12 -> null 3: null 4: null
7	Insert key=3	3 % 5 = 3	[]	Create new list with 3	[3]	0: 10 -> 15 -> 20 -> 5 -> null 1: null 2: 7 -> 12 -> null 3: 3 -> null 4: null
8	Insert key=8	8 % 5 = 3	[3]	Add 8 at end	[3, 8]	0: 10 -> 15 -> 20 -> 5 -> null 1: null 2: 7 -> 12 -> null 3: 3 -> 8 -> null 4: null
9	Insert key=25	25 % 5 = 0	[10, 15, 20, 5]	Add 25 at end	[10, 15, 20, 5, 25]	0: 10 -> 15 -> 20 -> 5 -> 25 -> null 1: null 2: 7 -> 12 -> null 3: 3 -> 8 -> null 4: null
10	Insert key=14	14 % 5 = 4	[]	Create new list with 14	[14]	0: 10 -> 15 -> 20 -> 5 -> 25 -> null 1: null 2: 7 -> 12 -> null 3: 3 -> 8 -> null 4: 14 -> null
11	End	-	-	-	-	Insertion complete

💡 All keys inserted; chaining handled collisions by linked lists at buckets.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
hashIndex	-	0	0	2	0	2	0	3	3	0	4	-
bucket[0]	[]	[10]	[10, 15]	[10, 15]	[10, 15, 20]	[10, 15, 20]	[10, 15, 20, 5]	[10, 15, 20, 5]	[10, 15, 20, 5]	[10, 15, 20, 5, 25]	[10, 15, 20, 5, 25]	[10, 15, 20, 5, 25]
bucket[2]	[]	[]	[]	[7]	[7]	[7, 12]	[7, 12]	[7, 12]	[7, 12]	[7, 12]	[7, 12]	[7, 12]
bucket[3]	[]	[]	[]	[]	[]	[]	[]	[3]	[3, 8]	[3, 8]	[3, 8]	[3, 8]
bucket[4]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[]	[14]	[14]

Key Moments - 3 Insights

Why do we add keys to the end of the linked list in the bucket?

Adding keys at the end preserves insertion order and avoids overwriting existing keys, as shown in steps 2, 4, 6, 8, and 9 in the execution_table.

What happens if the bucket is empty when inserting a key?

A new linked list is created with the key as its first node, as seen in steps 1, 3, 7, and 10 where empty buckets become lists with one element.

How does chaining handle collisions?

When multiple keys hash to the same index, they are stored in a linked list at that bucket, preventing overwriting and allowing multiple keys, as shown in bucket 0 with keys 10, 15, 20, 5, and 25.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the state of bucket 0 after inserting key 20?

A [10, 15, 20]

B [10, 20]

C [20]

D [15, 20]

💡 Hint

Check the 'Bucket State After' column at step 4 in the execution_table.

At which step does bucket 3 first get a key inserted?

A Step 3

B Step 8

C Step 7

D Step 10

💡 Hint

Look at the 'Hash Index' and 'Bucket State After' columns for bucket 3 in the execution_table.

If we insert a key 30, what would be its hash index and where would it be inserted?

A Index 0, new list created

B Index 0, added at end of bucket 0 list

C Index 1, new list created

D Index 2, added at end of bucket 2 list

💡 Hint

Calculate 30 % 5 and check bucket 0's current state in variable_tracker.

Concept Snapshot

Collision Handling Using Chaining:
- Use a hash function to find bucket index.
- Each bucket holds a linked list of keys.
- If collision occurs, add key to linked list at bucket.
- Insert at end to preserve order.
- Allows multiple keys per bucket without overwriting.

Full Transcript

Collision handling using chaining stores multiple keys that hash to the same index in a linked list at that bucket. When inserting a key, the hash index is computed. If the bucket is empty, a new linked list is created with the key. If not, the key is added at the end of the existing linked list. This prevents overwriting keys and handles collisions efficiently. The execution table shows step-by-step insertion of keys, updating bucket states and linked lists. Variable tracking shows how each bucket's list grows. Key moments clarify why keys are added at the end and how empty buckets are handled. The visual quiz tests understanding of bucket states and insertion steps.

Practice

1. What is the main idea behind collision handling using chaining in hash tables?

easy

A. Store all elements that hash to the same index in a linked list at that index

B. Resize the hash table when a collision occurs

C. Use a second hash function to find a new index

D. Ignore collisions and overwrite existing data

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain chaining method

   Chaining stores all collided elements in a linked list at that index to keep them separate.

3. Final Answer:

   Store all elements that hash to the same index in a linked list at that index -> Option A

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at each hash index [OK]

Common Mistakes:

• Thinking chaining resizes the table
• Confusing chaining with open addressing
• Ignoring collisions instead of handling them

2. Which of the following is the correct way to declare a hash table using chaining in C++?

easy

A. std::vector<int> hashTable(size);

B. std::list hashTable(size);

C. std::vector hashTable(size);

D. std::list<int> hashTable(size);

Solution

1. Step 1: Understand chaining data structure

   Chaining uses a list at each index, so a vector of lists is needed.

2. Step 2: Check syntax correctness

   std::vector creates a vector where each element is a list, perfect for chaining.

3. Final Answer:

   std::vector hashTable(size); -> Option C

4. Quick Check:

   Vector of lists = chaining hash table [OK]

Hint: Chaining = vector of lists in C++ [OK]

Common Mistakes:

• Using list of vectors instead of vector of lists
• Using vector of ints only (no chaining)
• Incorrect container nesting order

3. Consider the following code snippet using chaining for collision handling:

std::vector hashTable(5);
int hashFunction(int key) { return key % 5; }

// Insert keys
hashTable[hashFunction(7)].push_back(7);
hashTable[hashFunction(12)].push_back(12);
hashTable[hashFunction(17)].push_back(17);

// Print contents at index 2
for (int val : hashTable[2]) {
    std::cout << val << " ";
}

What will be the output?

medium

A. 7 12 17

B. 12 17

C. 7

D. No output

Solution

1. Step 1: Calculate hash indices for keys

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys go to index 2.

2. Step 2: Check what is printed at index 2

   All three keys (7, 12, 17) are stored in the list at index 2 and printed in insertion order.

3. Final Answer:

   7 12 17 -> Option A

4. Quick Check:

   Keys mod 5 = 2, print all at index 2 [OK]

Hint: Calculate key % size to find index [OK]

Common Mistakes:

• Forgetting all keys collide at index 2
• Printing keys at wrong index
• Assuming keys overwrite each other

4. The following code attempts to insert keys into a hash table using chaining but causes a runtime error:

std::vector hashTable;
int hashFunction(int key) { return key % 10; }

void insertKey(int key) {
    int index = hashFunction(key);
    hashTable[index].push_back(key);
}

int main() {
    insertKey(15);
    insertKey(25);
    return 0;
}

What is the error and how to fix it?

medium

A. hashFunction returns wrong index; change modulo to 5

B. hashTable is empty; initialize with size before insertions

C. push_back is wrong method; use insert instead

D. No error; code runs fine

Solution

1. Step 1: Identify cause of runtime error

   hashTable is declared but not sized, so accessing hashTable[index] causes out-of-range error.

2. Step 2: Fix by initializing hashTable size

   Initialize hashTable with size 10 (e.g., std::vector hashTable(10);) before insertions.

3. Final Answer:

   hashTable is empty; initialize with size before insertions -> Option B

4. Quick Check:

   Vector size must match hash range [OK]

Hint: Initialize vector size before accessing indices [OK]

Common Mistakes:

• Ignoring vector size causes crash
• Changing hash function unnecessarily
• Using wrong list methods

5. You have a hash table of size 7 using chaining. You insert keys: 10, 21, 17, 14, 28, 35.
After all insertions, which index will have the longest chain and what will be its contents?
Use hash function: index = key % 7.

hard

A. Index 0: 10 -> 21 -> 35

B. Index 3: 10 -> 17

C. Index 4: 21 -> 14

D. Index 0: 21 -> 14 -> 28 -> 35

Solution

1. Step 1: Calculate hash indices for each key

   10 % 7 = 3, 21 % 7 = 0, 17 % 7 = 3, 14 % 7 = 0, 28 % 7 = 0, 35 % 7 = 0.

2. Step 2: Group keys by index

   Index 0: 21, 14, 28, 35 (4 keys); Index 3: 10, 17 (2 keys).

3. Step 3: Identify longest chain and contents

   Index 0 has the longest chain with keys 21, 14, 28, 35 inserted in order.

4. Final Answer:

   Index 0: 21 -> 14 -> 28 -> 35 -> Option D

5. Quick Check:

   Keys mod 7 grouped; longest chain at index 0 [OK]

Hint: Calculate key % size, count keys per index [OK]

Common Mistakes:

• Miscomputing modulo results
• Mixing up indices and keys
• Ignoring insertion order in chain