How Does HashMap Work Internally? (Java Interview Deep Dive)

Why this is the most-asked Java internals question

"How does HashMap work internally?" appears in nearly every Java interview because it has verifiable depth: it can be answered in one sentence or in five layers, and the layer where you stop tells the interviewer your level precisely. It also touches hashing, equality, memory and even concurrency, so a single question lets them probe several fundamentals at once.

This page gives you the full narration — put, get, collisions, treeification, load factor and resize — in the order interviewers expect. Practice it until you can whiteboard it without pausing.

How to narrate it in an interview

Answer from the data structure outward: "a HashMap is an array of buckets; each bucket holds entries whose keys hash to that index." Then trace an operation step by step rather than listing facts. The narration — hash, spread, index, walk the bucket, compare hash-then-equals — is what earns the marks, because it proves you understand the mechanism, not just the vocabulary.

Q1. What is the internal structure of a HashMap?

A HashMap holds a Node[] array — the bucket table. Each Node stores the key, value, the key's cached hash, and a next pointer forming a linked list for that bucket. When a bucket grows large it becomes a red-black tree of TreeNodes instead of a list.

The cached hash inside each node is an easy detail to miss and a good one to mention: hashes are computed once at insertion and stored, so resize does not recompute them. The array is the map; buckets are its slots.

Interview note: Follow-up: "what is the initial capacity?" 16 buckets by default, with a 0.75 load factor, so the first resize happens at 12 entries.

Q2. Walk through what happens on put(key, value).

HashMap calls key.hashCode(), spreads the bits, computes the bucket index with (n-1) & hash, and goes to that bucket. Empty bucket: insert a new node. Non-empty: walk the chain comparing hash then equals — replace the value on a match, append a new node otherwise. After insertion it checks whether to treeify the bucket or resize the table.

// conceptual sketch of the index computation
int h = key.hashCode();
int spread = h ^ (h >>> 16);     // mix high bits into low bits
int index = (n - 1) & spread;    // bucket, n is a power of two

The bit-spread step (h ^ (h >>> 16)) exists because (n-1) & hash only uses the low bits; mixing the high bits in reduces collisions when hashCodes differ mainly in their upper bits.

Interview note: Trap: "does put replace on equal keys or add a duplicate?" It replaces the value when the key equals an existing one and returns the old value; keys never duplicate.

Q3. Why must equal keys have equal hashCodes?

Because get finds the bucket via hashCode() first and only searches that bucket. If two equal objects produce different hashes, an entry stored via one instance is looked up in a different bucket via the other — and the lookup fails even though the keys are "equal."

class Point {
    int x, y;
    // equals overridden but hashCode NOT
}
Map<Point, String> m = new HashMap<>();
m.put(new Point(1, 2), "home");
m.get(new Point(1, 2));   // null — different default hashCode, wrong bucket

This is the single most common self-inflicted HashMap bug, and the reason keys should be immutable — if a key's fields change after insertion, its hash no longer matches its bucket and the entry is effectively lost while still consuming memory.

Interview note: Follow-up: "the mutated key's entry is stuck — how do you retrieve it?" Iterate entrySet(); only hashed lookup is broken, so a full scan still finds it.

Q4. How are collisions handled, and what is treeification?

Colliding keys share a bucket as a linked list. When a single bucket's chain exceeds 8 nodes AND the table has at least 64 buckets, that bucket converts to a red-black tree, turning worst-case lookup in the bucket from O(n) to O(log n). It reverts to a list when it shrinks below 6 nodes.

The two thresholds — 8 to treeify, 6 to untreeify — leave a gap so a bucket hovering at the boundary does not flip-flop on every add and remove. The 64-bucket precondition matters: below it, HashMap resizes instead of treeifying, because a tiny table with a long chain is better fixed by spreading entries.

Interview note: Trap: "chain hits 8 in a 16-bucket table — does it treeify?" No — the table is under 64 buckets, so it resizes first; treeification needs both conditions.

Q5. What do load factor and initial capacity control?

Capacity is the bucket count; load factor (default 0.75) is the fill ratio that triggers resize. When size > capacity × loadFactor, the table doubles and every entry is redistributed. Lower load factor wastes memory on empty buckets; higher piles up collisions.

The practical detail: new HashMap<>(16) resizes at 12 entries, not 16. To hold N entries without a resize, size for N / 0.75:

Map<String, User> byId = new HashMap<>(
    (int) Math.ceil(10_000 / 0.75));   // holds ~10k without resizing

Pre-sizing matters because each resize is an O(n) redistribution — avoiding a dozen of them on a known-large map is a real optimization.

Interview note: Follow-up: "does resize recompute hashCodes?" No — hashes are cached in the nodes; only the index mapping changes because n changed.

Q6. Explain what happens during a resize.

On resize the table doubles, preserving the power-of-two invariant. In Java 8+, each entry moves to either its old index or old index plus old capacity — decided by a single bit of the hash — so entries split cleanly between the "low" and "high" halves without recomputing hashes.

This one-bit split is why doubling keeps rehashing cheap and why capacity must stay a power of two. It also fixed the Java 7 flaw where concurrent resize could invert a bucket's list and create an infinite loop.

Interview note: Trap: "which bit decides the new index?" The bit at the position equal to the old capacity: if (hash & oldCap) == 0 the entry stays; otherwise it moves to index + oldCap.

Q7. Why is capacity always a power of two?

So the index computation (n-1) & hash works as a fast modulo. When n is a power of two, n-1 is all ones in binary, and the AND keeps exactly the low bits of the hash — equivalent to hash % n but far cheaper. If n weren't a power of two, the AND would skip buckets and distribute unevenly.

If you pass a non-power-of-two initial capacity, HashMap rounds it up to the next power of two internally. This invariant is what makes both indexing and resize efficient, so it ties Q2, Q5 and Q6 together.

Interview note: Follow-up: "you pass capacity 17 — what happens?" It becomes 32, the next power of two; HashMap never uses a non-power-of-two table size.

Q8. How does HashMap differ from ConcurrentHashMap under threads?

HashMap is not thread-safe: concurrent writes can lose updates or corrupt the structure. ConcurrentHashMap allows concurrent reads and fine-grained locked writes (per-bin locking), forbids null keys and values, and offers atomic compound operations — putIfAbsent, compute, merge — that HashMap plus external synchronization cannot match cleanly.

The deeper point is that wrapping a HashMap in Collections.synchronizedMap serializes all access and still leaves check-then-act sequences racy. ConcurrentHashMap's atomic methods exist to close that compound-operation gap without a global lock.

concurrentCounts.merge(key, 1, Integer::sum);   // atomic, no external lock

Interview note: Trap: "is ConcurrentHashMap's size() exact under concurrent updates?" No — it is an estimate; needing an exact live count usually signals a design smell.

How to prepare

Whiteboard put, get and resize until you can narrate them without pausing — that fluency is exactly what the question measures. Then write the failure demos yourself: a key class missing hashCode(), a mutable key you change after insertion, and a map you deliberately pre-size to avoid resizes. Each takes five minutes and permanently inoculates you against the trap versions.

Pair this with the Java coding questions, since hashing underlies the duplicate and frequency problems, and the multithreading questions for the ConcurrentHashMap follow-ups. To rebuild the collections foundations end to end, work through the Java learning path before your next round.