Course contentsShow
← Java
Lesson 1063 of 2,87025. Set ImplementationsFree lesson

Performance Impact of Rehashing

Understand the O(n) cost of rehashing and why it happens infrequently as capacity grows.

Performance Impact of Rehashing

You'll learn why rehashing is expensive but rarely causes performance problems in practice.

The Cost of Rehashing

When a HashSet exceeds its threshold (capacity × load factor), rehashing must occur. This operation costs O(n) time because every single element in the set must be reprocessed:

  1. A new, larger backing array is allocated
  2. Every element's hash code is recalculated for its position in the new array
  3. Each element is inserted into the new array at its new bucket location

This is much more expensive than a normal add() operation, which is O(1).

Why It Happens Infrequently

The key insight: as capacity grows, rehashing becomes increasingly rare. Here's why:

  • First rehash might happen at 16 elements (if default capacity is 16)
  • Second rehash at 32 elements
  • Third rehash at 64 elements
  • Fourth rehash at 128 elements

Notice the pattern? The gaps between rehashes double each time. The more elements you add, the less frequently you pay the rehashing cost.

The Analogy

Think of moving to a bigger house. Moving is exhausting and time-consuming (O(n) — you must pack and unpack everything). But if you move from a 2-bedroom to a 4-bedroom, then eventually to an 8-bedroom mansion, you're moving less frequently even as you acquire more possessions. The disruption becomes negligible relative to your daily life.

Amortized Impact

While any single rehash costs O(n), the amortized cost per insertion remains O(1) because rehashing happens logarithmically with respect to the number of elements — not linearly.

Key Takeaway: Rehashing costs O(n) time because all elements must be repositioned, but exponential capacity growth ensures these expensive operations become increasingly rare, preserving O(1) average insertion performance.