Java HashMap internals

HashMap internals — buckets, hash spreading, treeification at 8, resize

The single most-asked Java interview topic. "Explain how HashMap works internally" appears in a large majority of Java interviews, and the follow-ups go deep. It's also your Stage 1 exit-gate whiteboard item. Give it the full three hours.

---

L-048 · How HashMap works

The structure

An array of buckets. Each bucket is a linked list, or a red-black tree once it grows.

transient Node<K,V>[] table;     // the bucket array — length is ALWAYS a power of two
transient int size;              // number of key-value mappings
int threshold;                   // capacity × loadFactor — when to resize
final float loadFactor;          // 0.75 by default

static class Node<K,V> {
    final int hash;              // the SPREAD hash, cached
    final K key;
    V value;
    Node<K,V> next;              // chain to the next node in this bucket
}

   table (capacity 16)
   ┌────┐
 0 │ ●──┼──▶ [hash|K1|V1|next] ─▶ [hash|K5|V5|null]      ← a collision chain
   ├────┤
 1 │null│
   ├────┤
 2 │ ●──┼──▶ [hash|K2|V2|null]
   ├────┤
 3 │null│
   ├────┤
 ...
15 │ ●──┼──▶ (a TreeNode red-black tree, if this bucket got long)
   └────┘

put — the full walkthrough

This is the answer to the interview question. Learn the six steps.

   1. hash = spread(key.hashCode())
   2. index = (n - 1) & hash                    ← n is the table length
   3. If table[index] is empty → place a new Node. Done.
   4. Else, walk the chain (or tree):
        - if a node's hash matches AND (key == k || key.equals(k)) → REPLACE the value
        - otherwise append at the end
   5. If the chain length reached 8 (and capacity ≥ 64) → TREEIFY that bucket
   6. If ++size > threshold → RESIZE (double capacity, rehash)

Step 1 — hash spreading

static final int spread(int h) {
    return (h = key.hashCode()) ^ (h >>> 16);
}

Why: the index is (n-1) & hash, and for a small table only the low bits of the hash are used. n = 16 means only the low 4 bits matter — the upper 28 bits are discarded entirely.

If two keys differ only in their high bits, they collide despite having completely different hash codes.

   hash A = 0111 1111 1111 1111 0000 0000 0000 0101
   hash B = 0000 0000 0000 0000 0000 0000 0000 0101
                                            & 1111  →  both index 5. COLLISION.

XORing the high 16 bits into the low 16 mixes them in, so high-bit differences influence the index:

h ^ (h >>> 16)        // one shift, one XOR — extremely cheap

This is the highest-value detail to know about HashMap. Most candidates know "it hashes the key"; explaining why the spread exists is a different level of answer.

Step 2 — why the capacity is a power of two

index = (n - 1) & hash          // NOT hash % n

When n is a power of two, (n-1) is a mask of all ones:

   n = 16  →  n-1 = 15 = 0000 1111
   hash & 0000 1111  ≡  hash % 16

A bitwise AND instead of a modulo. % on integers is a division — historically tens of cycles; & is one. On a structure called millions of times, that matters.

It also makes resizing cheap — see step 6.

And note from Day 030: hash % n on a negative hash gives a negative index. & cannot, because it masks off the sign bit. Two reasons for one design choice.

Step 4 — the equality check

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

Three checks, in order, deliberately:

1. p.hash == hash — an int comparison. Cheap, and rejects almost all non-matches instantly.
2. k == key — reference identity. Free, and true for interned strings and cached Integers.
3. key.equals(k) — only reached if the first two didn't settle it.

The cached hash in each Node is what makes step 1 possible — hashCode() isn't recomputed on every comparison.

This is exactly why Day 040's contract matters: if hashCode disagrees with equals, step 1 fails and equals is never even reached. The object is unreachable in the map.

Step 5 — treeification

Since Java 8, a bucket whose chain reaches 8 nodes converts to a red-black tree, provided the table capacity is at least 64. Below 64, it resizes instead — a short table is the more likely cause.

   Chain:  O(n) worst case within the bucket
   Tree:   O(log n)

Why it exists — and this is a security answer, not just performance:

Hash collision DoS. An attacker who can control map keys — HTTP parameter names, JSON field names — and knows your hash function can craft thousands of keys that all hash to the same bucket. Every lookup becomes O(n), and the server melts under a small request. This affected Java, PHP, Python, Ruby and others around 2011–2012.

