Load factor and rehashing in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Load Factor in Hash Tables

What does the load factor in a hash table represent?

A The ratio of the number of stored elements to the total number of buckets

B The number of collisions that have occurred during insertions

C The maximum number of elements the hash table can store

D The total number of buckets in the hash table

💡 Hint

Think about how full the hash table is compared to its capacity.

The load factor is the ratio of stored elements to buckets, indicating how full the hash table is. It helps decide when to resize the table.

❓ Reasoning

intermediate

Effect of High Load Factor on Hash Table Performance

What is the most likely effect of a high load factor on a hash table's performance?

A No effect on performance as load factor only affects memory usage

B Faster search times due to more elements being stored

C Increased number of collisions leading to slower search and insertion

D Decreased memory usage with no impact on speed

💡 Hint

Consider what happens when many elements share the same bucket.

A high load factor means more elements per bucket, causing more collisions and slower operations.

🧠 Conceptual

advanced

Purpose of Rehashing in Hash Tables

Why is rehashing performed in a hash table?

A To reduce the load factor by increasing the number of buckets and redistribute elements

B To delete all elements and reset the hash table

C To convert the hash table into a linked list for easier traversal

D To compress the stored data to save memory

💡 Hint

Think about what happens when the table becomes too full.

Rehashing increases the number of buckets and redistributes elements to keep operations efficient.

🔍 Analysis

advanced

Identifying When Rehashing Should Occur

Given a hash table with 100 buckets and 75 stored elements, should rehashing be triggered if the load factor threshold is 0.7?

A No, because the load factor is below 1

B Yes, because the load factor is 0.75 which exceeds the threshold

C No, because 75 elements is less than 100 buckets

D Yes, because the number of buckets is too small regardless of load factor

💡 Hint

Calculate the load factor and compare it to the threshold.

Load factor = 75/100 = 0.75, which is greater than 0.7, so rehashing should occur.

❓ Comparison

expert

Comparing Rehashing Strategies

Which rehashing strategy is generally more efficient in maintaining hash table performance as it grows?

A Keeping the number of buckets fixed and only re-inserting elements

B Reducing the number of buckets to save memory and re-inserting elements

C Increasing the number of buckets by one and re-inserting all elements

D Doubling the number of buckets and re-inserting all elements

💡 Hint

Consider how the size increase affects load factor and performance.

Doubling buckets quickly reduces load factor and keeps operations efficient, while small increases cause frequent rehashing.