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

Rehashing Process

Implementing table resizing by creating a new table and rehashing all existing elements.

Rehashing Process

What you'll learn: How to properly resize a hash table by creating a new, larger table and redistributing all existing elements.


Why Rehash?

When your hash table's load factor (ratio of elements to table size) gets too high, collisions become frequent and performance degrades. The solution? Create a bigger table and move everything over—this is rehashing.

The Core Idea

Rehashing isn't as simple as copying elements to a new array. Because hash functions depend on table size (remember the division method: hash(key) % table_size), every element must be hashed again with the new table size.

Think of it like moving to a bigger apartment building with more mailboxes. You can't just transfer mail from box #5 to box #5 in the new building—the addressing system is different because there are more boxes now!

The Rehashing Steps

  1. Create a new table (typically 2× the old size)
  2. Initialize the new table (empty chains or slots)
  3. Iterate through every element in the old table
  4. Recompute the hash for each key using the new table size
  5. Insert each element into its new position
  6. Replace the old table with the new one

Example Scenario

Your table has size 7, and you're rehashing to size 17. A key that hashed to key % 7 = 3 will now hash to key % 17, which could be completely different! Every single element needs this recalculation.

Cost Consideration

Rehashing is expensive—it's an O(n) operation where n is the number of elements. However, it happens infrequently enough that hash tables maintain their average-case O(1) performance when amortized over many operations.

Key Takeaway: Rehashing rebuilds the entire hash table with a new size, requiring every element to be hashed again because the hash function's output depends on table size.