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.

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. Replace the existing element with the new one when a collision occurs

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

D. Resize the hash table immediately when a collision happens

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, allowing multiple elements per slot.

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:

• Confusing chaining with open addressing
• Thinking collisions overwrite existing data
• Believing resizing happens on every collision

2. Which of the following is the correct way to declare a node structure for chaining in C?

easy

A. typedef struct Node { int key; Node* next; } Node;

B. struct Node { int key; int next; };

C. typedef struct Node { int key; struct Node* next; } Node;

D. struct Node { int key; struct Node next; };

Solution

1. Step 1: Check correct pointer usage in struct

   In C, to create a linked list node, the next pointer must be a pointer to the same struct type.

2. Step 2: Validate typedef syntax

   typedef struct Node { int key; struct Node* next; } Node; correctly uses struct Node* next; and typedefs the struct as Node.

3. Final Answer:

   typedef struct Node { int key; struct Node* next; } Node; -> Option C

4. Quick Check:

   Pointer to struct Node is struct Node* next [OK]

Hint: Use struct Node* for next pointer in C structs [OK]

Common Mistakes:

• Using struct Node next instead of pointer
• Missing typedef keyword or incorrect syntax
• Declaring next as int instead of pointer

3. Consider the following code snippet for inserting keys into a hash table using chaining. What will be the output after inserting keys 5, 15, and 25 if the hash function is key % 10?

typedef struct Node {
  int key;
  struct Node* next;
} Node;

Node* hashTable[10] = {NULL};

void insert(int key) {
  int index = key % 10;
  Node* newNode = malloc(sizeof(Node));
  newNode->key = key;
  newNode->next = hashTable[index];
  hashTable[index] = newNode;
}

// Insert keys
insert(5);
insert(15);
insert(25);

// Print keys at index 5
Node* temp = hashTable[5];
while(temp != NULL) {
  printf("%d -> ", temp->key);
  temp = temp->next;
}
printf("NULL\n");

medium

A. NULL

B. 5 -> 15 -> 25 -> NULL

C. 15 -> 25 -> 5 -> NULL

D. 25 -> 15 -> 5 -> NULL

Solution

1. Step 1: Calculate hash index for each key

   All keys 5, 15, 25 % 10 = 5, so all go to index 5.

2. Step 2: Trace insertion order in chaining

   Each new node is inserted at the head, so order is 25 (last inserted), then 15, then 5.

3. Final Answer:

   25 -> 15 -> 5 -> NULL -> Option D

4. Quick Check:

   New nodes added at head = 25 -> 15 -> 5 [OK]

Hint: New nodes go to head of list in chaining [OK]

Common Mistakes:

• Assuming insertion at tail instead of head
• Miscomputing hash index
• Printing keys in wrong order

4. The following code for inserting into a chained hash table has a bug. What is the bug?

void insert(int key) {
  int index = key % 10;
  Node newNode;
  newNode.key = key;
  newNode.next = hashTable[index];
  hashTable[index] = &newNode;
}

medium

A. No bug, code is correct

B. newNode is a local variable and will be lost after function ends

C. next pointer is not assigned properly

D. Hash function is incorrect

Solution

1. Step 1: Identify variable scope issue

   newNode is declared as a local variable on the stack inside insert function.

2. Step 2: Explain why this causes a bug

   After function returns, newNode memory is invalid, so hashTable points to invalid memory.

3. Final Answer:

   newNode is a local variable and will be lost after function ends -> Option B

4. Quick Check:

   Local variable address stored = invalid pointer [OK]

Hint: Use malloc for nodes, not local variables [OK]

Common Mistakes:

• Ignoring variable lifetime
• Thinking hash function is wrong
• Assuming next pointer assignment is incorrect

5. You have a hash table of size 7 using chaining. You insert keys: 10, 21, 17, 14, 28. The hash function is key % 7. After all insertions, which index will have the longest chain and what will be the order of keys in that chain if new nodes are inserted at the head?

hard

A. Index 0: 28 -> 14 -> 21 -> NULL

B. Index 3: 17 -> 14 -> 28 -> NULL

C. Index 3: 14 -> 17 -> 28 -> NULL

D. Index 4: 10 -> 21 -> NULL

Solution

1. Step 1: Compute hash index for each key

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

2. Step 2: Group keys by index and order insertion at head

   Index 0 keys inserted in order: 21, then 14, then 28 (last inserted at head). So chain at index 0 is 28 -> 14 -> 21 -> NULL.
   Index 3 keys are 10 and 17.

3. Final Answer:

   Index 0: 28 -> 14 -> 21 -> NULL -> Option A

4. Quick Check:

   Longest chain at index 0 with keys inserted at head [OK]

Hint: Calculate key % size, insert new nodes at head [OK]

Common Mistakes:

• Miscomputing hash indexes
• Mixing up insertion order in chains
• Choosing wrong index for longest chain