Explain capacity, load factor, and resizing in HashMap. What is the default load factor and why?
answer
- Capacity=buckets (pow2, default 16); load factor=0.75
- threshold = capacity x loadFactor = 12 by default
- Exceed threshold -> resize doubles capacity
- 0.75 = space/time balance (Poisson: long chains rare)
- Pre-size with N/0.75; low/high split on one bit
basics
~20 sCapacity is the number of buckets (default 16). Load factor (default 0.75) is how full the map gets before it grows. When entries exceed capacity x load factor (the threshold), the map doubles its capacity and re-spreads entries so buckets stay short and lookups stay fast.
solid answer
~50 sCapacity is the size of the bucket array, always a power of two, defaulting to 16. The load factor (default 0.75) controls the space/time trade-off: the threshold = capacity x loadFactor (12 by default). When the number of entries exceeds the threshold, resize() doubles the capacity and redistributes entries. 0.75 is a deliberate balance: lower values waste memory but reduce collisions; higher values save memory but lengthen chains. Resizing is expensive (it allocates a new array and moves entries), so if you know the final size you should pre-size the map. To leave room for N entries, call `HashMap.newHashMap(N)` (since JDK 19) or pass an initial capacity above N / 0.75, e.g. new HashMap<>((int)(N / 0.75f) + 1). Because capacity is a power of two, each entry either keeps its index or moves to index + oldCapacity, decided by one bit of its stored hash.
code
java · 18 linesimport java.util.HashMap;
import java.util.Map;
public class PreSize {
public static void main(String[] args) {
int expected = 1000;
// Both give a table of 2048 buckets, so 1000 entries cause no growth.
Map<String, Integer> byFormula = new HashMap<>((int) (expected / 0.75f) + 1);
Map<String, Integer> byFactory = HashMap.newHashMap(expected); // JDK 19+
// A table of 1024 buckets: its threshold is 768, so the 769th entry grows it.
Map<String, Integer> tooSmall = new HashMap<>(expected);
// Defaults: capacity 16, load factor 0.75, growth at the 13th entry.
Map<String, Integer> defaults = new HashMap<>();
}
}
go deeper
Knows default capacity 16 and that the map grows when it gets too full; aware of load factor 0.75 by name.
Computes the threshold, explains the space/time trade-off behind 0.75, and pre-sizes a map to avoid resizes.
Explains the power-of-two invariant, the (n-1)&hash indexing, and the low/high resize split on one bit of the stored hash.
Reasons about resize cost at scale, sizing strategy for hot paths, and trade-offs of tuning load factor for memory- vs latency-sensitive systems.
## Definitions first - **Capacity**: the number of buckets in the internal array (the *table*). HashMap keeps capacity a **power of two** (16, 32, 64, ...). Default initial capacity is **16**. - **Size**: the number of key-value entries actually stored (returned by `size()`). Do not confuse size (entries) with capacity (buckets). - **Load factor**: a `float` measuring how full the map is allowed to get before growing. Default **0.75**. - **Threshold**: the entry count that triggers growth, computed as `capacity x loadFactor`. With defaults that is `16 x 0.75 = 12`. ## What happens as you add entries The table is allocated lazily, "initialized on first use" in the source: `new HashMap<>()` holds no array until something like the first `put` runs `resize()` to create it. After that, each `put` of a new key increments size. When size **exceeds** the threshold, the map calls `resize()`. Resizing: 1. Allocates a new table of **double** the capacity (16 -> 32 -> 64 ...). 2. Recomputes the new threshold (`newCapacity x loadFactor`). 3. Moves every existing entry into the new table. This keeps the average number of entries per bucket low, which is what preserves near-O(1) lookups. Other paths grow the table too. When a `put` adds to a bucket already holding 8 entries and the table has fewer than 64 buckets, `treeifyBin` calls `resize()` instead of building a tree, even with size under the threshold. And a `putAll` from a map larger than the threshold resizes an allocated table before it inserts anything. ## Why 0.75? The load factor is a **space-time trade-off**: - A **low** load factor (e.g. 0.5) means the map grows sooner, so buckets stay very short (fewer collisions, faster lookups) but you waste memory on empty buckets and resize more often. - A **high** load factor (e.g. 0.95) means fewer/later resizes and less memory, but buckets get crowded, collisions rise, and lookups slow down. The class documentation says only that, as a general rule, .75 "offers a good tradeoff between time and space costs". The source's implementation notes add an estimate: under random hash codes, at that threshold bucket sizes follow a Poisson distribution with a parameter of about 0.5, so long chains are rare. ## The low/high split Because capacity is a power of two, the bucket index is computed as `(capacity - 1) & hash` (a bitmask). When capacity doubles, exactly **one new bit** of the hash becomes significant. So for each old entry, you only test that one bit: - bit is 0 -> the entry stays at its **same index** in the new table; - bit is 1 -> it moves to index `oldIndex + oldCapacity`. Thus each old bucket splits into at most two destination buckets (a *low* list and a *high* list) **without calling hashCode()** on any key, because each node stores its hash. This form dates from Java 8, and it preserves relative order within the split lists. The stored hash is not what Java 8 added: JDK 7's update line also read it, unless its optional alternative hashing forced a rehash, then masked it for the new index and linked the entry at the head of its target bucket. Both versions visit every entry once. ## Pre-sizing to avoid resizes Resizing copies all entries, so repeated growth while building a large map is wasteful. If you know you will store N entries and want **zero** resizes, set the initial capacity to at least `N / loadFactor`. A common idiom: `new HashMap<>((int)(N / 0.75f) + 1)`. The constructor rounds the requested capacity up to a power of two (via `tableSizeFor`). Since JDK 19, `HashMap.newHashMap(N)` does the arithmetic for you, and the constructor's documentation points to it, because `new HashMap<>(N)` takes a capacity, not an expected number of entries. On older JDKs, Guava's `Maps.newHashMapWithExpectedSize(N)` also takes the expected count. Do not over-size either: iterating takes time proportional to capacity plus size, and the documentation warns against setting the initial capacity too high if iteration performance is important. ## Key numbers to remember Default capacity 16; default load factor 0.75; default threshold 12; growth = double; index = `(capacity-1) & hash`.
- If you create new HashMap<>(20), what is the actual initial capacity?32. The requested capacity is rounded up to the next power of two by tableSizeFor, so 20 becomes 32.
- You will insert 1000 entries. What initial capacity avoids resizing?At least 1000 / 0.75 ~= 1334, rounded up to the next power of two = 2048. Passing new HashMap<>(2048) (or 1334, which rounds to 2048) avoids resizes.
- Saying default capacity is 10 (that is ArrayList, not HashMap)
- Confusing size (entries) with capacity (buckets)
- Thinking a resize calls hashCode() on every key again (each node stores its hash)
- Claiming capacity can be any number (it is rounded to a power of two)
- Believing load factor 0.75 means it resizes at 75 entries regardless of capacity
- HashMap resize split into low and high lists
- Java 1.8
- HashMap.newHashMap
- Java 19
Assumes JDK 27. HashMap.newHashMap arrived in JDK 19, so it is on 25 LTS too; on older JDKs use the capacity formula. The low/high split dates from Java 8, and these paths read the same at JDK 25.
context
- HashMap (Java SE 27 & JDK 27)docs.oracle.com
- HashMap.java at jdk-27-gagithub.com