When should you pass a `capacity` to `buildList`/`buildString`, and what is the performance characteristic of building a collection or string this way?
answer
- Capacity forwards to ArrayList/StringBuilder/LinkedHashMap ctor
- Avoids resize reallocation + arraycopy
- Still amortized O(n); it's a constant-factor win
- Use when size is known/large/hot path
- Map capacity is a bucket hint, load factor applies
basics
~10 sPass capacity when you already know roughly how many items or characters you'll add. It pre-sizes the internal array so it doesn't keep resizing and copying as it grows, which speeds up big builds.
solid answer
~40 s`buildList(capacity)`, `buildSet(capacity)`, `buildMap(capacity)`, and `buildString(capacity)` all forward the hint to the underlying `ArrayList`/`LinkedHashSet`/`LinkedHashMap`/`StringBuilder` constructor. These structures grow by reallocating a larger backing array and copying when they exceed capacity; a good initial capacity avoids those intermediate reallocations and array copies. Building is amortized O(n) regardless, but pre-sizing removes the constant-factor resize churn and reduces GC pressure on hot paths or large outputs. Use it when n is known or cheaply estimable (e.g., `source.size`); skip it when n is small or unknown, since a wrong guess (too small still resizes, too large wastes memory) gives little benefit. For maps, remember the capacity is the bucket hint, not a hard limit.
go deeper
Knows capacity pre-sizes the buffer to avoid resizing.
Explains the resize/copy mechanics and when to estimate size.
Frames it as a constant-factor/GC optimization, not an asymptotic one, and weighs over- vs under-estimation.
Discusses measuring before optimizing, load-factor nuance for maps, and capacity tuning on allocation-sensitive hot paths.
## The capacity overloads ```kotlin buildList(capacity: Int) { ... } buildSet(capacity: Int) { ... } buildMap(capacity: Int) { ... } buildString(capacity: Int) { ... } ``` Each forwards `capacity` to the backing structure's capacity constructor: `ArrayList(capacity)`, `LinkedHashSet(capacity)`, `LinkedHashMap(capacity)`, `StringBuilder(capacity)`. ## Why capacity matters: growth mechanics These structures store elements in a backing array. When you exceed the current array size, they: 1. allocate a new, larger array (typically ~1.5x or 2x), 2. copy all existing elements over, 3. discard the old array (garbage). Doing this repeatedly while a list grows from 0 to n triggers several reallocations and copies. The total work is still **amortized O(n)** (geometric growth guarantees it), but each resize is a real allocation + arraycopy + extra garbage. ## When to pass capacity - **Known/estimable size**: e.g. `buildList(source.size) { source.forEach { add(transform(it)) } }`. - **Large outputs**: big strings/collections where resize churn and GC matter. - **Hot paths**: tight loops called frequently. ## When NOT to bother - Small or unknown n — overhead of a few resizes is negligible. - Wildly overestimating wastes memory (an oversized array sits allocated). - Underestimating still resizes, so a bad guess gives little benefit. ## Example ```kotlin val ids: List<Long> = buildList(rows.size) { for (r in rows) add(r.id) } val csv = buildString(rows.size * 16) { // rough char estimate rows.forEach { append(it.id).append(',').appendLine(it.name) } } ``` ## Note on map capacity For `LinkedHashMap`, the capacity argument is an *initial bucket count* hint, and load factor still applies, so the table may resize before reaching `capacity` entries. It's a hint, not a hard guarantee of zero resizes. ## Bottom line Capacity is a constant-factor optimization: it doesn't change the O(n) asymptotics but removes reallocation/copy overhead and GC pressure when you can estimate size cheaply.
- Does passing capacity change the Big-O of building the list?No — it stays amortized O(n). Capacity only removes the constant-factor cost of repeated reallocation and copying.
- What happens if you underestimate the capacity?The structure simply resizes when it overflows, so you lose the benefit but nothing breaks.
Like renting the right-size moving truck up front instead of doing several trips in a car that's too small.
saying these in an interview costs you the question
- Claiming capacity changes the algorithmic complexity to O(1)
- Always passing a huge capacity 'to be safe' (wastes memory)
- Thinking capacity is a hard cap on element count
- Not knowing it forwards to the backing structure's constructor