HashMap Internals in Java: Buckets, Collisions, Resizing and Treeification

put() and get() hide collisions, equality checks, resizing, and mutable-key traps. A key moves from hashCode() to a bucket; replacement, resizing, and key mutation affect later lookups. Equal hash codes do not make keys equal. The public Map contract and OpenJDK's implementation details answer different questions, so keep them separate.

HashMap's public behaviour and bucket model

HashMap<K,V> implements Map<K,V> with a hash table. The Java SE 25 HashMap documentation permits one null key and null values, guarantees neither iteration order nor synchronisation, and gives expected constant-time get and put for well-dispersed hashes, not a worst-case bound.

The OpenJDK 25 GA implementation uses a default initial capacity of 16, a default load factor of 0.75, and lazy table allocation on first insertion. For a non-null key with raw hash h, the spread hash is h ^ (h >>> 16). With table length n, the bucket index is (n - 1) & spreadHash; the power-of-two length makes the mask valid.

A list node stores the spread hash, key, value, and next-node link. For design context, review hashing and collision resolution. A lookup checks the relevant bucket, then compares hashes and keys.

Worked collision: "Aa" and "BB" are different keys

Both strings produce the same raw hash. This program calculates their OpenJDK-style spread and bucket without private-field access:

import java.util.HashMap;

public class Main {
    static int spread(String key) {
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }

    static int index(int spreadHash, int capacity) {
        return (capacity - 1) & spreadHash;
    }

    public static void main(String[] args) {
        HashMap<String, Integer> scores = new HashMap<>();
        scores.put("Aa", 10);
        scores.put("BB", 20);
        scores.put("Aa", 30);

        System.out.println("Aa hashCode = " + "Aa".hashCode());
        System.out.println("BB hashCode = " + "BB".hashCode());
        System.out.println("Aa bucket at capacity 16 = " + index(spread("Aa"), 16));
        System.out.println("BB bucket at capacity 16 = " + index(spread("BB"), 16));
        System.out.println("Aa -> " + scores.get("Aa"));
        System.out.println("BB -> " + scores.get("BB"));
        System.out.println("size -> " + scores.size());
    }
}

Aa hashCode = 2112
BB hashCode = 2112
Aa bucket at capacity 16 = 0
BB bucket at capacity 16 = 0
Aa -> 30
BB -> 20
size -> 2

The arithmetic is 2112 = 0x00000840. Because 2112 >>> 16 = 0, the spread is 2112 ^ 0 = 2112. Then 2112 & 15 = 0, so both keys enter bucket 0. Yet "Aa".equals("BB") is false, so they coexist. The third put matches the stored hash and key, replaces 10 with 30, and keeps size 2.

What put and get check inside a bucket

OpenJDK's put spreads the hash, initialises the table, calculates the index, and creates a node in an empty bin. In an occupied bin, it compares stored hash and key via equals. A match replaces the value; a collision continues through the list or tree. A null key has spread hash 0 and starts in bucket 0.

For get("BB"), spread 2112 gives index 0. The search rejects "Aa", then matches "BB" and returns 20. Both hash and equality matter: equal keys need equal hash codes, while unequal keys may share one. The number 2112 identifies neither string.

Worked resize from capacity 4 to capacity 8

This example forces small hashes while equals compares an immutable identity:

import java.util.HashMap;

public class Main {
    static final class DemoKey {
        final String id;
        final int forcedHash;

        DemoKey(String id, int forcedHash) {
            this.id = id;
            this.forcedHash = forcedHash;
        }

        @Override
        public int hashCode() { return forcedHash; }

        @Override
        public boolean equals(Object other) {
            return other instanceof DemoKey
                    && id.equals(((DemoKey) other).id);
        }
    }

    public static void main(String[] args) {
        HashMap<DemoKey, String> map = new HashMap<>(4, 0.75f);
        DemoKey a0 = new DemoKey("A0", 0);
        DemoKey a4 = new DemoKey("A4", 4);
        DemoKey a8 = new DemoKey("A8", 8);
        DemoKey a12 = new DemoKey("A12", 12);

        map.put(a0, "zero");
        map.put(a4, "four");
        map.put(a8, "eight");
        map.put(a12, "twelve");

        System.out.println(map.get(a0));
        System.out.println(map.get(a4));
        System.out.println(map.get(a8));
        System.out.println(map.get(a12));
        System.out.println("size = " + map.size());
    }
}

