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.

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:

• Lookup time inside a bucket drops from O(n) ➔ O(log n)

• Write/update operations remain manageable via tree balancing.

But — treeification is not automatic.
HashMap applies two key thresholds before switching from list ➔ tree.

---

Treeify Thresholds

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.

Reason:
Trees add unnecessary memory and balancing overhead when few elements remain.

---

What Happens Internally During Transformations

• 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)

---

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…