Collection Pre-Sizing

## What HashMap stores and how lookups work A **HashMap** maps keys to values. Internally it holds an array of **buckets** (slots), `Node[] table`. To find where a key goes, it computes the key's **hash code**, spreads the bits, and reduces it to an index `hash & (table.length - 1)` — which is why the table length is always a **power of two** (that masking trick only works then). Each bucket holds the entries whose keys landed on that index (a short linked list, or a balanced tree once a bucket gets large). Good distribution means most buckets hold 0–1 entries, giving **average O(1)** `get`/`put`. ## The load factor and why HashMap resizes If you keep adding entries into a fixed number of buckets, buckets get crowded, collisions rise, and lookups degrade toward O(n). To keep buckets sparse, HashMap tracks a **threshold = capacity × load factor**. The **load factor** is the maximum fullness ratio before growing; the default is **0.75** (75%). When `size` exceeds the threshold, HashMap **resizes**: 1. Allocates a new table **double** the length, 2. **Rehashes** — recomputes each existing entry's index for the new length and moves it. Rehashing is O(n) and touches every entry, making it costlier than an `ArrayList` copy (which just moves references). Each resize also discards the old table (GC pressure). ## Why passing the raw count fails Because the threshold is `capacity × 0.75`, a HashMap created with capacity `n` can only hold ~`0.75 × n` entries before it grows. So: ``` new HashMap<>(100); // threshold ≈ 75 (actually 96×0.75 after power-of-two rounding) // insert 100 entries → resizes at least once ``` The constructor argument is **bucket capacity**, not **entry capacity** — a classic confusion. ## The correct sizing rule To guarantee no resize while inserting `n` entries, you need `capacity × 0.75 > n`, i.e. `capacity > n / 0.75`. The conventional, safe formula is: ```java int capacity = (int) (expectedSize / 0.75f) + 1; Map<K, V> map = new HashMap<>(capacity); ``` The `+ 1` covers the strict-inequality / rounding edge. HashMap then rounds `capacity` **up to the next power of two** internally (e.g. you ask for 134, it uses 256). So the result is always at least enough. ### Java 19+ shortcut Manually doing this math is error-prone, so JDK 19 added factory helpers that take the **expected element count** and apply the formula for you: ```java Map<K, V> map = HashMap.newHashMap(expectedSize); Set<E> set = HashSet.newHashSet(expectedSize); ``` Prefer these when available — they encode the rule correctly and read clearly. (`HashSet` is backed by a `HashMap`, so the same load-factor logic and the same sizing concern apply to it.) ## Common misuse and edge cases - **Copy constructor:** `new HashMap<>(otherMap)` already sizes itself for the source's entries — you don't redo the math. - **Over-sizing:** a too-large capacity wastes memory (a big, mostly-empty bucket array) and slightly hurts cache locality, but never breaks correctness. - **Custom load factor:** you can pass a second constructor arg; higher (e.g. 0.9) saves memory but raises collisions, lower (e.g. 0.5) speeds lookups at memory cost. The default 0.75 is the tuned compromise — change it only with measurement. ## Bottom line Size a `HashMap`/`HashSet` for **headroom**, not the raw count: `n / 0.75 + 1`, or just `HashMap.newHashMap(n)` on modern JDKs. This avoids the double-and-rehash work entirely on known-large builds.