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.