How HashMap Handles Collisions (Chaining to Tree at 8)

Fast recall

Quick revision

Core answer

HashMap stores entries in an array of buckets. Collisions are resolved by chaining. Since Java 8, when a bucket's chain exceeds 8 entries (and the table has at least 64 buckets), the chain is converted to a Red-Black tree for O(log n) worst-case lookups instead of O(n).

HashMap handles collisions with chaining — but the implementation evolved significantly in Java 8 to defeat hash-flooding attacks.

Collision chaining (pre-Java 8):

Two keys in the same bucket form a linked list — worst case O(n)
Attackers exploited this: crafted inputs that all hash to one bucket turned a HashMap-backed endpoint into a DoS vector

Java 8 treeification:

Chain exceeds 8 nodes → converts to a Red-Black tree; worst case drops to O(log n)
Chain falls below 6 nodes → reverts to linked list (the gap prevents thrashing)
Treeification only happens when the table has at least 64 slots (MIN_TREEIFY_CAPACITY) — smaller tables resize instead, since doubling redistributes entries better than converting

Spread function:

XOR-mixes upper 16 bits of hashCode() into lower 16 before computing the bucket index
Small tables only use the lowest bits — mixing improves distribution and reduces clustering

I recommend using Java records for HashMap keys — they auto-generate correct hashCode() and equals(), preventing the silent data-loss bug that happens when the contract is broken.

Interview-ready guide

Interview answer

HashMap handles collisions with chaining — but the implementation evolved significantly in Java 8 to defeat hash-flooding attacks.

Collision chaining (pre-Java 8):

Two keys in the same bucket form a linked list — worst case O(n)
Attackers exploited this: crafted inputs that all hash to one bucket turned a HashMap-backed endpoint into a DoS vector

Java 8 treeification:

Chain exceeds 8 nodes → converts to a Red-Black tree; worst case drops to O(log n)
Chain falls below 6 nodes → reverts to linked list (the gap prevents thrashing)
Treeification only happens when the table has at least 64 slots (MIN_TREEIFY_CAPACITY) — smaller tables resize instead, since doubling redistributes entries better than converting

Spread function:

XOR-mixes upper 16 bits of hashCode() into lower 16 before computing the bucket index
Small tables only use the lowest bits — mixing improves distribution and reduces clustering

I recommend using Java records for HashMap keys — they auto-generate correct hashCode() and equals(), preventing the silent data-loss bug that happens when the contract is broken.

03 · Deep dive