Questions
6 of 17
What is the Load Factor? How does it trigger a Rehash/Resize?
Difficulty: 3/10
Load Factor and Resizing
The load factor measures how full a Hash Table is. For a table with n stored entries and m buckets, the load factor is alpha = n / m. As the load factor increases, collisions generally become more frequent, so implementations resize the table when a configured threshold is exceeded.
javascript
- 1
A lower load factor generally means fewer collisions but more memory usage.
- 2
A higher load factor improves memory efficiency but can increase lookup cost.
- 3
Resizing usually allocates a larger table.
- 4
Existing entries must be rehashed because bucket indexes depend on table capacity.
- 5
A resize operation itself can take O(n).
- 6
Over many insertions, resizing can still preserve amortized O(1) insertion.
Follow-up Questions
- Why must entries be rehashed after resizing?
- How does resizing affect amortized complexity?
- What load factor would you choose and why?