skip to content

Explain capacity, load factor, and resizing in HashMap. What is the default load factor and why?

level: middleimportance: must knowfreq 80%

answer

  1. Capacity=buckets (pow2, default 16); load factor=0.75
  2. threshold = capacity x loadFactor = 12 by default
  3. Exceed threshold -> resize doubles capacity
  4. 0.75 = space/time balance (Poisson: long chains rare)
  5. Pre-size with N/0.75; low/high split on one bit

basics

~20 s

Capacity 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 s

Capacity 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 lines
java
import 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

for a junior

Knows default capacity 16 and that the map grows when it gets too full; aware of load factor 0.75 by name.

for a middle

Computes the threshold, explains the space/time trade-off behind 0.75, and pre-sizes a map to avoid resizes.

for a senior

Explains the power-of-two invariant, the (n-1)&hash indexing, and the low/high resize split on one bit of the stored hash.

for a principal

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