Treeification bounds the damage at O(log n) instead of O(n).

Untreeify at 6, not 8. The gap prevents thrashing — repeated convert/unconvert at a boundary value.

For tree ordering, keys are compared by hash, then by Comparable if the key type implements it, then by a tie-breaking System.identityHashCode.

Step 6 — resize

threshold = capacity × loadFactor        // 16 × 0.75 = 12

When size exceeds the threshold, capacity doubles and every entry is redistributed.

The Java 8 optimisation, and it's elegant:

Because capacity doubles and is a power of two, the new index differs from the old by exactly one bit — the newly significant one:

   old capacity 16, index = hash & 1111
   new capacity 32, index = hash & 11111
                                   ↑ this bit is new

   if (hash & 16) == 0  →  the entry stays at index j
   else                 →  it moves to index j + 16

So each chain splits into exactly two chains — "lo" and "hi" — with no rehashing at all. One bit test per node.

Before Java 8, resizing rehashed every key and reversed chain order — which under concurrent access could produce an infinite loop in get(), a famous production hang. Java 8 preserves order, which eliminated that particular disaster (though HashMap is still not thread-safe — Day 053).

Why load factor 0.75

A space-time trade-off, and there's a mathematical reason for the number.

Load factor	Collisions	Memory
Low (0.5)	Fewer	More wasted
0.75	Balanced	Balanced
High (1.0)	Many	Compact

Under uniform hashing, bucket occupancy follows a Poisson distribution. At a load factor of 0.75 the probability of a bucket reaching 8 entries is about 0.00000006 — which is precisely why 8 was chosen as the treeify threshold. The JDK source documents this.

Being able to connect 0.75 and 8 through the Poisson distribution is a genuinely strong answer.

Complexity

Case	get / put
Average, good hash	O(1)
Worst case, chained	O(n)
Worst case, treeified	O(log n)
Resize	O(n), amortised into O(1) per op

Sizing it properly

new HashMap<>();                    // capacity 16, resizes at 12
new HashMap<>(1000);                // capacity rounded UP to 1024, resizes at 768 — still resizes!
new HashMap<>((int)(1000 / 0.75) + 1);   // ✅ capacity 2048, no resize for 1000 entries

The constructor argument is initial capacity, not expected size. A common mistake — sizing to your expected element count still triggers a resize at 75%.

(Java 19+ adds HashMap.newHashMap(int numMappings) which does this arithmetic for you.)

---

Write your own

This is the Stage 1 exit-gate item. Implement it before reading further.

public class SimpleHashMap<K, V> {

    static class Node<K, V> {
        final int hash; final K key; V value; Node<K, V> next;
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash; this.key = key; this.value = value; this.next = next;
        }
    }

    private Node<K, V>[] table;
    private int size;
    private int threshold;
    private static final float LOAD_FACTOR = 0.75f;

    @SuppressWarnings("unchecked")
    public SimpleHashMap() {
        table = new Node[16];
        threshold = (int) (16 * LOAD_FACTOR);
    }

    // ---- step 1: spread ----
    private static int spread(Object key) {
        if (key == null) return 0;
        int h = key.hashCode();
        return h ^ (h >>> 16);
    }

    // ---- step 2: index by masking ----
    private int indexFor(int hash) { return (table.length - 1) & hash; }

    public V put(K key, V value) {
        int hash = spread(key);
        int i = indexFor(hash);

        for (Node<K, V> e = table[i]; e != null; e = e.next) {
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) {
                V old = e.value;
                e.value = value;                       // REPLACE
                return old;
            }
        }
        table[i] = new Node<>(hash, key, value, table[i]);   // prepend
        if (++size > threshold) resize();
        return null;
    }

    public V get(Object key) {
        int hash = spread(key);
        for (Node<K, V> e = table[indexFor(hash)]; e != null; e = e.next)
            if (e.hash == hash && (e.key == key || (key != null && key.equals(e.key))))
                return e.value;
        return null;
    }

    // ---- step 6: split each chain using ONE bit ----
    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] old = table;
        int oldCap = old.length, newCap = oldCap << 1;
        Node<K, V>[] neu = new Node[newCap];

        for (int j = 0; j < oldCap; j++) {
            Node<K, V> e = old[j];
            while (e != null) {
                Node<K, V> next = e.next;
                int newIndex = (e.hash & oldCap) == 0 ? j : j + oldCap;   // ← the one-bit test
                e.next = neu[newIndex];
                neu[newIndex] = e;
                e = next;
            }
        }
        table = neu;
        threshold = (int) (newCap * LOAD_FACTOR);
    }

    public int size() { return size; }
    public int capacity() { return table.length; }

    public void printDistribution() {
        int used = 0, max = 0;
        for (Node<K, V> b : table) {
            int len = 0;
            for (Node<K, V> e = b; e != null; e = e.next) len++;
            if (len > 0) used++;
            max = Math.max(max, len);
        }
        System.out.printf("   size=%d capacity=%d bucketsUsed=%d longestChain=%d%n",
                size, table.length, used, max);
    }
}

