How does HashMap resize internally?

• Trigger: resize when size > capacity * loadFactor (default threshold = 16 * 0.75 = 12)
• New capacity: doubles the old capacity (16 → 32 → 64); always a power of 2
• Bucket index: hash & (capacity - 1) – bitwise AND is ~10x faster than modulo; power-of-2 capacity makes this work
• Java 8 redistribution: for each entry, check hash & oldCapacity; if 0, stay at current index; if 1, move to oldIndex + oldCapacity
• Cost: O(n) – every entry is visited and potentially moved
• Pre-sizing: new HashMap<>(expectedSize * 4/3 + 1) avoids resize entirely

When does HashMap resize?

HashMap maintains a threshold field equal to capacity * loadFactor. When size exceeds this threshold after a put operation, resize is triggered.

With default settings (capacity 16, load factor 0.75), the first resize happens when the 13th entry is added (threshold = 12). After resize, capacity becomes 32 and threshold becomes 24.

package com.bank.demo;

import java.util.*;

public class ResizeTriggerDemo {
    public static void main(String[] args) {
        // Capacity 16, load factor 0.75 → threshold 12
        Map<String, String> map = new HashMap<>(16, 0.75f);

        for (int i = 1; i <= 15; i++) {
            map.put("ACC" + i, "Holder" + i);
            // Resize happens when 13th entry is added
            // (size > 12 after 12th entry triggers resize on 13th put)
        }

        System.out.println("Size: " + map.size());
        // Capacity is now 32 (doubled from 16)
        // Threshold is now 24 (32 * 0.75)
    }
}

Size: 15

The growth sequence for default settings:

| Capacity | Threshold | Resize at entry |
|---|---|---|
| 16 | 12 | 13th |
| 32 | 24 | 25th |
| 64 | 48 | 49th |
| 128 | 96 | 97th |
| 256 | 192 | 193rd |
| 1024 | 768 | 769th |

Why is capacity always a power of 2?

The bucket index is computed as hash & (capacity - 1). When capacity is a power of 2, capacity - 1 is a bitmask with all lower bits set:

- capacity 16 → mask 15 = `0b00001111`
- capacity 32 → mask 31 = `0b00011111`
- capacity 64 → mask 63 = `0b00111111`

Bitwise AND with this mask extracts the lower bits of the hash, which is equivalent to hash % capacity. But bitwise AND is a single CPU instruction, while modulo requires integer division – roughly 10x slower.

package com.bank.demo;

public class BitwiseVsModuloDemo {
    public static void main(String[] args) {
        int hash = "SAV2001".hashCode();
        int capacity = 16;

        // These produce the same result:
        int bitwiseIndex = hash & (capacity - 1); // fast: one instruction
        int moduloIndex = Math.floorMod(hash, capacity); // slow: division

        System.out.println("Bitwise: " + bitwiseIndex);
        System.out.println("Modulo:  " + moduloIndex);
        System.out.println("Same: " + (bitwiseIndex == moduloIndex));

        // Performance comparison
        int iterations = 100_000_000;
        long start = System.nanoTime();
        int sum = 0;
        for (int i = 0; i < iterations; i++) {
            sum += i & 15; // bitwise
        }
        long bitwiseTime = System.nanoTime() - start;

        start = System.nanoTime();
        sum = 0;
        for (int i = 0; i < iterations; i++) {
            sum += i % 16; // modulo
        }
        long moduloTime = System.nanoTime() - start;

        System.out.printf("Bitwise: %d ms%n", bitwiseTime / 1_000_000);
        System.out.printf("Modulo:  %d ms%n", moduloTime / 1_000_000);
    }
}

Bitwise: 3
Modulo:  3
Same: true
Bitwise: 45 ms
Modulo:  128 ms

How does Java 8 redistribute entries efficiently?

Before Java 8, every entry was rehashed with the new mask: hash & (newCapacity - 1). This required recomputing the index for every entry.

Java 8 introduced an optimization. When capacity doubles from n to 2n, the new mask has one more bit than the old mask. For each entry, only that one extra bit matters:

• If the extra bit in the hash is 0, the entry stays at its current index.
• If the extra bit is 1, the entry moves to oldIndex + oldCapacity.

The check is simply hash & oldCapacity. This splits each bucket into exactly two groups with one bit check per entry – no full rehash needed.

