Course contentsShow
← Computer Science
Lesson 428 of 2,87210. Hash TablesFree lesson

Load Factor and Rehashing

Understanding load factor thresholds and when to resize and rehash the entire table.

Load Factor and Rehashing

What you'll learn: How hash tables decide when they're too full and need to grow to maintain performance.

What is Load Factor?

The load factor is a simple ratio that tells you how full your hash table is:

Load Factor = Number of Elements / Table Size

For example, if you have 7 elements in a table with 10 slots, your load factor is 0.7 (or 70% full).

Why It Matters

Think of a hash table like a parking lot. When it's mostly empty, finding a spot is instant. But as it fills up (especially with open addressing from our previous lessons), finding an empty slot takes longer. With separate chaining, long chains form at each slot, making searches slow.

A high load factor means:

  • More collisions
  • Longer probe sequences (linear probing, quadratic probing)
  • Longer chains (separate chaining)
  • Slower operations overall

Load Factor Thresholds

Most hash tables set a maximum load factor threshold:

  • Separate chaining: Often 0.75 to 1.0
  • Open addressing: Usually 0.5 to 0.7 (needs more empty space for probing)

When you exceed this threshold, it's time to rehash.

The Rehashing Process

When the load factor crosses your threshold:

  1. Create a new, larger table (typically double the size)
  2. Recompute hash values for all existing elements (the hash function output depends on table size!)
  3. Insert all elements into the new table
  4. Replace the old table with the new one

This is expensive (O(n) time), but happens infrequently enough that the average-case insertion remains O(1).

Key Takeaway: The load factor measures how full your hash table is; when it exceeds a threshold, rehashing to a larger table maintains efficient performance.