Collision Handling Using Chaining in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys with chaining

What is the state of the hash table after inserting keys 10, 22, 31, 4, 15 using chaining with hash function h(key) = key % 10?

DSA Python

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

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

    def insert(self, key):
        index = self.hash_function(key)
        self.table[index].append(key)

ht = HashTable()
keys = [10, 22, 31, 4, 15]
for key in keys:
    ht.insert(key)

print(ht.table)

A [[], [10, 22, 31, 4, 15], [], [], [], [], [], [], [], []]

B [[10], [22], [31], [4], [15], [], [], [], [], []]

C [[10, 22, 31, 4, 15], [], [], [], [], [], [], [], [], []]

D [[10], [31], [22], [], [4], [15], [], [], [], []]

💡 Hint

Remember the hash function is key % 10, and collisions are handled by adding keys to the list at that index.

Hashes: 10%10=0, 22%10=2, 31%10=1, 4%10=4, 15%10=5. The table becomes [[10], [31], [22], [], [4], [15], [], [], [], []].

❓ Predict Output

intermediate

Output after deleting a key in chaining hash table

Given the hash table with chaining below, what is the state after deleting key 22? Initial table: [[10], [31], [22, 42], [], [4], [15], [], [], [], []] Hash function: h(key) = key % 10

DSA Python

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[10], [31], [22, 42], [], [4], [15], [], [], [], []]

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

    def delete(self, key):
        index = self.hash_function(key)
        if key in self.table[index]:
            self.table[index].remove(key)

ht = HashTable()
ht.delete(22)
print(ht.table)

A [[10], [31], [], [], [4], [15], [], [], [], []]

B [[10], [31], [42], [], [4], [15], [], [], [], []]

C [[10], [31], [22, 42], [], [4], [15], [], [], [], []]

D [[10], [31], [42, 22], [], [4], [15], [], [], [], []]

💡 Hint

Deleting a key removes it from the list at the hashed index.

Key 22 is in the list at index 2. Removing it leaves [42] at index 2.

🔧 Debug

advanced

Identify the error in chaining insertion

What error does the following code raise when inserting keys 5 and 15? Code: class HashTable: def __init__(self): self.size = 10 self.table = [None] * self.size def hash_function(self, key): return key % self.size def insert(self, key): index = self.hash_function(key) self.table[index].append(key) ht = HashTable() ht.insert(5) ht.insert(15)

DSA Python

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

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

    def insert(self, key):
        index = self.hash_function(key)
        self.table[index].append(key)

ht = HashTable()
ht.insert(5)
ht.insert(15)

A AttributeError: 'NoneType' object has no attribute 'append'

B IndexError: list index out of range

C TypeError: unsupported operand type(s) for %: 'str' and 'int'

D No error, code runs successfully

💡 Hint

Check how the table is initialized and what type each slot holds before insertion.

The table slots are initialized to None, so calling append on None raises AttributeError.

🧠 Conceptual

advanced

Why use chaining for collision handling?

Which of the following is the main advantage of using chaining to handle collisions in a hash table?

A It uses less memory than open addressing methods.

B It guarantees constant time lookup for all keys regardless of collisions.

C It allows multiple keys to be stored at the same index without overwriting existing keys.

D It avoids the need for a hash function.

💡 Hint

Think about what happens when two keys hash to the same index.

Chaining stores collided keys in a list at the same index, preventing overwriting.

❓ Predict Output

expert

Final hash table state after mixed operations with chaining

Given the hash table with chaining and hash function h(key) = key % 7, what is the state of the table after these operations? Operations: Insert 10 Insert 21 Insert 14 Insert 7 Delete 21 Insert 28 Delete 14 Initial table is empty with size 7.

DSA Python

class HashTable:
    def __init__(self):
        self.size = 7
        self.table = [[] for _ in range(self.size)]

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

    def insert(self, key):
        index = self.hash_function(key)
        self.table[index].append(key)

    def delete(self, key):
        index = self.hash_function(key)
        if key in self.table[index]:
            self.table[index].remove(key)

ht = HashTable()
operations = [
    ('insert', 10),
    ('insert', 21),
    ('insert', 14),
    ('insert', 7),
    ('delete', 21),
    ('insert', 28),
    ('delete', 14)
]

for op, key in operations:
    if op == 'insert':
        ht.insert(key)
    else:
        ht.delete(key)

print(ht.table)

A [[7, 28], [], [], [10], [], [], []]

B [[], [7], [], [10, 28], [], [], []]

C [[28], [7], [], [10], [], [], []]

D [[], [7], [], [10], [], [], [28]]

💡 Hint

Calculate the hash index for each key and update the table step-by-step.

Step-by-step (all colliding keys hash to index 0 except 10→3): Insert 10: [[], [], [], [10], [], [], []] Insert 21: [[21], [], [], [10], [], [], []] Insert 14: [[21, 14], [], [], [10], [], [], []] Insert 7: [[21, 14, 7], [], [], [10], [], [], []] Delete 21: [[14, 7], [], [], [10], [], [], []] Insert 28: [[14, 7, 28], [], [], [10], [], [], []] Delete 14: [[7, 28], [], [], [10], [], [], []]

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