Collision Handling Using Chaining in DSA Python - Execution Trace

Concept Flow - Collision Handling Using Chaining

Insert key-value pair

↓

Compute hash index

↓

Check bucket at index

↓

Empty

↓

Done

When inserting a key, compute its hash index. If the bucket is empty, create a new list. If collision occurs, add the new node at the start of the linked list in that bucket.

Execution Sample

DSA Python

hash_table = [[] for _ in range(3)]

# Insert keys 5, 8, 11
for key in [5, 8, 11]:
    index = key % 3
    hash_table[index].insert(0, key)

print(hash_table)

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

Execution Table

Step	Operation	Key	Computed Index	Bucket State Before	Bucket State After	Visual State of Hash Table
1	Insert	5	5 % 3 = 2	[]	[5]	[[], [], [5]]
2	Insert	8	8 % 3 = 2	[5]	[8, 5]	[[], [], [8 -> 5]]
3	Insert	11	11 % 3 = 2	[8, 5]	[11, 8, 5]	[[], [], [11 -> 8 -> 5]]
4	End	-	-	-	-	Insertion complete, all keys stored with chaining at index 2

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hash_table	[[], [], []]	[[], [], [5]]	[[], [], [8, 5]]	[[], [], [11, 8, 5]]	[[], [], [11, 8, 5]]
key	-	5	8	11	-
index	-	2	2	2	-

Key Moments - 3 Insights

Why do we insert new keys at the head of the list instead of the tail?

Inserting at the head is faster because it avoids traversing the entire list. As shown in steps 2 and 3 of the execution_table, new keys are added at the start, making insertion O(1).

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

If the bucket is empty (step 1), a new list is created and the key is inserted directly. This is shown by the empty list [] changing to [5] in the bucket.

How does chaining handle collisions?

When multiple keys hash to the same index (steps 2 and 3), chaining stores them in a linked list at that bucket. The visual state shows multiple keys linked together at index 2.

Visual Quiz - 3 Questions

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

A [5]

B [5, 8]

C [8, 5]

D []

💡 Hint

Check row 2 in execution_table under 'Bucket State After'

At which step does the first collision occur?

A Step 1

B Step 2

C Step 3

D No collision occurs

💡 Hint

Look at the 'Computed Index' column; keys 5 and 8 both map to index 2

If the hash table size changed to 5, what would be the index for key 11?

A 1

B 2

C 3

D 0

💡 Hint

Calculate 11 % 5 and compare with 'Computed Index' column logic

Concept Snapshot

Collision Handling Using Chaining:
- Use a list (bucket) at each hash index
- On collision, add new key at head of linked list
- Insertion is O(1) by prepending
- Hash index = key % table_size
- Buckets store multiple keys linked
- Handles collisions by chaining keys together

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. We compute the hash index by taking the key modulo the table size. If the bucket is empty, we create a new list and insert the key. If not, we add the new key at the start of the list to keep insertion fast. This way, collisions are handled by chaining keys together in the same bucket. The example inserts keys 5, 8, and 11 into a hash table of size 3. All keys map to index 2, so they form a linked list there. This method keeps insertion simple and efficient.

Practice

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

easy

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

B. Replace the existing element with the new one

C. Resize the hash table immediately

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index, allowing multiple elements to share the same slot.

3. Final Answer:

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

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Remember: chaining uses linked lists to store collisions [OK]

Common Mistakes:

• Thinking collisions replace existing elements
• Assuming collisions are ignored
• Believing resizing happens immediately on collision

2. Which of the following is the correct way to initialize a hash table with chaining in Python?

easy

A. hash_table = dict()

B. hash_table = [None] * size

C. hash_table = [0] * size

D. hash_table = [[] for _ in range(size)]

Solution

1. Step 1: Understand chaining initialization

   Chaining requires each slot to hold a list to store multiple elements.

2. Step 2: Choose correct initialization

   Using list comprehension to create a list of empty lists ensures each slot can hold multiple elements.

3. Final Answer:

   hash_table = [[] for _ in range(size)] -> Option D

4. Quick Check:

   Empty lists per slot = hash_table = [[] for _ in range(size)] [OK]

Hint: Use list of empty lists for chaining slots [OK]

Common Mistakes:

• Using [None] * size creates references to same list
• Using zeros instead of lists for chaining
• Using dict() which is not a list-based hash table

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

hash_table = [[] for _ in range(3)]
keys = [5, 8, 11]
for key in keys:
    index = key % 3
    hash_table[index].append(key)
print(hash_table)

What is the output?

medium

A. [[5, 8, 11], [], []]

B. [[], [], [5, 8, 11]]

C. [[], [5, 8, 11], []]

D. [[], [5], [8, 11]]

Solution

1. Step 1: Calculate indices for each key

   5 % 3 = 2, 8 % 3 = 2, 11 % 3 = 2. All keys map to index 2.

2. Step 2: Append keys to corresponding lists

   All keys 5, 8, 11 are appended to hash_table[2], so hash_table = [[], [], [5, 8, 11]].

3. Final Answer:

   [[], [], [5, 8, 11]] -> Option B

4. Quick Check:

   Keys mod 3 = 2, all in last list [OK]

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

Common Mistakes:

• Miscomputing modulo operation
• Appending keys to wrong index
• Confusing list positions in output

4. Find the error in this chaining insertion code:

hash_table = [[]] * 4
key = 10
index = key % 4
hash_table[index].append(key)
print(hash_table)

medium

A. Modulo operation is incorrect

B. Append method is not valid for lists

C. Using [[]] * 4 creates references to the same list

D. Index calculation should be key % 3

Solution

1. Step 1: Understand list multiplication behavior

   Using [[]] * 4 creates 4 references to the same inner list, not 4 separate lists.

2. Step 2: Effect on append operation

   Appending to one index appends to all because all slots point to the same list.

3. Final Answer:

   Using [[]] * 4 creates references to the same list -> Option C

4. Quick Check:

   List multiplication duplicates references [OK]

Hint: Use list comprehension for separate lists, not multiplication [OK]

Common Mistakes:

• Assuming [[]] * 4 creates independent lists
• Incorrect modulo calculation
• Misunderstanding append method usage

5. You have a hash table of size 5 using chaining. Insert keys [7, 12, 17, 22, 27]. After insertion, what is the structure of the hash table?

hard

A. [[], [], [7, 12, 17, 22, 27], [], []]

B. [[], [7, 12, 17, 22, 27], [], [], []]

C. [[], [], [], [7, 12, 17, 22, 27], []]

D. [[7, 12, 17, 22, 27], [], [], [], []]

Solution

1. Step 1: Calculate index for each key using modulo 5

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2, 22 % 5 = 2, 27 % 5 = 2. All keys map to index 2.

2. Step 2: Insert keys at index 2

   All keys are appended to the list at index 2, so hash_table = [[], [], [7, 12, 17, 22, 27], [], []].

3. Final Answer:

   [[], [], [7, 12, 17, 22, 27], [], []] -> Option A

4. Quick Check:

   All keys mod 5 = 2, stored at index 2 [OK]

Hint: Calculate key % size to find correct bucket [OK]

Common Mistakes:

• Miscomputing modulo results
• Placing keys in wrong index
• Confusing list positions in output