Collision handling (open addressing) in Data Structures Theory - Mini Project: Build & Apply

Collision Handling with Open Addressing

📖 Scenario: Imagine you are designing a simple hash table to store student IDs and their names. Sometimes, two student IDs might hash to the same position. To handle this, you will use open addressing, which means if a spot is taken, you look for the next empty spot.

🎯 Goal: You will build a step-by-step example of how open addressing works to resolve collisions in a hash table.

📋 What You'll Learn

Create an initial hash table with empty slots

Set a hash function and a starting index

Implement linear probing to find the next empty slot

Insert a new student ID and name into the hash table using open addressing

💡 Why This Matters

🌍 Real World

Hash tables are used in many applications like databases, caches, and dictionaries to store and quickly find data.

💼 Career

Understanding collision handling is important for software developers and data engineers who work with efficient data storage and retrieval.

1

Create the initial hash table

Create a list called hash_table with 5 empty slots represented by None.

Data Structures Theory

# Create a list called hash_table with 5 None values
# Your code here

Need a hint?

Use a list with 5 None elements to represent empty slots.

2

Set the hash function and starting index

Create a variable called student_id with the value 12. Then create a variable called start_index that stores the hash value of student_id modulo the length of hash_table.

Data Structures Theory

hash_table = [None, None, None, None, None]
# Create student_id = 12 and start_index using modulo
# Your code here

Need a hint?

Use the modulo operator % to find the starting index.

3

Implement linear probing to find an empty slot

Create a variable called index and set it equal to start_index. Then create a while loop that continues as long as hash_table[index] is not None. Inside the loop, update index to (index + 1) % len(hash_table) to move to the next slot.

Data Structures Theory

hash_table = [None, None, None, None, None]
student_id = 12
start_index = student_id % len(hash_table)
# Use linear probing to find an empty slot
# Your code here

Need a hint?

Use a while loop and update index with modulo to wrap around.

4

Insert the student ID and name into the hash table

Create a variable called student_name with the value "Alice". Then assign a tuple (student_id, student_name) to hash_table[index] to insert the student data at the found empty slot.

Data Structures Theory

hash_table = [None, None, None, None, None]
student_id = 12
start_index = student_id % len(hash_table)
index = start_index
while hash_table[index] is not None:
    index = (index + 1) % len(hash_table)
# Insert the student data at hash_table[index]
# Your code here

Need a hint?

Store the student ID and name as a tuple in the empty slot.