What does it mean to 'pre-size' a Java collection like ArrayList or HashMap, and why might you do it when you already know roughly how many elements you'll add?
answer
- Backing array is fixed-length → grow = allocate + copy
- ArrayList grows 1.5x; HashMap doubles + rehashes
- Amortized O(1) ≠ zero copying
- HashMap capacity = expectedSize / 0.75 + 1
- Constructor arg = one allocation instead of many
basics
~20 sPre-sizing means telling a collection up front how many items you expect, via a constructor argument (e.g. new ArrayList<>(1000)). It avoids the collection having to grow and copy its internal array repeatedly as you add items, which saves time and memory churn.
solid answer
~40 sPre-sizing is passing an expected capacity to a collection's constructor so its internal storage is allocated once, big enough for the data you know is coming. ArrayList and HashMap are backed by arrays that have a fixed size; when they fill up they allocate a bigger array and copy everything over. For an ArrayList this is a 1.5x growth-and-copy; for a HashMap it's a doubling plus a rehash of every entry. If you're inserting a known, large number of elements, those repeated resizes are wasted work and produce garbage for the GC. By calling new ArrayList<>(expectedSize) or new HashMap<>(capacity) you skip the intermediate allocations and do the work once. It's a cheap, low-risk optimization on hot paths where the final size is known or estimable.
go deeper
Knows you can pass a number to the constructor and that it avoids re-growing the list; can state ArrayList is array-backed.
Explains the allocate-and-copy resize mechanism, ArrayList's 1.5x growth, and that HashMap capacity must account for the 0.75 load factor.
Frames it as eliminating wasted work and GC churn on hot paths, cites the capacity = n/0.75 + 1 rule, and knows when it's worth doing vs noise.
Reasons about it as a system-wide micro-optimization budget: where to apply it (latency-critical batch paths), measuring before/after, and the memory-vs-resize trade-off across a service.
## What a collection 'capacity' is A **collection** in Java is an object that holds a group of elements (a list, a set, a map). Several of the standard ones store their elements in a plain **array** — a fixed-length block of memory. `ArrayList` keeps an internal `Object[]`; `HashMap` keeps an internal array of buckets (`Node[]`). The **size** of a collection is how many elements you've actually put in it. The **capacity** is how many slots the backing array currently has. Capacity is an implementation detail you normally don't see, but it drives performance. ## The problem: arrays can't grow A Java array has a length fixed at creation. So when an `ArrayList` whose backing array is full needs to accept one more element, it can't 'extend' the array — it must: 1. Allocate a **new, larger** array, 2. **Copy** every existing element into it (via `System.arraycopy`), 3. Drop the old array (which becomes garbage). This copy is O(n) in the current size. `ArrayList` grows by roughly **1.5x** each time (new capacity ≈ old + old/2). `HashMap` is similar but **doubles** its bucket array and, worse, must **rehash** — recompute each key's bucket position and move it — because a key's bucket depends on the array length. ## Why 'amortized O(1)' is not 'free' People say adding to an `ArrayList` is **amortized O(1)**: across many adds, the average cost per add is constant, because resizes get rarer as the list grows (each resize roughly doubles headroom). That's true and reassuring — you'll never do better than linear total work. **But amortized-O(1) still means real copying happens.** If you start from the default capacity (10 for `ArrayList`) and add a million elements, you trigger ~20-ish reallocations, copying a growing prefix each time — millions of element copies total, plus ~20 throwaway arrays for the garbage collector. None of that work produces a result you keep; it's pure overhead caused by *not knowing the size up front* — even though you did. ## The fix: pre-size If you know (or can estimate) the final element count, give it to the constructor: - **ArrayList:** `new ArrayList<>(expectedSize)` allocates a backing array of exactly that length once. No resizes if your estimate holds. - **HashMap:** the capacity argument is the **bucket-array size**, not the element count — and HashMap resizes when it gets ~75% full (the **load factor**, default 0.75). So to hold `n` entries without a resize you need capacity > n/0.75. The standard rule is **`capacity = (int)(expectedSize / 0.75) + 1`**. (Java 19+ adds `HashMap.newHashMap(n)` which does this math for you.) ### Load factor in one sentence The **load factor** is the fullness threshold at which a HashMap grows: at 0.75, a 16-bucket map resizes once it holds 12 entries. Higher load factor = less memory but more hash collisions (slower lookups); lower = faster lookups but more memory. 0.75 is the default trade-off. ## When it matters / doesn't - **Matters:** hot paths, large known sizes, tight loops, batch builds, latency-sensitive code, memory-constrained services. - **Doesn't much:** small collections, cold code, when the final size is genuinely unknown (a bad over-estimate just wastes memory). Pre-sizing is one of the cheapest, safest optimizations: a constructor argument, no behavior change, no algorithmic risk.
- If you over-estimate the size badly, what's the downside?Wasted memory: the backing array is allocated larger than needed and stays that way (ArrayList won't shrink automatically; you'd call trimToSize()). It also slightly hurts cache locality. Over-estimating is usually less harmful than under-estimating, but a wild over-estimate (e.g. millions for a handful of items) is a real waste.
saying these in an interview costs you the question
- Thinking ArrayList stores elements in a linked structure rather than an array
- Believing amortized O(1) means no resizing/copying ever happens
- Passing the expected element count directly as HashMap capacity (ignoring the 0.75 load factor)
- Claiming pre-sizing changes program behavior or output (it only affects performance/memory)