Understanding HashMap Internals: Table Initialization, Resizing, and Load Factor

HashMap Underlying Implementation

In JDK 1.8, HashMap stores entries in an array of Node<K,V> objects, where each bucket may contain a linked list or a red‑black tree when the chain becomes long.

/** * array */
transient Node
[] table;
/** * linked list node */
static class Node
implements Map.Entry
{
    final int hash;
    final K key;
    V value;
    Node
next;
    // getters, hashCode, equals, etc.
}
/** * red‑black tree node */
static final class TreeNode
extends LinkedHashMap.Entry
{
    TreeNode
parent;
    TreeNode
left;
    TreeNode
right;
    boolean red;
    // ...
}

When Is the Table Initialized?

The table is not allocated during new HashMap() . It is lazily created on the first put operation by calling resize() . The default length after this first allocation is 16 and the default threshold (capacity × loadFactor) is 12, so the map can hold 12 entries before the first resize.

Resize Logic

Both the initial allocation and subsequent expansions are performed by the same resize() method. The method doubles the array size when the current size exceeds the threshold.

final Node
[] resize() {
    Node
[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        newCap = oldCap << 1;
        newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) {
        newCap = oldThr;
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE;
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node
[] newTab = (Node
[])new Node[newCap];
    table = newTab;
    // rehash existing entries if oldTab != null
    return newTab;
}

Why Table Length Is a Power of Two

Using a length that is a power of two allows the index to be computed with a fast bitwise AND operation: index = hash & (length - 1) . This avoids the slower modulo operation and distributes keys uniformly when the hash function spreads bits well.

Index Calculation

Computing the bucket index with hash & (length‑1) (instead of hash % length or hash & length ) reduces collisions because the mask length‑1 consists of consecutive low‑order 1 bits.

Effect of Initial Capacity and Load Factor

When a specific initialCapacity is supplied, the constructor calls tableSizeFor(initialCapacity) to round it up to the next power of two, which becomes the initial threshold. The actual table is still allocated lazily on first put .

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Examples:

new HashMap(1000) → table length 1024, threshold 768; the 769th entry triggers a resize.

new HashMap(10000) → table length 16384, threshold 12288; inserting 10 001 entries does **not** cause a resize.

Load Factor (0.75)

A load factor that is too small causes frequent resizing (performance cost), while a factor that is too large leads to high collision rates and longer chains (or trees), degrading get/put performance. The default 0.75 is a balanced compromise.

Summary

HashMap uses an array of size 2ⁿ to enable fast index calculation via hash & (length‑1) . The default capacity (16) and load factor (0.75) give a threshold of 12, triggering the first resize after 12 entries. Resizing doubles both the array length and the threshold, preserving existing entries. Specifying an initial capacity rounds up to the nearest power of two, influencing when the first resize occurs. Understanding these mechanics helps answer common interview questions about HashMap behavior.