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#

LinkedList<int>[] hashTable = new LinkedList<int>[5];
Insert(7);
Insert(12);
Insert(17);

Insert keys 7, 12, and 17 into a hash table of size 5 using chaining to handle collisions.

Execution Table

Step	Operation	Hash Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert 7	7 % 5 = 2	Empty	Create new linked list at index 2; Insert 7	[7]	[null, null, 7 -> null, null, null]
2	Insert 12	12 % 5 = 2	[7]	Traverse list at index 2; Insert 12 at end	[7 -> 12]	[null, null, 7 -> 12 -> null, null, null]
3	Insert 17	17 % 5 = 2	[7 -> 12]	Traverse list at index 2; Insert 17 at end	[7 -> 12 -> 17]	[null, null, 7 -> 12 -> 17 -> null, null, null]
4	End	-	[7 -> 12 -> 17]	-	[7 -> 12 -> 17]	[null, null, 7 -> 12 -> 17 -> null, null, null]

💡 All keys inserted; chaining handled collisions at index 2.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hashTable[2]	null	[7]	[7 -> 12]	[7 -> 12 -> 17]	[7 -> 12 -> 17]
LinkedList at index 2 size	0	1	2	3	3

Key Moments - 3 Insights

Why do we insert new keys at the end of the linked list in the bucket?

In the execution_table rows 2 and 3, we see traversal happens before insertion. This ensures keys are added at the end to preserve insertion order and avoid overwriting existing keys.

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

As shown in step 1 of the execution_table, if the bucket is empty, a new linked list is created and the key is inserted as the first node.

Why do all keys 7, 12, and 17 end up in the same bucket?

Because their hash index calculation (key % 5) results in 2 for all three keys, causing them to collide and be stored in the linked list at index 2, as shown in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the bucket state after inserting key 12?

A [7 -> 12]

B [12]

C [7]

D Empty

💡 Hint

Refer to execution_table row 2 under 'Bucket State After' column.

At which step does the linked list at index 2 first get created?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Check execution_table row 1 'Pointer Changes' for linked list creation.

If we insert key 3 instead of 17, which bucket will it go to?

A Index 2

B Index 0

C Index 3

D Index 1

💡 Hint

Calculate 3 % 5 and check execution_table for bucket indexing.

Concept Snapshot

Collision Handling Using Chaining:
- Use a linked list at each bucket to store multiple keys.
- Compute hash index: index = key % table_size.
- If bucket empty, create new list and insert key.
- If bucket not empty, append key to linked list.
- Handles collisions by chaining keys in the same bucket.

Full Transcript

Collision Handling Using Chaining stores multiple keys in the same bucket using linked lists. When inserting a key, we compute its hash index by taking the key modulo the table size. If the bucket at that index is empty, we create a new linked list and insert the key. If not, we traverse the linked list and add the key at the end. This way, keys that hash to the same index are chained together, preventing data loss. The example inserts keys 7, 12, and 17 into a hash table of size 5. All three keys hash to index 2, so they are stored in a linked list at that bucket. This method efficiently handles collisions by chaining keys in linked lists.

Practice

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

easy

A. Replace the existing element with the new one

B. Resize the hash table immediately when collision occurs

C. Store collided elements in a linked list at the same index

D. Ignore the new element causing collision

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index.

3. Final Answer:

   Store collided elements in a linked list at the same index -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at one index [OK]

Common Mistakes:

• Thinking chaining replaces old elements
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following is the correct way to declare a hash table with chaining in C# using List<T> for chaining?

easy

A. Dictionary hashTable = new Dictionary();

B. Dictionary hashTable = new Dictionary();

C. List hashTable = new List();

D. Dictionary hashTable = new Dictionary();

Solution

1. Step 1: Understand chaining data structure

   Chaining uses a list to store multiple values per key index.

2. Step 2: Correct C# syntax for dictionary with list values

   Dictionary means keys are int, values are lists of strings.

3. Final Answer:

   Dictionary hashTable = new Dictionary(); -> Option D

4. Quick Check:

   Dictionary with List values = Dictionary hashTable = new Dictionary(); [OK]

Hint: Use Dictionary with List as value for chaining [OK]

Common Mistakes:

• Using List with two generic types (invalid)
• Using Dictionary with simple string values only
• Confusing key and value types

3. What will be the output of the following C# code snippet using chaining?

var hashTable = new Dictionary();
int key = 2;
if (!hashTable.ContainsKey(key))
    hashTable[key] = new List<string>();
hashTable[key].Add("apple");
hashTable[key].Add("banana");

foreach(var item in hashTable[key])
    Console.Write(item + " ");

medium

A. No output

B. apple banana

C. apple

D. banana apple

Solution

1. Step 1: Initialize dictionary and add list for key 2

   Since key 2 is not present, a new list is created and assigned.

2. Step 2: Add "apple" and "banana" to list at key 2

   Both strings are added in order: "apple", then "banana".

3. Step 3: Print all items in list at key 2

   Loop prints "apple " then "banana " in order.

4. Final Answer:

   apple banana -> Option B

5. Quick Check:

   List order preserved = apple banana [OK]

Hint: Items print in insertion order in chaining list [OK]

Common Mistakes:

• Assuming reversed order output
• Forgetting to initialize list before adding
• Expecting no output if key missing

4. Identify the error in this C# code snippet implementing chaining:

var hashTable = new Dictionary();
int key = 5;
hashTable[key].Add("orange");

medium

A. Key does not exist; list not initialized before Add

B. Dictionary cannot have List as value type

C. Add method does not exist for List

D. Key must be string, not int

Solution

1. Step 1: Check if key 5 exists in dictionary

   Key 5 is not added yet, so hashTable[key] is null.

2. Step 2: Adding to null list causes runtime error

   Cannot call Add on null; list must be initialized first.

3. Final Answer:

   Key does not exist; list not initialized before Add -> Option A

4. Quick Check:

   Initialize list before Add [OK]

Hint: Always initialize list before adding elements [OK]

Common Mistakes:

• Assuming dictionary auto-creates lists
• Confusing key types
• Thinking Add method is invalid

5. You want to implement a hash table with chaining in C# that stores multiple values per key and supports removing a specific value from the chain. Which approach correctly supports this feature?

hard

A. Use Dictionary and call Remove(value) on the list at the key

B. Use Dictionary and overwrite value to remove

C. Use Dictionary but clear entire list to remove one value

D. Use Dictionary but do not implement removal

Solution

1. Step 1: Understand chaining with multiple values per key

   Chaining uses a list to hold multiple values at one key.

2. Step 2: Removing a specific value requires list's Remove method

   List<string> supports Remove(value) to delete one item without affecting others.

3. Step 3: Other options either overwrite or clear all values, not specific removal

   Overwriting loses all values; clearing removes all; ignoring removal is incomplete.

4. Final Answer:

   Use Dictionary and call Remove(value) on the list at the key -> Option A

5. Quick Check:

   List Remove supports specific value deletion [OK]

Hint: Use List and Remove(value) to delete specific chained item [OK]

Common Mistakes:

• Overwriting value instead of removing one
• Clearing entire list to remove one item
• Ignoring removal feature