Course contentsShow
← Java
Lesson 1127 of 2,87026. Map ImplementationsFree lesson

Performance Cost of Rehashing

Learn why rehashing is an O(n) operation and how it affects HashMap performance during insertion.

Performance Cost of Rehashing

You'll learn why rehashing is an expensive O(n) operation that can temporarily slow down HashMap insertions.

Why Rehashing Is Expensive

When a HashMap reaches its threshold (capacity × load factor), it must rehash. This isn't just about creating a new, larger array—it requires processing every single existing entry in the map. Each entry must be moved from the old array to the new one, and its bucket position must be recalculated based on the new capacity.

Think of it like moving to a new apartment building with twice as many mailboxes. You can't just physically move the mail—you have to recalculate which mailbox each piece belongs in based on the new numbering system. Every single piece of mail must be examined and relocated.

The O(n) Cost Breakdown

Rehashing is O(n) where n is the number of entries because:

  1. Every entry must be visited – you can't skip any
  2. Each hash must be recalculated to determine the new bucket index
  3. Each node must be relinked into the new bucket structure
  4. Tree bins may need restructuring if collision resolution used trees

This means if you have 10,000 entries, rehashing touches all 10,000 entries in one operation.

The Performance Impact

During a put() operation that triggers rehashing, that single insertion becomes dramatically slower—not O(1), but O(n). For a large HashMap, this can cause noticeable latency spikes. This is why presizing your HashMap with an appropriate initial capacity matters: fewer rehashes mean more predictable performance.

Key Takeaway: Rehashing is an O(n) operation that examines and relocates every entry, making any insertion that triggers rehashing significantly slower than normal O(1) operations.