Then run this

import java.util.*;

public class HashMapDemo {

    // A deliberately terrible hash — every key collides
    record BadKey(int id) {
        @Override public int hashCode() { return 1; }
    }
    record GoodKey(int id) { }        // record generates a proper hashCode

    public static void main(String[] args) {

        // ---- 1. Watch resizing and distribution ----
        System.out.println("--- growth and distribution ---");
        SimpleHashMap<String, Integer> map = new SimpleHashMap<>();
        int lastCap = 0;
        for (int i = 0; i < 100; i++) {
            map.put("key" + i, i);
            if (map.capacity() != lastCap) { map.printDistribution(); lastCap = map.capacity(); }
        }
        map.printDistribution();

        // ---- 2. Prove the spread matters ----
        System.out.println("\n--- why spreading matters ---");
        int h1 = 0x7FFF0005, h2 = 0x00000005;
        System.out.printf("   without spread: %d vs %d → %s%n",
                h1 & 15, h2 & 15, (h1 & 15) == (h2 & 15) ? "COLLIDE" : "differ");
        int s1 = h1 ^ (h1 >>> 16), s2 = h2 ^ (h2 >>> 16);
        System.out.printf("   with spread:    %d vs %d → %s%n",
                s1 & 15, s2 & 15, (s1 & 15) == (s2 & 15) ? "COLLIDE" : "differ");

        // ---- 3. Collision DoS, and treeification saving you ----
        System.out.println("\n--- hash collision attack ---");
        int n = 30_000;
        Map<BadKey, Integer> bad = new HashMap<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) bad.put(new BadKey(i), i);
        System.out.printf("   %,d all-colliding keys: %,5d ms  ← treeified, O(log n)%n",
                n, System.currentTimeMillis() - start);

        Map<GoodKey, Integer> good = new HashMap<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) good.put(new GoodKey(i), i);
        System.out.printf("   %,d well-hashed keys:   %,5d ms%n",
                n, System.currentTimeMillis() - start);

        // ---- 4. Pre-sizing ----
        int m = 2_000_000;
        start = System.currentTimeMillis();
        Map<Integer, Integer> grow = new HashMap<>();
        for (int i = 0; i < m; i++) grow.put(i, i);
        long growTime = System.currentTimeMillis() - start;

        start = System.currentTimeMillis();
        Map<Integer, Integer> sized = new HashMap<>((int) (m / 0.75f) + 1);
        for (int i = 0; i < m; i++) sized.put(i, i);
        long sizedTime = System.currentTimeMillis() - start;

        System.out.printf("%n--- building %,d entries ---%n", m);
        System.out.printf("   default:   %,5d ms  (≈21 resizes)%n", growTime);
        System.out.printf("   pre-sized: %,5d ms  (0 resizes)%n", sizedTime);

        // ---- 5. HashMap is NOT thread-safe ----
        System.out.println("\n--- concurrency ---");
        Map<Integer, Integer> unsafe = new HashMap<>();
        Runnable task = () -> { for (int i = 0; i < 50_000; i++) unsafe.put(i, i); };
        Thread t1 = new Thread(task), t2 = new Thread(task);
        t1.start(); t2.start();
        try { t1.join(); t2.join(); } catch (InterruptedException ignored) {}
        System.out.println("   expected 50000 entries, got " + unsafe.size()
                         + "   ← lost updates (Day 053)");
    }
}

Four results to record:

1. The distribution table as capacity doubles — watch bucketsUsed and longestChain.
2. The spread demonstration — two very different hashes colliding without it, separating with it.
3. 30,000 all-colliding keys still complete quickly — that's treeification doing its job. Try it on Java 7 semantics (a chain) and it would be O(n²) overall.
4. HashMap under two threads loses entries. Day 053's motivation.

