🔑 Section 10 · Question #28

How to Choose the Initial Capacity for HashMap

When the no-argument constructor new HashMap<>() is called, the default capacity is 16 with a load factor of 0.75, resulting in an expansion threshold of 12 ($16 \times 0.75$)....

🔑 HashMap equals hashCode 📄 Source Markdown

🟢 Junior Level

Initial Capacity is the number of bucket slots allocated in the internal table array when a HashMap is instantiated.

When the no-argument constructor new HashMap<>() is called, the default capacity is 16 with a load factor of 0.75, resulting in an expansion threshold of 12 ($16 \times 0.75$). If you know in advance that the map will hold, for instance, 1,000 elements, relying on the default constructor forces 7 consecutive table resizes ($16 \to 32 \to 64 \to 128 \to 256 \to 512 \to 1024 \to 2048$). Each resize allocates a new backing array and rehashes/transfers all existing nodes.

The Golden Sizing Formula

To insert $N$ items without triggering a single resize, calculate the initial capacity using the default load factor ($0.75$):

\[\text{capacity} = \left\lceil \frac{\text{expected elements}}{0.75} \right\rceil = \text{expected elements} \times \frac{4}{3}\] 
import java.util.HashMap;
import java.util.Map;

public class InitialCapacityDemo {
    public static void main(String[] args) {
        int expectedSize = 100;

        // Manual calculation: 100 / 0.75 = 133.33 -> round up to 134
        int capacity = (int) Math.ceil(expectedSize / 0.75f);
        Map<String, Integer> map = new HashMap<>(capacity);

        // Modern standard approach (Java 19+):
        Map<String, Integer> modernMap = HashMap.newHashMap(expectedSize);
    }
}

Analogy: If you are hosting a banquet for 100 guests, you don’t book a table for 16 and repeatedly relocate to progressively larger banquet halls 7 times as guests arrive. You reserve a hall with 134+ seats from the start so everyone sits comfortably without disruption.

🟡 Middle Level

The Classic Trap: Passing expectedSize Directly

A frequent interview mistake is assuming that new HashMap<>(1000) accommodates 1,000 items without resizing:

  1. Passing 1000 causes tableSizeFor(1000) to round up to the next power of two $\to$ 1024.
  2. The expansion threshold is computed as: \(\text{threshold} = 1024 \times 0.75 = 768\)
  3. As items are populated, inserting the 769th item satisfies the condition ++size > threshold ($769 > 768$).
  4. An unexpected, expensive resize occurs, reallocating and rehashing the table from 1024 to 2048 buckets.

The Correct Sizing for 1,000 Elements:

\(\text{initialCapacity} = (int) \left(\frac{1000}{0.75f}\right) + 1 = 1334\)

  • tableSizeFor(1334) rounds up to the next power of two $\to$ 2048.
  • Sized threshold: $\text{threshold} = 2048 \times 0.75 = 1536$.
  • All 1,000 items fit safely without resizing ($1000 \le 1536$).

Modern Standard: Static Factory Methods (Java 19+)

Beginning in Java 19, the JDK introduced official static factory methods that encapsulate the load factor division:

// Allocates a HashMap sized for 10,000 entries with zero resizes:
Map<String, Order> orders = HashMap.newHashMap(10_000);

// Corresponding factories for LinkedHashMap and HashSet:
Map<String, Order> linkedOrders = LinkedHashMap.newLinkedHashMap(10_000);
Set<String> uniqueTags = HashSet.newHashSet(10_000);

Internally, OpenJDK implements calculateHashMapCapacity as:

static int calculateHashMapCapacity(int numMappings) {
    return (int) Math.ceil(numMappings / (double) DEFAULT_LOAD_FACTOR);
}

🔴 Senior Level

The Perils of Over-Allocation

Developers occasionally allocate massive capacities blindly (e.g., new HashMap<>(1_000_000) for a handful of entries). This creates severe performance drawbacks:

  1. Heap Memory Waste: An internal table array of 1,000,000 reference slots consumes 4 MB of RAM with compressed OOPs (-XX:+UseCompressedOops) or 8 MB without, completely unpopulated.
  2. Iteration Degradation: Iterating over map.keySet(), map.values(), or map.entrySet() has a computational complexity of: \(\mathcal{O}(\text{capacity} + \text{size})\) The iterator must sequentially scan every slot in table.length. With capacity = 1_000_000 and size = 10, the iterator performs 999,990 null checks, triggering massive CPU L1/L2/L3 cache misses.
  3. GC Pressure & Card Table Overhead: Large arrays of reference pointers impose heavier scanning costs on generational and concurrent collectors (such as G1 GC Card Tables and ZGC page scans) during marking phases.

