Starting from this post, I'm shifting gears.
The next few blogs will be purely technical — heavier, sharper, with no extra storytelling.
HashMap looks simple on the surface.
But when you go under the hood, especially after Java 8, it’s clear it wasn’t designed for just happy paths.
Here’s the real architecture.
Pre-Java 8: LinkedList for Collisions
Old HashMap = array of buckets.
Each bucket = LinkedList of Entry<K,V> nodes.
Collision handling was straightforward:
hash(key) ➔ find bucket ➔ scan linked list sequentially
No balancing, no optimizations.
| Scenario | Result |
| Low collisions | O(1) lookup |
| High collisions | Degrades to O(n) |
Worst case: All keys land in same bucket → performance collapses.
Java 8+: Treeification at Bucket Level
If a single bucket becomes overcrowded, HashMap doesn’t just let it grow linearly.
It converts that bucket into a Red-Black Tree.
Benefits:
But — treeification is not automatic.
HashMap applies two key thresholds before switching from list ➔ tree.
Treeify Thresholds
| Constant | Meaning |
| TREEIFY_THRESHOLD = 8 | If a bucket holds more than 8 nodes, treeification is considered. |
| MIN_TREEIFY_CAPACITY = 64 | Treeification only allowed if overall table capacity ≥ 64. |
Behavior:
if (bucketSize > 8 && capacity >= 64) {
linkedList ➔ red-black tree
} else if (bucketSize > 8 && capacity < 64) {
resize() ➔ increase buckets
}
Reason for 64 cap:
If the map is small, it's cheaper to spread entries by resizing than by adding tree overhead.
Untreeify Threshold
Not all trees stay forever.
| Constant | Meaning |
| UNTREEIFY_THRESHOLD = 6 | If entries in a treeified bucket fall below 6, revert back to LinkedList. |
Reason:
Trees add unnecessary memory and balancing overhead when few elements remain.
Normal Mode:
Node<K,V>[] table
Treeified Mode:
Buckets are TreeNode<K,V> instead of simple Node<K,V>.
LinkedList nodes ➔ TreeNodes:
When treeified, all nodes inside a bucket are upgraded to TreeNode<K,V> with parent/left/right pointers.
Rebalancing:
Red-Black Tree rules are applied: self-balancing during inserts and deletes inside the tree.
Collision Flow in Java 8 HashMap (Pseudocode Mental Model)
hash = spread(key.hashCode())
bucket = table[hash & (n-1)]
if (bucket == null)
insert new node
else
if (bucket is tree)
treeInsert()
else
linkedListInsert()
if (bucketSize > TREEIFY_THRESHOLD)
if (table.length >= MIN_TREEIFY_CAPACITY)
treeifyBucket()
else
resize()
✅ Notice: Treeification logic is bucket-local, not full-table wide.
Why Red-Black Tree?
Chosen because:
O(log n) worst-case lookup guarantee.
Moderate balancing cost compared to stricter AVL trees.
Predictable performance even under adversarial key distributions (e.g., hash collision attacks).
Decision Table (Snapshot)
| Situation | Action |
| Bucket > 8 nodes & Table ≥ 64 | Treeify |
| Bucket > 8 nodes & Table < 64 | Resize table |
| Tree bucket shrinks < 6 nodes | Untreeify |
Final Thoughts
HashMap isn’t "just a Map."
It’s an adaptive system — switching between lightweight linked lists, heavyweight trees, and full-table resizing depending on the situation.
If you’ve ever wondered why your lookups stay fast even when your app stores millions of entries,
this dance between chaining, treeification, and resizing is the reason.
No premature optimizations.
Only smart, ruthless adaptivity — the way real systems survive scale.
Coming Up Next
In the next post of this Advanced HashMap series,
I’ll break down the equals() and hashCode() contract —
how they silently govern the behavior of every hash-based structure you use, and how even small mistakes can wreck your data structures.
You can read it here…
