Collision Handling Using Chaining in DSA C - Execution Trace

Concept Flow - Collision Handling Using Chaining

Start: Insert key

↓

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

Yes→Create new linked list node with key

↓

Add node at head of list

↓

Traverse linked list

↓

Insert key node

↓

Done

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

Execution Sample

DSA C

hash_table = [NULL, NULL, NULL]
insert(5)
insert(8)
insert(11)

Insert keys 5, 8, and 11 into a hash table of size 3 using chaining to handle collisions.

Execution Table

Step	Operation	Hash Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert 5	5 % 3 = 2	NULL	Create node(5) at bucket[2]	Node(5) -> NULL	[NULL, NULL, 5 -> NULL]
2	Insert 8	8 % 3 = 2	5 -> NULL	Create node(8), point node(8).next to node(5), bucket[2] = node(8)	8 -> 5 -> NULL	[NULL, NULL, 8 -> 5 -> NULL]
3	Insert 11	11 % 3 = 2	8 -> 5 -> NULL	Create node(11), point node(11).next to node(8), bucket[2] = node(11)	11 -> 8 -> 5 -> NULL	[NULL, NULL, 11 -> 8 -> 5 -> NULL]
4	End	-	No more inserts	-	-	[NULL, NULL, 11 -> 8 -> 5 -> NULL]

💡 All keys inserted; chaining handled collisions by adding nodes at head of linked list in bucket 2.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
bucket[0]	NULL	NULL	NULL	NULL	NULL
bucket[1]	NULL	NULL	NULL	NULL	NULL
bucket[2]	NULL	5 -> NULL	8 -> 5 -> NULL	11 -> 8 -> 5 -> NULL	11 -> 8 -> 5 -> NULL

Key Moments - 3 Insights

Why do we add new nodes at the head of the linked list instead of the tail?

Adding at the head is faster because we don't need to traverse the list. See execution_table steps 2 and 3 where new nodes point to the previous head.

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

A new node is created and assigned directly to the bucket. See step 1 where bucket[2] was NULL before inserting 5.

How does chaining handle multiple keys hashing to the same index?

It stores all keys in a linked list at that bucket. The list grows by adding new nodes at the head, as shown in steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the bucket[2] state after inserting key 8?

A 5 -> NULL

B 11 -> 8 -> 5 -> NULL

C 8 -> 5 -> NULL

D NULL

💡 Hint

Check the 'Bucket State After' column in step 2.

At which step does the bucket[2] linked list first contain more than one node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Bucket State After' column and see when the list length changes.

If we changed the hash function to use modulo 1 instead of 3, what would happen to the bucket states?

A All keys go to bucket[0], forming a longer linked list

B Keys distribute evenly across buckets

C Buckets remain empty

D Keys go to bucket[1]

💡 Hint

Modulo 1 means all keys hash to index 0, so all nodes chain there.

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 node.
- If not, add new node at head of linked list.
- Handles collisions by chaining keys in lists.

Full Transcript

Collision handling using chaining means when two keys hash to the same index, we store them in a linked list at that index. When inserting, we compute the hash index. If the bucket is empty, we create a new node. If not, we add the new node at the head of the linked list. This way, collisions are handled by chaining keys together. For example, inserting keys 5, 8, and 11 into a hash table of size 3 results in all keys chaining at bucket index 2. The linked list grows by adding new nodes at the head, making insertion efficient.