Skip to main content
PreparationZone Logo
PrepZone

How HashMap Works Inside

Buckets, collision chains, treeification and resizing — the most asked internals question there is.

Pass checkpoint below

Read these first

Why this matters

  • This is the most asked internals question in Java interviews, and the answer touches hashing, collisions, tree conversion and resizing in one coherent story.
  • The failure modes are real: a poor hashCode turns O(1) lookups into O(n) scans, and a mutable key loses data.
  • Understanding resize cost is what makes pre-sizing a map feel obvious rather than pedantic.

The structure

table — array of buckets
bucket 0empty
bucket 1"asha" → 30
bucket 5 — collision chain
"ravi" → 24next →
"neha" → 29next → null
bucket 9 — treeified
Red-black treeMore than 8 entries: lookup becomes O(log n)

Bucket index comes from the key's hash, not its insertion order — which is why HashMap iteration has no predictable sequence.

The hash picks a bucket. Keys that land in the same bucket form a short list, and once a bucket grows past eight entries it becomes a balanced tree so lookups stay fast.
  • The map holds a Node[] table, always a power-of-two length.
  • Each Node stores the hash, the key, the value and a next pointer.
  • Nodes landing on the same index form a chain.
  • A chain that grows past a threshold is converted into a red-black tree.

Finding the bucket

Three steps turn a key into an array index.

Java
Loading compiler…

Step 3 is the reason the table length is a power of two. For length 16, length - 1 is 0b1111, so the mask keeps the lowest four bits — exactly a modulo, computed as a single bitwise AND.

Step 2 exists because of step 3. Masking only looks at the low bits, so two keys differing only in their high bits would collide every time. XOR-ing the top 16 bits down mixes that information into the part that is actually used.

put, step by step

Java
Loading compiler…
  • Compute the spread hash and mask it to an index.
  • If the bucket is empty, store a new node there. Done.
  • If the bucket is occupied, walk the chain. For each node, compare the stored hash first, then compare keys with == or equals.
  • If a node matches, replace its value and return the old one.
  • If no node matches, append a new node at the end of the chain.
  • If the chain has reached 8 nodes and the table is at least 64 long, treeify the bucket.
  • If size now exceeds capacity × load factor, resize.

The hash comparison before equals is a deliberate optimisation: comparing two int values is far cheaper than calling equals, and unequal hashes guarantee unequal keys.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 6 sections

  • get, step by step
  • Treeification
  • Resizing
  • Why the hashCode contract matters here
  • null handling and the family
  • Common misreadings

Test yourself

Answer these before moving on — recall is what makes it stick.