The first insertion creates length 4; 4 x 0.75 = 3 sets the threshold. At length 4, 0 & 3 = 0, 4 & 3 = 0, and 8 & 3 = 0, so the first three entries share bucket 0. The fourth insertion raises size to 4, exceeding 3, and grows the table to length 8 with threshold 6.

Now 0 & 7 = 0 and 8 & 7 = 0, while 4 & 7 = 4 and 12 & 7 = 4. OpenJDK tests storedHash & oldCapacity, so each entry stays or moves by exactly 4. The result is bucket[0]: A0 -> A8 and bucket[4]: A4 -> A12. The program prints zero, four, eight, twelve, and size = 4.

Treeification and the 8, 6 and 64 constants

OpenJDK 25 GA defines TREEIFY_THRESHOLD = 8, UNTREEIFY_THRESHOLD = 6, and MIN_TREEIFY_CAPACITY = 64. A dense list bin may become a red-black tree; a small tree bin after a split may revert to a list.

Do not assume the eighth insertion always treeifies. Current put checks TREEIFY_THRESHOLD - 1; adding the ninth after finding eight list nodes attempts treeification. Below 64, the attempt resizes instead. These are implementation details, not Map or HashMap guarantees. Tree bins limit long collision scans, but well-distributed keys remain essential to expected O(1) operations.

Common HashMap errors

A mutable key can become unreachable through normal lookup even while its node remains in the map:

import java.util.HashMap;

public class Main {
    static final class MutableKey {
        int id;
        MutableKey(int id) { this.id = id; }
        @Override
        public int hashCode() { return id; }

        @Override
        public boolean equals(Object other) {
            return other instanceof MutableKey
                    && id == ((MutableKey) other).id;
        }
    }

    public static void main(String[] args) {
        HashMap<MutableKey, String> map = new HashMap<>();
        MutableKey key = new MutableKey(42);
        map.put(key, "admin");
        System.out.println("before mutation -> " + map.get(key));
        key.id = 99;
        System.out.println("after mutation -> " + map.get(key));
        System.out.println("contains after mutation -> " + map.containsKey(key));
        System.out.println("size -> " + map.size());
    }
}

At length 16, id 42 uses 42 & 15 = 10. After mutation, id 99 searches 99 & 15 = 3. The node remains on its original path, so output is before mutation -> admin, after mutation -> null, contains after mutation -> false, and size -> 1. Make key fields immutable.

Other common mistakes:

• Inconsistent equals and hashCode can make equal lookups miss. Implement and test both.

• get(key) == null cannot distinguish absence from a mapped null. Use containsKey when needed.

• Iteration-order assumptions are brittle. Use LinkedHashMap for insertion order or TreeMap for key order.

Fail-fast iterators detect bugs, not thread safety. For shared mutation, coordinate externally or use a concurrent collection. Catching ConcurrentModificationException is not recovery.

How assessments test HashMap internals

Typical questions ask you to calculate a bucket, distinguish replacement from collision, or trace resize and mutable-key failure. Practise with data structures hashing MCQs without assuming a fixed pattern.

1. At length 16, forced hashes 5 and 21 both use bucket 5: 5 & 15 = 5 and 21 & 15 = 5. At length 32, they use buckets 5 and 21 because the old-capacity bit 16 separates them.

2. At default length 16 and load factor 0.75, the threshold is 16 x 0.75 = 12. The thirteenth distinct insertion triggers a resize. Replacing an existing value does not change size.

3. After map.put("ready", null), get("ready") and get("missing") both return null. containsKey("ready") is true, while containsKey("missing") is false.

For each answer, explain spread, index, hash and equality, then size and threshold effects.

HashMap internals: the short version and next step

• Spread each hash before indexing.

• Use a power-of-two mask to select the bucket.

• Use equals to resolve same-hash candidates.

• A matching key replaces, rather than grows.

• Resize uses the old-capacity bit.

• Tree bins cannot rescue unsound keys.

Run the programs. Replace "BB" with a non-colliding string, then add A16/16 and predict its length-8 bucket first.

If useful, choose the Java course for language concepts, DSA Using Java for maps in algorithms, or the Coding and DSA category to compare routes.