Collision Handling Using Open Addressing Linear Probing in DSA Python - Build from Scratch

Collision Handling Using Open Addressing Linear Probing

📖 Scenario: Imagine you are managing a small library's book catalog. Each book has a unique ID number. You want to store these IDs in a simple table so you can quickly find them later. Sometimes, two books might want to go into the same spot in the table. To handle this, you will use a method called linear probing to find the next empty spot.

🎯 Goal: You will build a simple hash table using a list to store book IDs. When a collision happens (two books want the same spot), you will use linear probing to find the next free spot. Finally, you will print the table showing where each book ID is stored.

📋 What You'll Learn

Create a list called hash_table with 7 empty slots represented by None

Create a list called book_ids with these exact values: 10, 20, 15, 7, 32

Write a function called hash_function that returns the index by taking the book ID modulo 7

Insert each book ID into hash_table using linear probing to handle collisions

Print the final hash_table showing the stored book IDs and empty slots as None

💡 Why This Matters

🌍 Real World

Hash tables with collision handling are used in many places like databases, caches, and memory management to store and find data quickly.

💼 Career

Understanding collision handling in hash tables is important for software developers working on efficient data storage, search engines, and system design.

1

Create the hash table and book IDs list

Create a list called hash_table with 7 None values to represent empty slots. Then create a list called book_ids with these exact values: 10, 20, 15, 7, 32.

DSA Python

# Create hash_table with 7 None values
# Create book_ids list with 10, 20, 15, 7, 32
# Your code here

Hint

Use [None] * 7 to create a list with 7 empty slots.

Write the exact list [10, 20, 15, 7, 32] for book IDs.

2

Define the hash function

Define a function called hash_function that takes a parameter key and returns key % 7.

DSA Python

hash_table = [None] * 7
book_ids = [10, 20, 15, 7, 32]

# Define hash_function(key) that returns key modulo 7
# Your code here

Hint

The hash function finds the index by using the remainder when dividing by 7.

3

Insert book IDs using linear probing

Write a for loop to go through each book_id in book_ids. For each book_id, find the index using hash_function(book_id). If the slot at that index in hash_table is None, insert the book_id there. If not, use linear probing by moving to the next index (wrap around to 0 after 6) until you find an empty slot, then insert the book_id.

DSA Python

hash_table = [None] * 7
book_ids = [10, 20, 15, 7, 32]

def hash_function(key):
    return key % 7

# Insert each book_id into hash_table using linear probing
# Your code here

Hint

Use a while loop to find the next empty slot if the first index is taken.

Remember to wrap around using modulo 7.

4

Print the final hash table

Write a print statement to display the hash_table list showing the stored book IDs and None for empty slots.

DSA Python

hash_table = [None] * 7
book_ids = [10, 20, 15, 7, 32]

def hash_function(key):
    return key % 7

for book_id in book_ids:
    index = hash_function(book_id)
    while hash_table[index] is not None:
        index = (index + 1) % 7
    hash_table[index] = book_id

# Print the hash_table
# Your code here

Hint

The printed list shows book IDs in their slots and None for empty slots.