Walk through what actually happens when a HashMap resizes, and why repeated resizing is expensive.

## 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. 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 copying all current entries. The *amortized* cost per insert is still O(1) (total copying 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. ## Java 8 made the rehash cheaper (but not free) Pre-Java 8, resizing recomputed each entry's position and could reverse linked-list order (a thread-safety footgun under concurrent misuse). Java 8 exploits the power-of-two doubling: when capacity doubles, the bucket-index bitmask gains exactly one more bit. So each entry either **stays at its current index** or **moves to `index + oldCapacity`**, decided by a single bit of its hash (`hash & oldCapacity`). Each old bucket therefore splits into at most **two** new buckets ("lo" and "hi"), entries are relinked without recomputing full hashes, and order is preserved. This is faster and more predictable — but 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 any resize Map<K,V> m = new HashMap<>((int)(N / 0.75f) + 1); // Java 19+: Map<K,V> m2 = HashMap.newHashMap(N); ``` Now there is **one** allocation and **zero** rehashes for the first N inserts: predictable latency, less garbage. ## 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. Java 8's power-of-two split makes each rehash cheaper; presizing avoids them altogether.