Interview Prep Zoneby CuriouserLabs

Question 1 of 5 · senior level

How does HashMap work internally? Walk through put(), collisions, treeification and resizing.

🎤 Say this first

put(k,v): spread the key's hash (h ^ h>>>16), index with hash & (n-1), then place the entry in that bucket. Collisions chain into a linked list compared via equals(); a chain past 8 nodes (with table ≥ 64) becomes a red-black tree, capping worst-case lookup at O(log n). When size exceeds capacity × 0.75 the table doubles and entries split between index i and i + oldCap — possible only because capacity is a power of two.

The full picture

🎬 HashMap internals: buckets, chains, trees, resize

1 / 5
01234567"cat" → 9Senior follow-up: a mutable key whose hashCode changes after insertion is silently lost — hashCode/equals contract.

A HashMap is an array of buckets (default capacity 16, here 8 for clarity). put("cat", 9) → hash("cat") is spread (h ^ h>>>16) and masked: index = hash & (n-1) → bucket 3.

Buckets, a collision chain, treeification and the power-of-two resize.
  • Hash spreading: (h = key.hashCode()) ^ (h >>> 16) mixes high bits into low bits because the index mask only uses low bits — defends against bad hashCode distributions.
  • Treeify threshold 8, untreeify 6: chosen because with a decent hash, chain length follows a Poisson distribution — 8 collisions is ~1 in 10 million, so trees are a pathological-case defense (including hash-flooding DoS), not the normal path.
  • Resize is expensive: every entry rehashed/moved; pre-size with new HashMap<>(expected / 0.75f + 1) (or HashMap.newHashMap(expected) in 19+) for large known loads.
  • Iteration order: none guaranteed — use LinkedHashMap for insertion/access order (and as an LRU via removeEldestEntry), TreeMap for sorted keys.

🔄 Likely follow-up questions

  • Why must capacity be a power of two, and what does hash & (n-1) do vs %?
  • How does computeIfAbsent differ from get-then-put under concurrency?
  • What changed in Java 8 vs 7 that mitigated hash-collision DoS attacks?