HashMap Internals: Buckets, Resize and Treeification

HashMap is the collection Java programs touch most, and the one interviewers probe hardest, because its implementation ties together hashing, the equals/hashCode contract, amortised complexity and a genuine concurrency failure that took down real systems.

The structure#

transient Node<K,V>[] table;      // always a power of two in length
transient int size;               // number of key-value mappings
int threshold;                    // capacity * loadFactor — resize when size exceeds this
final float loadFactor;           // 0.75 by default
 
static class Node<K,V> {
    final int hash;               // cached — never recomputed
    final K key;
    V value;
    Node<K,V> next;               // chain for collisions
}

Caching the hash in the node is a small detail with a large effect: a resize re-buckets every entry without calling hashCode() again, and a get compares the cached int before it ever calls equals, which short-circuits most collision comparisons for free.

Finding the bucket#

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
 
// and then, in putVal/getNode:
int index = (n - 1) & hash;       // n is the table length

The index calculation uses & rather than % because the table length is always a power of two, and a bitwise AND is far cheaper than a division. But that also means only the lowest bits of the hash are used. With a 16-slot table, only the bottom four bits matter.

That is why the spread exists. Many real hashCode() implementations vary mostly in their high bits — Integer.hashCode() is the value itself, so a map keyed on values that are all multiples of 65,536 would put every entry in bucket zero. XORing the high 16 bits down into the low 16 mixes that variation into the range the index actually reads, at the cost of one shift and one XOR.

put, step by step#

1. Compute the spread hash and the bucket index.
2. If the bucket is empty, store a new node. Done.
3. If the first node has the same hash and an equal key, replace the value.
4. If the bucket is a tree, insert into the tree.
5. Otherwise walk the chain. Replace on a match, or append at the end.
6. If the chain now has 8 entries, treeify (or resize if the table is smaller than 64).
7. If ++size > threshold, resize.

Step 3 is worth noticing: the hash is compared before equals. Two objects with different hashes are never compared with equals at all, which is why an expensive equals is usually not a performance problem in a well-distributed map.

Resizing#

// Default: capacity 16, threshold 12
Map<String, Order> m = new HashMap<>();
// After the 13th put: allocate a 32-slot table, re-bucket all 13 entries, threshold becomes 24.

The table doubles and every entry is redistributed. Because the capacity is a power of two and the index is (n - 1) & hash, an entry either stays at its current index or moves to index + oldCapacity — determined by a single bit test, (hash & oldCapacity) == 0. Java 8 exploits this to split each bucket into a "low" and a "high" chain in one pass, preserving relative order and avoiding a rehash.

The cost is still O(n) at that moment. Inserting a million entries into a default-sized map performs about 16 resizes and re-buckets roughly two million entries in total, allocating and discarding each old table along the way.

// Wrong: this still resizes, because 1000 * 0.75 = 750 < 1000
Map<String, Order> a = new HashMap<>(1000);
 
// Right: capacity must exceed expectedSize / loadFactor
Map<String, Order> b = new HashMap<>((int) (1000 / 0.75f) + 1);
 
// Java 19+: does the arithmetic for you
Map<String, Order> c = HashMap.newHashMap(1000);

This is a genuinely common mistake — new HashMap<>(expectedSize) sets the capacity, not the capacity the expected size requires. The constructor also rounds up to the next power of two, so new HashMap<>(1000) actually allocates 1024 slots with a threshold of 768.

Treeification#

When a bucket's chain reaches 8 entries, HashMap converts it from a linked list to a red-black tree, dropping worst-case lookup within that bucket from O(n) to O(log n). If the table is smaller than 64 slots it resizes instead, on the reasoning that a small table is more likely to be suffering from too few buckets than from genuinely colliding hashes. On shrinking, a tree reverts to a list at 6 entries — the gap from 8 prevents thrashing at the boundary.

The threshold of 8 comes from probability. With a good hash function and a 0.75 load factor, bucket occupancy follows a Poisson distribution with λ = 0.5, giving these probabilities:

A bucket reaching eight entries by chance is a one-in-tens-of-millions event, so if it happens the cause is almost certainly a poor hashCode or a deliberate attack — and in both cases a tree is the right response. This feature was added in Java 8 specifically to defend against hash collision denial of service, where an attacker submits thousands of keys engineered to collide and turns every lookup into a linear scan.

Tree nodes require keys to be Comparable, or fall back to comparing identity hash codes, which is why treeification helps even for keys with no natural order.

The concurrency failure#

Java 8's resize preserves chain order and cannot form a cycle, so the infinite loop is gone. What remains is still fatal: concurrent modification can lose entries, resurrect removed ones, produce a size that does not match the contents, or throw ConcurrentModificationException from an unrelated iteration. A HashMap is simply not safe to share.

The answer is ConcurrentHashMap — not Collections.synchronizedMap, which serialises every operation onto one lock. See ConcurrentHashMap internals.

Null keys and iteration order#

HashMap allows one null key, stored in bucket 0 with a hash of 0, and any number of null values. Hashtable and ConcurrentHashMap allow neither, because in a concurrent map a null return from get would be ambiguous between "absent" and "mapped to null".

Iteration order is the table order, which means it depends on the current capacity. A map that iterates as a, b, c at size 12 may iterate as c, a, b after the resize at 13. Tests that assert on HashMap order pass until the data grows.

What gets asked#

The full sequence is usually: how does put work; what is a collision and how is it resolved; why 0.75; what happens at 8 entries; and what goes wrong with concurrent access. Being able to say "index is (n-1) & hash, which is why the capacity is a power of two, and why the hash is XORed with its high bits — otherwise only the low bits would ever be used" covers the first three at once.