Comparison of Capacity Strategies

Strategy Resizes for $N=1000$ Final Capacity Backing Array Memory Primary Consequence
new HashMap<>() (default) 7 resizes 2048 8 KB Latency spikes during progressive rehashing
new HashMap<>(1000) (naive) 1 resize (at item 769) 2048 8 KB Single unexpected P99 latency spike
HashMap.newHashMap(1000) 0 resizes 2048 8 KB Optimal throughput and flat latency
new HashMap<>(100_000) (oversized) 0 resizes 131,072 512 KB Fast insertion, severely degraded iteration

4 Tricky Questions

1. What happens if you instantiate new HashMap<>(12) and insert exactly 12 items? Does resize() trigger?

Answer: No, but inserting a 13th item will trigger a resize. Let’s trace the OpenJDK execution:

  1. Passing 12 causes tableSizeFor(12) to round up to the nearest power of two $\to$ 16.
  2. Threshold calculation: $\text{threshold} = 16 \times 0.75 = 12$.
  3. As items are inserted:
    • After inserting 11 elements: size is 11 ($11 \le 12$).
    • Inserting the 12th element: putVal evaluates if (++size > threshold) resize();.
    • 12 > 12 evaluates to false. No resize occurs!
  4. If a 13th element is inserted, 13 > 12 evaluates to true, triggering resize().

2. Why did legacy libraries like Guava use (int)(expected / 0.75f + 1.0f) instead of (int)(expected / 0.75f)?

Answer: To defend against floating-point precision truncation during integer casting:

  • Casting (int) floatValue performs truncation towards zero (floor).
  • For expected = 3: $3 / 0.75 = 4.0$. However, due to binary IEEE-754 floating-point inaccuracies, the division may produce 3.9999998f.
  • Casting (int) 3.9999998f truncates to 3!
  • Then tableSizeFor(3) yields 4, with threshold $4 \times 0.75 = 3$. Inserting items could trigger a premature resize. Adding + 1.0f or utilizing Math.ceil() shields the calculation from float precision loss.

3. Does it make sense to specify initialCapacity for small collections holding fewer than 10 elements?

Answer: Generally, no. The default capacity of 16 bucket slots accommodates up to 12 elements ($16 \times 0.75$) with zero resizes. An array of 16 reference pointers occupies only ~80 bytes of heap memory. Attempting to fine-tune capacity for 3 or 5 elements adds cognitive clutter to the codebase with zero measurable performance benefit. Pre-sizing is beneficial when collections hold dozens, hundreds, or thousands of elements.

4. How should you calculate initial capacity when using a custom loadFactor (e.g. 0.5f)?

Answer: Apply the universal formula using the specified load factor: \(\text{capacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil\) For an expected size of 100 and a load factor of 0.5f: \(\text{capacity} = \left\lceil \frac{100}{0.5f} \right\rceil = 200\) Pass both arguments to the constructor:

Map<Key, Value> map = new HashMap<>(200, 0.5f);

tableSizeFor(200) rounds the capacity to 256. The resulting threshold is $256 \times 0.5 = 128$, safely accommodating 100 elements without any resizing.

🎯 Interview Cheat Sheet

  • Capacity Formula: $\text{initialCapacity} = \lceil \text{expectedElements} / 0.75 \rceil$.
  • The Naive new HashMap<>(1000) Mistake: Allocates capacity 1024 with threshold 768; a resize occurs on the 769th insertion.
  • Proper 1,000 Capacity: Specify 1334 (rounds to capacity 2048, threshold 1536 $\implies$ zero resizes).
  • Modern Standard (Java 19+): Prefer HashMap.newHashMap(expectedSize) or HashSet.newHashSet(expectedSize).
  • Dangers of Over-Allocation: Excessive capacities waste heap memory and degrade iteration speed ($\mathcal{O}(\text{capacity} + N)$).
  • Small Collections: Collections with $\le 12$ entries need no initial sizing; default capacity 16 is already optimal.