Load factor and rehashing in Data Structures Theory - Mini Project: Build & Apply

Understanding Load Factor and Rehashing in Hash Tables

📖 Scenario: Imagine you have a small library where you keep books in boxes. Each box can hold a few books. When a box gets too full, you need to get bigger boxes to keep the books organized and easy to find.This is similar to how a hash table works in computers. We will learn about the load factor, which tells us how full the boxes are, and rehashing, which is the process of getting bigger boxes when needed.

🎯 Goal: You will build a simple example to understand how load factor is calculated and when rehashing happens in a hash table.

📋 What You'll Learn

Create a dictionary representing a hash table with a fixed size and some entries

Add a variable to store the maximum load factor allowed before rehashing

Calculate the current load factor based on the number of entries and table size

Add a condition to check if rehashing is needed and update the table size accordingly

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding load factor and rehashing helps software developers design efficient data structures that keep programs fast and responsive.

1

Create the initial hash table data

Create a dictionary called hash_table with these exact entries: 'apple': 1, 'banana': 2, 'cherry': 3. Also create a variable called table_size and set it to 5.

Data Structures Theory

# Create the hash_table dictionary and table_size variable
# Your code here

Need a hint?

Use curly braces {} to create the dictionary with the exact keys and values.

Set table_size to 5 as an integer.

2

Set the maximum load factor

Create a variable called max_load_factor and set it to 0.7. This value means the hash table should rehash when it is more than 70% full.

Data Structures Theory

hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
table_size = 5
# Create max_load_factor variable
# Your code here

Need a hint?

Use a decimal number for max_load_factor to represent 70%.

3

Calculate the current load factor

Create a variable called current_load_factor and set it to the number of entries in hash_table divided by table_size. Use len(hash_table) to get the number of entries.

Data Structures Theory

hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
table_size = 5
max_load_factor = 0.7
# Calculate current_load_factor
# Your code here

Need a hint?

Use len(hash_table) to count entries and divide by table_size.

4

Check if rehashing is needed and update table size

Write an if statement that checks if current_load_factor is greater than max_load_factor. If true, double the table_size by multiplying it by 2.

Data Structures Theory

hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
table_size = 5
max_load_factor = 0.7
current_load_factor = len(hash_table) / table_size
# Check if rehashing is needed and update table_size
# Your code here

Need a hint?

Use an if statement to compare the load factors and multiply table_size by 2 inside the block.