Collision Handling Using Chaining in DSA Python

Mental Model

When two keys want to go to the same spot in a table, we keep them in a small linked list at that spot.

Analogy: Imagine a mailbox with several slots. If two letters come for the same slot, we put them in a small pile inside that slot instead of losing one.

Hash Table:
Index 0 -> null
Index 1 -> 21 -> 41 -> null
Index 2 -> 32 -> null
Index 3 -> null
Index 4 -> 14 -> null

Dry Run Walkthrough

Input: Insert keys 14, 21, 32, 41 into a hash table of size 5 using chaining

Goal: Show how collisions are handled by adding nodes to linked lists at the same index

Step 1: Insert 14, hash index = 14 % 5 = 4

Index 4 -> 14 -> null

Why: 14 goes to index 4, no collision yet

Step 2: Insert 21, hash index = 21 % 5 = 1

Index 1 -> 21 -> null
Index 4 -> 14 -> null

Why: 21 goes to index 1, no collision yet

Step 3: Insert 32, hash index = 32 % 5 = 2

Index 1 -> 21 -> null
Index 2 -> 32 -> null
Index 4 -> 14 -> null

Why: 32 goes to index 2, no collision yet

Step 4: Insert 41, hash index = 41 % 5 = 1, collision with 21

Index 1 -> 21 -> 41 -> null
Index 2 -> 32 -> null
Index 4 -> 14 -> null

Why: 41 collides at index 1, so we add it to the linked list there

Result:

Index 0 -> null
Index 1 -> 21 -> 41 -> null
Index 2 -> 32 -> null
Index 3 -> null
Index 4 -> 14 -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, key):
        self.key = key
        self.next = None

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash_function(key)  # find index
        new_node = Node(key)  # create new node
        if self.table[index] is None:
            self.table[index] = new_node  # no collision, place node
        else:
            curr = self.table[index]
            while curr.next is not None:
                curr = curr.next  # move to end of chain
            curr.next = new_node  # add new node at end

    def __str__(self):
        result = []
        for i in range(self.size):
            curr = self.table[i]
            chain = []
            while curr:
                chain.append(str(curr.key))
                curr = curr.next
            chain_str = ' -> '.join(chain) + ' -> null' if chain else 'null'
            result.append(f'Index {i} -> {chain_str}')
        return '\n'.join(result)

# Driver code
ht = HashTable(5)
keys = [14, 21, 32, 41]
for key in keys:
    ht.insert(key)
print(ht)

index = self.hash_function(key) # find index

compute hash index for the key

if self.table[index] is None:

check if slot is empty, no collision

curr = self.table[index] while curr.next is not None: curr = curr.next

traverse linked list to find last node

curr.next = new_node # add new node at end

append new node to handle collision

Output

Index 0 -> null

Index 1 -> 21 -> 41 -> null

Index 2 -> 32 -> null

Index 3 -> null

Index 4 -> 14 -> null

Complexity Analysis

Time: O(n) in worst case because all keys could hash to the same index forming a long chain

Space: O(n) because we store all keys in linked lists inside the table

vs Alternative: Compared to open addressing which stores all keys in the array itself, chaining uses extra linked lists but handles collisions more flexibly

Edge Cases

Inserting into an empty hash table

Key is placed directly without collision

DSA Python

if self.table[index] is None:

Multiple keys hashing to same index

Keys are chained in linked list at that index

DSA Python

while curr.next is not None:

Hash table size is 1 (all keys collide)

All keys form one long chain at index 0

DSA Python

while curr.next is not None:

When to Use This Pattern

When you see a hash table with collisions and need to store multiple keys at one index, use chaining to keep keys in a linked list at that index.

Common Mistakes

Mistake: Overwriting existing key at index instead of chaining
Fix: Traverse the linked list and add new node at the end instead of replacing

Mistake: Not handling empty slot before chaining
Fix: Check if slot is None and insert directly if so

Summary

It stores multiple keys at the same hash index using linked lists to handle collisions.

Use it when your hash function causes collisions and you want to keep all keys safely.

The key insight is to keep a small chain of keys at each index instead of losing or overwriting them.

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