What actually happens when a HashMap resizes, and why is repeated resizing expensive?
answer
- Resize = allocate double array + rehash every entry (O(n))
- Bucket index = hash & (capacity - 1); changes when capacity grows
- Repeated resizes = repeated allocations + GC + latency spikes
- Doubling: entry stays or moves to index + oldCapacity
- Presize to avoid it: N / 0.75 + 1
basics
~20 sA HashMap that gets too full allocates a bucket array of double the size and moves every entry into it, recomputing its bucket. That's O(n) work plus a big allocation, so repeating it wastes time and creates garbage.
solid answer
~50 sA HashMap resizes when its size exceeds capacity * loadFactor. It allocates a bucket array of double the capacity and redistributes ("rehashes") every entry, because the bucket index depends on the table size: O(n) work and a fresh allocation each time. A map growing from empty crosses several thresholds (12, 24, 48, ...), each moving all current entries: total work stays O(n), amortized O(1) per insert, but with repeated allocations, GC pressure, and a latency spike on the triggering call. Because capacity is a power of two and doubles, each old bucket splits into at most two new buckets (the original index and index + oldCapacity), and each node already stores its hash, so hashCode() is not called; since Java 8 one hash bit picks the destination and bucket order is preserved. The fix is presizing: HashMap.newHashMap(expectedSize) on Java 19+, or a constructor argument of expectedSize / 0.75 + 1.
go deeper
Knows resizing copies entries into a bigger array and that it costs time; may not detail rehashing.
Explains the double-and-rehash mechanism and the threshold crossings, and knows presizing avoids it.
Articulates O(n) cost, GC/latency implications, the power-of-two split (index or index+oldCap), and the index = hash & (capacity-1) formula.
Reasons about tail latency, allocation/GC behaviour at scale, contrasts with ArrayList, and sets presizing as a standard to keep hot paths allocation-stable.
## Recap: capacity, threshold, buckets A `HashMap` holds entries in a **bucket array** of length `capacity` (always a power of two: 16, 32, 64, ...). A key's bucket index is derived from its hash code, typically `index = hash & (capacity - 1)` (a fast bitmask that works precisely because capacity is a power of two). The map grows when `size > capacity * loadFactor` — the **threshold** (default load factor 0.75, so threshold = capacity * 0.75). ## What a resize does, step by step 1. **Allocate** a new bucket array of **double** the capacity (16 → 32 → 64 → ...). 2. **Recompute placement** for every existing entry. Because the index formula `hash & (capacity - 1)` depends on `capacity`, an entry's bucket in the *new*, larger table may differ from its old bucket. This redistribution is called **rehashing**. 3. **Move** every entry into the new table. Plain-list nodes are relinked, not allocated again. 4. **Update** capacity, threshold, and the table reference; the old array becomes garbage. This is **O(n)** — proportional to the number of entries — and involves a sizeable allocation plus touching every entry. ## Why *repeated* resizing hurts Starting empty with default capacity 16, the thresholds you cross as you add entries are 12, 24, 48, 96, ... Each crossing triggers a full rehash of everything currently stored. Insert a million entries from an unsized map and you resize 17 times, each time moving all current entries. The *amortized* cost per insert is still O(1) (total moving is O(n) overall), **but**: - **Repeated large allocations** — each resize allocates a new array (the largest ones are huge), then discards the old one, creating **garbage** that pressures the GC and can cause pauses. - **Latency spikes** — the single `put` that triggers a resize does O(current size) work, so tail latency is bad even if average is fine. In a low-latency system that spike matters. - **Cache effects** — touching and rewriting the whole table churns CPU caches. ## What Java 8 changed (and what it did not) When capacity doubles, the bucket-index bitmask gains exactly one more bit, on any version. So each entry either **stays at its current index** or **moves to `index + oldCapacity`**, and each old bucket splits into at most **two** new buckets. Neither version calls `hashCode()` in an ordinary resize, because each node stores its hash; JDK 7 recomputed hashes only when its optional alternative hashing switched on. Before Java 8, a resize computed each entry's index from its stored hash and pushed it onto the head of its new bucket, which could reverse linked-list order (a thread-safety footgun under concurrent misuse). Since Java 8 a single bit of the hash (`hash & oldCapacity`) picks the "lo" or "hi" list, entries are relinked, and order is preserved. A bucket that is already a tree splits the same way, and a half of 6 entries or fewer goes back to a list, on new nodes. It's still O(n) and still allocates. ## The cure: presize If you know you'll store N entries, size the map so it never crosses a threshold: ```java // holds N entries without crossing the threshold Map<K,V> m = new HashMap<>((int)(N / 0.75f) + 1); // Java 19+: Map<K,V> m2 = HashMap.newHashMap(N); ``` Given well-spread hashes, there is now **one** bucket-array allocation and **zero** rehashes for the first N inserts: predictable latency, less garbage. (A table under 64 buckets also resizes when one bin grows past 8 entries, whatever its size.) ## Contrast with ArrayList `ArrayList` resizing is similar in spirit — allocate a bigger array (≈1.5×) and `System.arraycopy` the elements — but there's **no rehashing**: elements keep their positions, so the copy is a single bulk memory move (cheap per element). HashMap resizing is costlier per element because it must redistribute entries across buckets. ## Summary Resize = allocate-double + rehash-all = O(n) + a big allocation. Repeated resizes during growth mean repeated allocations, GC pressure, and latency spikes. Since Java 8 the split keeps each bucket's order; presizing avoids size-triggered resizes.
- Amortized insertion into a HashMap is O(1), so why does resizing still matter in a latency-sensitive service?Amortized O(1) hides tail latency: the single put that crosses a threshold does O(current size) work plus a large allocation. In a low-latency or real-time path that spike (and the GC churn from discarded arrays) is exactly what you must avoid, which is why you presize.
- How does a resize decide where each entry goes without calling hashCode(), and what did Java 8 change?Each node stores its hash, so hashCode() is not called. Because capacity is a power of two and doubles, the index mask gains one bit: an entry keeps its index or moves to index + oldCapacity. Since Java 8 the code tests that bit directly (hash & oldCapacity) and keeps each bucket's order; JDK 7 recomputed the index and pushed entries onto the head.
- Saying resize is O(1) — the triggering put is O(current size)
- Thinking resizing recomputes nothing — it redistributes entries because the index depends on capacity
- Confusing ArrayList resize (bulk arraycopy, no rehash) with HashMap resize (full rehash)
- Claiming Java 8 made resize free — it changed how entries split, still O(n) with allocation
- Assuming amortized O(1) means no latency problem — tail latency spikes on resize still matter
- Order-preserving HashMap resize
- Java 1.8
- HashMap.newHashMap
- Java 19
Assumes JDK 27. The order-preserving resize that tests one hash bit dates from Java 8 and is the same at JDK 25; HashMap.newHashMap exists since Java 19.
context
- HashMap (Java SE 27 & JDK 27)docs.oracle.com
- HashMap.java at jdk-27-gagithub.com