How does HashMap work internally?

The Answer

Say this in the room. 45 seconds.

• HashMap stores entries in an array of buckets, Node<K,V>[] table. The array is not allocated in the constructor — it's created on the first put(), at size 16.
• On put(), the key's hashCode() is spread — h ^ (h >>> 16) — to mix high bits down into the low bits, then the bucket index is (n - 1) & hash. That bitmask works only because capacity is always a power of two.
• Two keys landing in the same bucket collide, and chain into a linked list.
• When a bucket gets long, it converts to a red-black tree, dropping worst-case lookup from O(n) to O(log n).
• When size exceeds capacity × 0.75, the table doubles and every entry is redistributed.
• Lookup is O(1) average, O(log n) worst case. HashMap is not thread-safe.

Understand It

The table is lazy

The constructor allocates nothing. It only records the load factor. The array appears on first insert:

Map<String, Integer> m = new HashMap<>();
// reflection on the private `table` field
System.out.println("before put: " + tableLength(m));
m.put("a", 1);
System.out.println("after put:  " + tableLength(m));

before put: 0
after put:  16

Why: maps get declared and never used all the time — as fields, in DTOs, in config objects. Deferring a 16-slot array costs nothing and saves real memory across a large heap.

Why the hash gets "spread"

The index is computed with a bitmask, not a modulo:

int index = (n - 1) & hash;   // n = table length, always a power of 2

For n = 16, n - 1 is 0b1111 — so only the bottom 4 bits of the hash decide the bucket. Any hashCode() that varies mostly in its high bits would pile every entry into one slot.

So HashMap folds the high half down first:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

One XOR, one shift. Cheap insurance against a badly-distributed hashCode().

Note the key == null branch: a null key hashes to 0, so it always lives in bucket 0. That's why HashMap permits exactly one null key — and any number of null values.

Collisions: list first, tree later

Same bucket → the new node appends to a linked list on that bin. Lookup walks the chain calling equals().

The treeify rule — where nearly every article is wrong

The claim you'll read everywhere is "at 8 nodes the list becomes a red-black tree." That is incomplete, and it's the follow-up interviewers use to separate readers from people who've actually looked.

Two constants govern this:

If the bin hits 8 but the table is smaller than 64, HashMap resizes instead of treeifying. Reasoning: in a small table, a long bin usually means too few buckets, not genuinely pathological hashing. Spreading entries out is cheaper than building a tree.

Forcing every key into one bucket on JDK 21 shows exactly that:

entries= 8  table= 16  bin = Node      ← hit 8, did NOT treeify
entries= 9  table= 32  bin = Node      ← resized instead
entries=10  table= 64  bin = Node      ← resized again
entries=11  table= 64  bin = TreeNode  ← table >= 64, NOW it treeifies

The real rule: bin ≥ 8 AND table ≥ 64.

Tree bins also need ordering. TreeNode compares by hash first, then by Comparable if the key type implements it, and finally falls back to an arbitrary but consistent tiebreak. That's why a key type that is Comparable degrades more gracefully under heavy collision.

Resize

threshold = capacity × loadFactor → 16 × 0.75 = 12. The table doubles when size exceeds it, so the 13th entry triggers it:

size=12  table=16
size=13  table=32

The clever part of the JDK 8+ rewrite: because capacity doubles, an existing entry either stays at index i or moves to i + oldCap. Which one is decided by a single bit test, (e.hash & oldCap) == 0 — no rehashing required. Each bin splits into a "lo" list and a "hi" list, preserving relative order.

That order preservation is not cosmetic. In Java 7 the transfer reversed each chain, and two threads resizing concurrently could weave a circular linked list — a later get() would then spin at 100% CPU forever. The JDK 8 rewrite eliminated that specific livelock.

But that fix removed one symptom, not the thread-safety problem. Concurrent put() on JDK 21 still loses updates and corrupts size, because nothing here is synchronized. Use ConcurrentHashMap.

The contract you inherit

HashMap is only correct if your keys honor the hashCode()/equals() contract:

• Equal objects must return equal hash codes.
• A key's hash must not change while it's in the map.

Break the second and the entry becomes unreachable — the map looks in a bucket the key no longer hashes to. It's still in memory, still counted by size(), and you cannot get() or remove() it. That's the Challenge exercise below.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "You said it treeifies at 8. Always?" No — the table must also be ≥ 64 slots, else it resizes instead. Below 64, a long bin is treated as too-few-buckets rather than bad hashing.

2. "Why is capacity always a power of two?" So the index can be (n-1) & hash instead of hash % n. A bitmask is far cheaper than modulo, and it makes the resize split a single bit test. Pass a non-power-of-two to the constructor and tableSizeFor() silently rounds it up.

3. "What breaks if hashCode() returns a constant?" Nothing breaks — it stays correct, but every entry collides into one bin. You get O(n) until treeify, then O(log n). A hash map degraded into a sorted list.

4. "Is HashMap thread-safe on Java 21? The infinite loop was fixed." The fix removed the circular-list livelock. It did not add synchronization. Concurrent writes still lose updates and corrupt size. Use ConcurrentHashMap — not Collections.synchronizedMap(), which locks the whole map.

5. "Difference between HashMap and ConcurrentHashMap iteration?" HashMap iterators are fail-fast: structural modification during iteration throws ConcurrentModificationException. ConcurrentHashMap is weakly consistent: it never throws, but may or may not reflect concurrent updates.

Code traps

Trap A — predict before you run:

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
m.put("b", 2);
m.put("c", 3);
System.out.println(m);

Trap B:

Map<Integer, String> m = new HashMap<>();
m.put(1, "one");
System.out.println(m.get(1));
System.out.println(m.get(1L));

Common wrong answers

Check Yourself

Q1. A HashMap with default settings. How many put() calls with distinct keys before the table becomes 32?

Q2. Keys all return hashCode() == 7. After 8 inserts, what's in the bin?

Q3. Why does mutating a key's hash-bearing field make the entry unreachable?

Practice