How does ArrayList grow its backing array, and how does that differ from HashMap's growth and from other list types?
answer
- ArrayList grows ~1.5x (oldCap + oldCap>>1), bulk arraycopy, no rehash
- Default cap 10, allocated lazily on first add
- No load factor — capacity = array length directly
- HashMap doubles + rehashes; LinkedList never resizes
- Presize: new ArrayList<>(expectedSize)
basics
~20 sWhen an ArrayList fills up, it makes a new array about 1.5x bigger and copies the elements over with no load factor involved. HashMap instead doubles its array and re-buckets every entry. LinkedList never resizes because it has no backing array.
solid answer
~50 sArrayList holds element references in a contiguous Object[]. When add() would overflow it, the private grow() method enlarges the array by roughly 1.5x (newCap = oldCap + (oldCap >> 1), OpenJDK's choice, since the Javadoc specifies only amortized constant time), then System.arraycopy moves the elements; positions don't change, so it's a cheap bulk copy. There's no load factor: the capacity is exactly the array length. The default starting capacity is 10, allocated lazily on first add. HashMap differs in two ways: it grows by doubling and it must rehash, redistributing every entry across buckets, which is costlier per element. LinkedList stores each element in its own node with prev/next pointers, so it never resizes or copies on add, at the price of more memory per element and O(n) random access. ArrayDeque also uses a resizable array, roughly doubling below 64 slots and growing by 50% above that. Presizing with new ArrayList<>(expectedSize) avoids the resize cascade.
go deeper
Knows ArrayList grows by making a bigger array and copying, and that you can set initial capacity.
States the ~1.5x factor, the no-load-factor distinction from HashMap, lazy default-10 allocation, and contrasts with LinkedList.
Explains why 1.5x (amortized O(1), memory vs copy trade-off), the no-rehash bulk-copy nature, and compares ArrayDeque/CopyOnWriteArrayList; uses trimToSize.
Reasons about cache behaviour, allocation/GC at scale, and sets defaults (ArrayList-first, presize known sizes) backed by measurement rather than folklore.
## ArrayList: a growable array `ArrayList` stores references to its elements in a single contiguous backing array, `Object[] elementData`. Index access is a direct array read — O(1) and cache-friendly. The cost is growth: arrays can't be resized in place. ### Growth mechanics - **Default capacity 10**, but created lazily: `new ArrayList<>()` starts with an empty shared array and allocates the length-10 array on the **first** `add`. - When an `add` would exceed the current capacity, `grow()` computes a new capacity of about **1.5×** the old: `newCapacity = oldCapacity + (oldCapacity >> 1)` (`>> 1` is integer divide-by-two). So 10 → 15 → 22 → 33 → 49 → ... This is OpenJDK's implementation: the Javadoc says only that "the details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost". - It then copies the old elements into the new array with `System.arraycopy`, a fast bulk memory move. Crucially, **element positions are unchanged** — index i stays index i — so there is **no rehashing**, just a copy. ### Why 1.5× (not 2×)? Growing by a constant factor keeps the *amortized* cost of `add` at O(1) (total copying across all growths is O(n)). The JDK states no rationale for the factor itself, but the trade-off is arithmetic: right after growing, 1.5× leaves up to a third of the array empty and doubling up to half, while doubling copies less often. ## HashMap growth — for contrast `HashMap` grows by **doubling** (capacity is always a power of two) and, critically, must **rehash**: because a key's bucket index is `hash & (capacity - 1)`, growing the table changes where entries belong, so every entry is redistributed across the new buckets. That makes a HashMap resize more expensive *per element* than an ArrayList resize (which is a plain bulk copy with no recomputation). Also, HashMap has a **load factor** (0.75) that triggers growth before the table is full; ArrayList has **no load factor** — on its own it grows when an add would not fit, and its capacity argument is the array length directly. ## Other list/collection types - **LinkedList:** a doubly-linked list of nodes, each holding the element plus `prev`/`next` references. It **never resizes or copies** on add/remove at the ends (O(1)), but pays high per-element memory (two extra pointers + node object) and O(n) random access (must walk the chain). For most workloads `ArrayList` is faster despite resizing, because contiguous arrays are cache-friendly. - **ArrayDeque:** backed by a resizable circular array (ring buffer). In OpenJDK it roughly **doubles** below 64 slots (`oldCapacity + 2` more) and grows by **50%** from there, so 17 → 36 → 74 → 111 → 166. Like ArrayList it's array-based and benefits from presizing (`new ArrayDeque<>(n)`). - **CopyOnWriteArrayList:** copies the *entire* backing array on every mutation and has no initial-capacity constructor, since each write reallocates anyway; it's for read-heavy, rarely-written concurrent use. ## Practical guidance - Presize when you know the size: `new ArrayList<>(expectedSize)` — the argument is the array length directly (no /0.75 needed). - Prefer `ArrayList` over `LinkedList` by default; choose `LinkedList` mainly for frequent end-insertion or positioned-iterator edits with no indexing, and even then `ArrayDeque` is usually better for queue/stack use. - Call `trimToSize()` if a list grew large then shrank and you want to reclaim the slack. ## Summary table | Type | Storage | Growth | Rehash on grow? | Load factor | |---|---|---|---|---| | ArrayList | contiguous array | ~1.5× | no (bulk copy) | none | | HashMap | bucket array | 2× | yes | 0.75 | | ArrayDeque | ring buffer array | ~2× below 64 slots, then 1.5× | no | none | | LinkedList | linked nodes | n/a (no array) | n/a | n/a |
- Why is an ArrayList resize cheaper per element than a HashMap resize?ArrayList keeps element positions, so growth is a single System.arraycopy bulk move with no per-element computation. HashMap must rehash: each entry's bucket index depends on capacity, so growing the table redistributes every entry across new buckets — extra per-element work.
- If memory matters after a list shrinks dramatically, how do you reclaim the unused capacity?Call list.trimToSize(), which reallocates the backing array down to the current size, freeing the slack. (And presize on construction to avoid over-allocating in the first place.)
- Saying ArrayList doubles like HashMap — it grows ~1.5x
- Claiming ArrayList has a load factor — it doesn't
- Thinking ArrayList rehashes on grow — it just bulk-copies, positions unchanged
- Saying LinkedList resizes a backing array — it has none; it's linked nodes
- Recommending LinkedList for general use over ArrayList for performance — usually the opposite
Assumes JDK 27 and OpenJDK's implementation; the growth numbers are the same at JDK 25. The ArrayList Javadoc does not specify the growth policy.
context
- ArrayList (Java SE 27 & JDK 27)docs.oracle.com
- ArrayList.java at jdk-27-gagithub.com
- ArrayDeque.java at jdk-27-gagithub.com