// Capacity 16 → 32
// Old mask: 0b01111 (15)
// New mask: 0b11111 (31)
// Extra bit: bit 4 (value 16 = oldCapacity)

// Entry with hash 0b...01011:
//   Old index: hash & 15 = 01011 & 01111 = 01011 = 11
//   Check:     hash & 16 = 01011 & 10000 = 00000 = 0 → STAYS at index 11

// Entry with hash 0b...11011:
//   Old index: hash & 15 = 11011 & 01111 = 01011 = 11
//   Check:     hash & 16 = 11011 & 10000 = 10000 ≠ 0 → MOVES to index 11 + 16 = 27

What is the impact of load factor?

The load factor controls the trade-off between space and time:

| Load factor | Space | Collisions | Resize frequency |
|---|---|---|---|
| 0.50 | 50% wasted | Very few | Frequent (more resizes) |
| 0.75 (default) | 25% wasted | Few | Balanced |
| 1.00 | 0% wasted | Many | Rare (more collisions) |
| 1.50 | Overpacked | Very many | Very rare |

The default 0.75 is well-studied and works for most applications. Lower values waste memory but give faster lookups. Higher values save memory but increase collision chains.

How do you pre-size HashMap correctly?

package com.bank.service;

import java.math.BigDecimal;
import java.util.*;

public class PreSizingDemo {
    public static void main(String[] args) {
        int expectedAccounts = 100_000;

        // Formula: expectedSize / loadFactor + 1
        int correctCapacity = (int) (expectedAccounts / 0.75) + 1; // 133334
        Map<String, BigDecimal> balances = new HashMap<>(correctCapacity);
        // HashMap rounds up to next power of 2: 262144
        // Threshold = 262144 * 0.75 = 196608 > 100000 → no resize!

        // Simpler: expectedSize * 4/3 + 1 (integer math for 0.75)
        Map<String, BigDecimal> alt = new HashMap<>(expectedAccounts * 4 / 3 + 1);

        // Java 19+: factory method
        // Map<String, BigDecimal> modern = HashMap.newHashMap(expectedAccounts);

        // Load data without resizing
        for (int i = 0; i < expectedAccounts; i++) {
            balances.put("ACC" + String.format("%06d", i), BigDecimal.valueOf(i));
        }
        System.out.println("Loaded " + balances.size() + " accounts without resizing");
    }
}

Loaded 100000 accounts without resizing

What are common mistakes?

Mistake 1: Passing the expected size directly as capacity

// WRONG: new HashMap<>(10000) with 10K entries
// Capacity 16384 (next power of 2), threshold 12288
// 10000 < 12288 → no resize. Happens to work, but wastes capacity.

// WRONG: new HashMap<>(1000) with 1000 entries
// Capacity 1024, threshold 768
// 1000 > 768 → resize at 769th entry!

// CORRECT: account for load factor
// new HashMap<>(1000 * 4 / 3 + 1) = new HashMap<>(1334)
// Capacity 2048, threshold 1536 → no resize for 1000 entries

What should a senior engineer know?

- Resize cost. For a HashMap with 10 million entries, resize copies 10 million entries to a new table. Each entry's bucket position may change. This is O(n) and can cause a noticeable latency spike.

- Non-power-of-2 initial capacity. If you pass a non-power-of-2 initial capacity (e.g., 1000), HashMap rounds up to the next power of 2 (1024). This is handled by tableSizeFor() which uses bit manipulation to find the next power of 2.

- Maximum capacity. HashMap's maximum capacity is 1 << 30 (1,073,741,824). Beyond this, the threshold is set to Integer.MAX_VALUE to prevent further resizing.

- The hi/lo chain split. During Java 8 resize, each bucket is split into two chains: lo (entries that stay) and hi (entries that move). These chains are built by iterating the original chain once, then the lo chain is placed at the old index and the hi chain at oldIndex + oldCapacity.

What are common interview follow-up questions?

• "Why is capacity a power of 2?" – Enables fast bitwise AND instead of modulo for bucket indexing.
• "What triggers a resize?" – size exceeding capacity * loadFactor.
• "How does Java 8 optimize resize?" – One-bit check (hash & oldCapacity) instead of full rehash.
• "How do you avoid resize?" – Pre-size with new HashMap<>(expectedSize / 0.75 + 1).
• "What is the default load factor?" – 0.75.