---

Common mistakes

Mistake	Correction
"It uses hashCode() % capacity"	It's (n-1) & spread(hash), which requires a power-of-two capacity.
Not knowing why the spread exists	Only the low bits index the table; XOR mixes the high bits down.
"Capacity is a power of two for no reason"	It enables masking instead of modulo, and one-bit resize splitting.
Thinking treeification is only about performance	It's primarily a defence against hash-collision DoS.
Sizing new HashMap<>(expectedSize)	That's capacity. It still resizes at 75%. Divide by the load factor.
Mutating a key after insertion	The entry becomes unreachable (Day 040).
Using HashMap across threads	Not thread-safe. Lost updates, and historically infinite loops.

---

Interview questions

Q: Explain how HashMap works internally.

It's an array of buckets whose length is always a power of two. On put, the key's hashCode is spread by XORing its high 16 bits into the low ones, then the index is computed as (n-1) & hash — a mask rather than a modulo, which the power-of-two capacity makes valid. If the bucket is empty a node is placed; otherwise the chain is walked comparing cached hash first, then reference identity, then equals, replacing on a match. If a chain reaches eight nodes and capacity is at least 64, the bucket becomes a red-black tree. When size exceeds capacity times the load factor of 0.75, capacity doubles and entries are redistributed.

Q: Why is the hash spread?

Because indexing uses only the low bits — with capacity 16, just the low four. Two keys differing only in their high bits would collide despite having very different hash codes. XORing the top sixteen bits into the bottom sixteen mixes high-bit information into the index at the cost of one shift and one XOR.

Q: Why is capacity always a power of two?

So (n-1) is a mask of all ones and the index can be computed with a bitwise AND instead of a modulo, which is far cheaper on a hot path. It also means resizing only shifts entries by one bit — each chain splits into two based on a single bit test, with no rehashing. And unlike %, masking can't produce a negative index.

Q: What happens at eight entries in a bucket?

The bucket converts from a linked list to a red-black tree, provided table capacity is at least 64 — below that it resizes instead. This bounds worst-case lookup at O(log n) rather than O(n). It was added primarily as a defence against hash-collision denial-of-service attacks, where an attacker crafts keys that all land in one bucket. It untreeifies at six to avoid thrashing.

Q: Why is the load factor 0.75?

It balances space against collisions. Under uniform hashing bucket occupancy is Poisson-distributed, and at 0.75 the probability of a bucket reaching eight entries is about six in a hundred million — which is exactly why eight was chosen as the treeify threshold.

Q: How does resizing work?

Capacity doubles. Because it's a power of two, an entry's new index differs from its old by exactly one bit — the newly significant one. Testing hash & oldCapacity decides whether the entry stays at index j or moves to j plus oldCapacity, so each chain splits into two with no rehashing. Before Java 8 resizing rehashed and reversed chains, which could cause an infinite loop under concurrent access.

Q: Is HashMap thread-safe?

No. Concurrent puts lose updates, and on Java 7 concurrent resizing could create a cycle in a bucket chain, causing get to spin forever. Use ConcurrentHashMap.

---

Mini task

1. Implement SimpleHashMap yourself, from scratch, without looking. Exit-gate item.
2. Add treeification: convert a chain to a TreeMap at length 8.
3. Run HashMapDemo and record all four results.
4. Draw the resize bit-split on paper for capacity 16 → 32 with three specific hashes.
5. Compute the correct initial capacity for 10,000 expected entries.

---

Exit questions

1. Give the six steps of put.
2. What does spread do and why is it necessary?
3. Why must capacity be a power of two? Give three reasons.
4. What are the three comparisons in the chain walk, and why in that order?
5. What triggers treeification, what's the capacity precondition, and why does it exist?
6. Why untreeify at 6 rather than 8?
7. Explain the resize bit-split.
8. Why 0.75, and how does it connect to 8?
9. What is the correct initial capacity for n expected entries?
10. What goes wrong with HashMap across threads?

Articulation drill

Whiteboard it, out loud, for five minutes: "Explain how HashMap works internally."

Draw the bucket array. Walk a put. Show a collision. Show treeification. Show the resize bit-split. This is a Stage 1 exit-gate item — practise it until it's fluent, because you will be asked it.

---

Previous: Day 047 · Tomorrow: Day 049 — LinkedHashMap, the LRU cache, and TreeMap's red-black tree