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
hashCodeturns 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
Bucket index comes from the key's hash, not its insertion order — which is why HashMap iteration has no predictable sequence.
- The map holds a
Node[] table, always a power-of-two length. - Each
Nodestores 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.
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
- 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
==orequals. - 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
sizenow 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.