Collision Handling Using Chaining in DSA Python - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app. You want to store names and phone numbers. Sometimes, two names might have the same starting letter, causing a collision in your storage. You will use chaining to handle these collisions by storing multiple entries in a list at the same place.

🎯 Goal: Build a hash table using chaining to store names and phone numbers. You will create the initial hash table, add a helper variable for the hash size, insert entries handling collisions by chaining, and finally print the hash table.

📋 What You'll Learn

Create a hash table as a list of empty lists with a fixed size

Create a variable for the hash table size

Write a function to insert name and phone number into the hash table using chaining

Print the final hash table showing all chains

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many apps to store data efficiently even when collisions happen, like phone books, caches, and databases.

💼 Career

Understanding collision handling is important for software engineers working on data storage, search engines, and performance optimization.

1

Create the hash table

Create a list called hash_table with 5 empty lists inside it to represent the buckets for chaining.

DSA Python

# Create the hash_table with 5 empty lists
# Your code here

Hint

Use a list comprehension to create 5 empty lists inside hash_table.

2

Add the hash table size variable

Create a variable called hash_size and set it to 5 to represent the number of buckets in the hash table.

DSA Python

hash_table = [[] for _ in range(5)]
# Create hash_size variable and set it to 5
# Your code here

Hint

This variable will help us find the correct bucket for each entry.

3

Write the insert function using chaining

Write a function called insert that takes name and phone as parameters. Inside the function, calculate the index by taking the length of name modulo hash_size. Then append a tuple (name, phone) to the list at hash_table[index].

DSA Python

hash_table = [[] for _ in range(5)]
hash_size = 5

# Write insert function to add (name, phone) to hash_table using chaining
# Your code here

Hint

Use the length of the name to find the bucket index and add the entry as a tuple.

4

Insert entries and print the hash table

Use the insert function to add these entries: ("Amy", "123"), ("Bob", "456"), ("Cathy", "789"), ("Dan", "012"), and ("Eve", "345"). Then print the hash_table.

DSA Python

hash_table = [[] for _ in range(5)]
hash_size = 5

def insert(name, phone):
    index = len(name) % hash_size
    hash_table[index].append((name, phone))

# Insert entries and print the hash_table
# Your code here

Hint

Check how names with the same length modulo 5 are grouped together in the same bucket.

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