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:
- Every entry must be visited – you can't skip any
- Each hash must be recalculated to determine the new bucket index
- Each node must be relinked into the new bucket structure
- 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.