🟢 Junior Level

When 8 elements land in one bucket, HashMap decides to optimize the search. But the transition to a tree doesn’t always happen!

(Behavior described for Java 8+. In Java 7, treeification did not exist.)

What happens:

1. HashMap checks the total table size
2. If the table has fewer than 64 buckets — it resizes the table
3. If the table has 64 or more — the list converts to a tree

Why: Resize is preferred over treeification: when the table doubles, elements with the same hashCode spread across TWO different buckets (checked by one bit), which may eliminate the collision entirely. A tree only optimizes search within one bucket, but doesn’t resolve the collision.

Example:

// Full scenario:
// capacity=16, threshold=12 → 8 elements < 12 → resize does NOT happen
// At 13th element → resize to 32 → still < 64 → treeification does NOT trigger
// At 25th element → resize to 64 → now >= 64 → treeification TRIGGERS

🟡 Middle Level

The treeifyBin() Method and the 64 Condition

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();  // Increase the table
else {
    // Actual tree conversion
}

Parameters:

• TREEIFY_THRESHOLD = 8 — trigger for calling treeifyBin()
• MIN_TREEIFY_CAPACITY = 64 — minimum table size for tree
• UNTREEIFY_THRESHOLD = 6 — reverse transition

Why Exactly 8?

The probability of a bucket with 8 elements at loadFactor 0.75 and a good hashCode: 0.00000006 (Poisson distribution). The appearance of 8 elements is an anomaly.

Why the Gap Between 8 and 6? (Hysteresis)

If the thresholds were 8 and 7, constantly adding/removing the 8th element would cause HashMap to endlessly rebuild the structure. A gap of 2 ensures stability.

Performance Impact

Metric	List	Tree
Search (8 elements)	8 comparisons	3 comparisons
Search (1024 elements)	1024	10
Insertion	Fast	Slower (balancing)
Memory	~32 bytes/Node	~64 bytes/TreeNode

Common Mistakes

1. Thinking 8 elements = always a tree — also requires capacity >= 64
2. Ignoring the signal — 8 collisions mean a poor hashCode()

Treeification is a Problem Signal

If you see treeification in production — this isn’t “HashMap working as designed”, it’s an indicator of a problem. Either the key’s hashCode() is broken, or a Hash Flooding Attack is underway (an attacker deliberately creates collisions).

🔴 Senior Level

Conversion Process

1. All Nodes are replaced with TreeNodes
2. The list is converted to a doubly-linked one (prev is added)
3. A red-black tree is built with balancing

Red-black tree — a binary tree where each node is ‘colored’ red or black. Coloring rules guarantee balance: the height of the left and right branches differs by no more than 2x.

TieBreakOrder — a ‘tie-breaking’ mechanism: when two keys have the same hash and don’t implement Comparable, Java compares via System.identityHashCode() or class names.

When searching in the tree:

// 1. Compare by hash
// 2. If hashes are equal and key implements Comparable — use compareTo()
// 3. If not — tieBreakOrder() via System.identityHashCode()

TieBreakOrder

When keys don’t implement Comparable:

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
    return d;
}

This is a fallback mechanism for building a deterministic tree.

Architectural Trade-offs

Why not create a tree right away?

• TreeNode is 2x heavier than Node
• For 2-7 elements, a list is faster (less overhead)
• Treeification is protection against anomalies, not a standard mode

Edge Cases

1. Multi-threaded resize — two threads may simultaneously trigger treeification; ConcurrentHashMap solves this via CAS + synchronized on bucket head
2. null key — always in table[0], at 8 null keys (impossible since null is only one) — theoretically, a tree for null is never created

Performance

• Treeification: O(k * log k) for k elements
• At 1024 collisions: search takes 10 operations vs 1024 (list) — 100x gain
• But insertion slows by ~30-50% due to balancing

Production Monitoring

Anomalous treeification = problem indicator:

• Check hashCode() of your keys
• Possible Hash Flooding Attack
• In JFR, check HashMap.CollisionRate

---

🎯 Interview Cheat Sheet

Must know:

• TREEIFY_THRESHOLD = 8, MIN_TREEIFY_CAPACITY = 64, UNTREEIFY_THRESHOLD = 6
• At 8 elements AND capacity < 64 — resize, NOT tree
• At 8 elements AND capacity >= 64 — treeification (list → red-black tree)
• Hysteresis (8 → tree, 6 → list) prevents structure bouncing
• TieBreakOrder: if keys are not Comparable — System.identityHashCode() is used
• Implementing Comparable for keys speeds up treeification
• Treeification in production = problem signal (bad hashCode or attack)

Common follow-up questions:

• Why is resize preferred over tree? — resize spreads elements across different buckets, tree only optimizes search within one
• What is TieBreakOrder? — fallback for tree building when keys aren’t Comparable
• Can a null key create a tree? — no, null is only one, no self-collisions
• What is the complexity of treeification? — O(k * log k) for k elements

Red flags (DO NOT say):

• “8 elements = always a tree” — also requires capacity >= 64
• “Treeification is normal operation” — it’s anomaly protection
• “Tree solves the collision problem” — no, it only optimizes search within a bucket

Related topics:

• [[02. What is a Bucket in HashMap]]
• [[05. How HashMap Handles Collisions]]
• [[17. What is Capacity in HashMap]]
• [[18. When Does Rehashing Occur in HashMap]]