---

🟢 Junior Level

Short Interview Answer (30 Seconds)

To resolve collisions, HashMap uses the classic Separate Chaining algorithm, augmented in Java 8 by a hybrid tree structure.

When two distinct keys map to the same bucket index:

1. Singly Linked List (Java 8+ Tail Insertion): The new entry is appended to the end (tail) of the bucket’s collision chain via the Node.next reference.
2. Red-Black Tree (Treeification): If the number of entries in a single bucket reaches 8 and the total table capacity is at least 64, the linked list automatically converts into a balanced Red-Black Tree (TreeNode).
3. Lookup: When get() is called, HashMap locates the bucket, traverses the list or tree, first checking the cached primitive hash (p.hash == hash), and then confirming key identity/equality (k == key || key.equals(k)).

---

Comparison Table: Collision Handling in Java 7 vs. Java 8+

Characteristic	Java 7	Java 8+
List Insertion Strategy	Head Insertion (Prepended)	Tail Insertion (Appended to end)
Deep Collision Data Structure	Pure Singly Linked List	Red-Black Tree (TreeNode)
Worst-Case Search Complexity	$O(n)$	$O(\log n)$
Multi-Threaded resize() Bug	Caused infinite circular loops (100% CPU lockup)	Circular loops eliminated (though data race loss remains)
Treeification Conditions	None (always lists)	$\ge 8$ bucket items AND table capacity $\ge 64$

---

Java 21 Demonstration

import java.util.HashMap;

public class CollisionResolutionDemo {
    public static void main(String[] args) {
        HashMap<KeyWithCollision, String> map = new HashMap<>();

        KeyWithCollision k1 = new KeyWithCollision("id1", 42);
        KeyWithCollision k2 = new KeyWithCollision("id2", 42); // Identical hashCode!
        KeyWithCollision k3 = new KeyWithCollision("id3", 42); // Identical hashCode!

        // All three keys land in the exact same bucket:
        map.put(k1, "Value-1"); // Head node
        map.put(k2, "Value-2"); // Appended to tail of k1
        map.put(k3, "Value-3"); // Appended to tail of k2

        // Lookup correctly isolates target values via equals():
        System.out.println("k2 -> " + map.get(k2)); // Value-2
        System.out.println("Total map size: " + map.size()); // 3
    }

    record KeyWithCollision(String id, int fixedHash) {
        @Override
        public int hashCode() {
            return fixedHash; // Synthetic collision
        }
    }
}

---

🟡 Middle Level

Step-by-Step putVal Traversal Under Collisions

When the computed bucket index is already occupied, OpenJDK HotSpot executes the following collision loop:

// Snippet from HotSpot HashMap.putVal():
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        // Reached tail of linked list: append new node
        p.next = newNode(hash, key, value, null);
        // If chain length reached 8 (binCount >= 7)
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
        break;
    }
    // If key already exists: overwrite its value
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

---

Dual Conditions for Treeification (treeifyBin)

A widespread misconception is that reaching 8 items in a bucket always creates a tree. This is false:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // If overall table capacity is LESS than 64: NO TREE IS CREATED!
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // Doubles the table instead of treeifying!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Convert linked list nodes to TreeNode instances
    }
}

1. TREEIFY_THRESHOLD = 8: Bucket list length must be at least 8;
2. MIN_TREEIFY_CAPACITY = 64: Total table capacity must be at least 64.
   If capacity is below 64 (e.g., standard initial capacity 16 or 32), HashMap assumes the collision is due to table overcrowding and calls resize() to redistribute elements across twice as many buckets.

---

Untreeification and the Hysteresis Gap

A Red-Black Tree is a temporary defense mechanism. If entries are removed (remove()) or split during table expansion (resize()), a tree can revert back to a standard singly linked list:

• Treeification Threshold: $\ge 8$ elements;
• Untreeification Threshold: $\le 6$ elements (UNTREEIFY_THRESHOLD).

Why the Gap Between 6 and 8 (Hysteresis):

If both thresholds were identical (e.g., 8 to treeify and 7 to untreeify), continuous alternating insertions and deletions of an 8th element would trigger costly back-and-forth conversions (structure flapping / churning). The 2-element gap stabilizes performance against minor fluctuations.

---

🔴 Senior Level

Dual Architecture of TreeNode: Tree and List Concurrently

In OpenJDK HotSpot, TreeNode possesses a unique dual structure:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // Parent pointer in Red-Black Tree
    TreeNode<K,V> left;    // Left child pointer
    TreeNode<K,V> right;   // Right child pointer
    TreeNode<K,V> prev;    // Previous pointer in doubly linked list
    boolean red;           // Node color (true = Red, false = Black)
    // Inherited from HashMap.Node: final int hash, final K key, V value, Node next
}

TreeNode maintains two distinct data structures simultaneously:

1. Pointers left, right, and parent form a balanced Red-Black Tree for logarithmic lookups ($O(\log n)$);
2. Pointers next and prev maintain a doubly linked list connecting all nodes in the bucket!

Architectural Rationale for Dual Structure:

When resizing splits a bucket into two halves based on (e.hash & oldCap) == 0, HotSpot avoids complex in-order tree traversals. Instead, it iterates through the nodes as a flat doubly linked list via e.next. If a resulting partition has $\le 6$ elements, it untreeifies into plain Nodes instantly without tree destruction overhead.

---

Mechanics of the Java 7 Multi-Threaded Infinite Loop Bug

Why was using HashMap across multiple threads notoriously catastrophic in Java 7?

Root Cause: Head Insertion (Reversing Element Order):

In Java 7, the transfer() method during table resizing inserted elements at the head of the new bucket, reversing their relative order ($A \to B$ became $B \to A$).

Initial bucket state: [ A ] ──► [ B ] ──► null

1. Thread 1 starts resizing: reads e = A, notes next = B. At this exact moment, the OS context-switches Thread 1 to sleep.
2. Thread 2 completes a full resize uninterrupted:
   • Prepends A into the new table;
   • Prepends B before A (at the head). The list order is now inverted:

     New Table: [ B ] ──► [ A ] ──► null
     

3. Thread 1 wakes up. In its local registers, e = A, next = B. It inserts A, then proceeds to process B.
4. While manipulating pointers, A.next is forced to point to B, while B.next already points back to A.
5. A circular loop is forged: A ──► B ──► A ──► B ...
6. Any subsequent call to map.get() or map.put() targeting that bucket enters an infinite while(e != null) loop, consuming 100% of a CPU core indefinitely.

In Java 8+, switching to Tail Insertion and using bitwise partitioning (loHead/hiHead) preserves relative element order, making cyclic pointer corruption topologically impossible (although data races and silent lost updates can still occur).

---

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

HashMap resolves collisions via Separate Chaining. In Java 8+, colliding elements are appended to the tail of the bucket chain (Tail Insertion), eliminating the Java 7 circular loop bug. If a bucket’s chain length reaches 8 and overall capacity is $\ge 64$, the bucket treeifies into a Red-Black Tree (TreeNode), capping search complexity at $O(\log n)$. If capacity is under 64, resize() is invoked instead. When bucket occupancy drops to $\le 6$, the tree reverts to a singly linked list (hysteresis).

---

2. 4 Tricky Questions with Deep Answers

Question 1: Why does TreeNode simultaneously maintain tree pointers (left, right, parent) and list pointers (next, prev)?

Answer: This dual architecture optimizes table resizing and untreeification. Maintaining list pointers allows HashMap.resize() to traverse tree nodes as a simple flat linked list in linear time $O(k)$ rather than executing complex tree traversals. If splitting the bucket leaves $\le 6$ nodes in a partition, converting back to standard Node instances is performed in a single pass without tree decomposition.

Question 2: Exactly how did concurrent resizing in Java 7 produce an infinite CPU loop, and why did Java 8 tail insertion fix it?

Answer: Java 7 used Head Insertion during transfer(), which inverted node order in the new bucket ($A \to B$ became $B \to A$). If Thread 1 paused after reading $A$ and $B$, while Thread 2 completed resizing and inverted the pointers, Thread 1 would subsequently set $A.next = B$ while $B.next = A$ already held true. This formed a cyclic pointer graph. Subsequent lookups in that bucket would traverse while (e != null) forever at 100% CPU. Java 8 uses Tail Insertion and lo/hi queues, preserving initial element order and preventing cyclic graph creation.

Question 3: Under what exact conditions does a Red-Black Tree convert back into a linked list?

Answer: Untreeification occurs in two situations:

1. During Table Resize (resize()): If a treeified bucket splits into lo and hi sub-buckets, and either resulting partition has $\le 6$ elements (UNTREEIFY_THRESHOLD), that partition reverts to a list.
2. During Element Removal (remove()): If removing an entry shrinks the tree below a structural threshold (specifically, if root, root.left, root.right, or root.left.left is null, indicating approximately 2 to 6 nodes depending on balance), untreeify() converts the tree back into a list.

Question 4: How does HashMap search inside a TreeNode when keys do NOT implement Comparable?

Answer: When keys do not implement Comparable<K>, TreeNode.find() executes an exhaustive fallback:

1. Compares hashes: if hash < current.hash, branches left; if greater, branches right;
2. If hashes match and k == key || key.equals(k), returns the match;
3. If hashes match but equals returns false, it initiates a dual-branch recursive search: it recursively explores the left subtree, and if no match is found, explores the right subtree.

---

3. Common Pitfalls and Red Flags

❌ “Java 8 prepends colliding elements to the head of the bucket list.”
Correction: Java 8+ appends to the tail of the list (Tail Insertion) to preserve element order and eliminate infinite loops.

❌ “Reaching 8 elements in a bucket always creates a Red-Black Tree.”
Correction: Only if total table capacity table.length >= 64. If capacity is below 64, resize() is triggered instead.

❌ “Treeification makes HashMap thread-safe.”
Correction: TreeNode operations are not synchronized. Concurrent writes will corrupt tree invariants and lead to lost updates.

---

4. Related Questions

• What is a Collision in HashMap
• What Happens When 8 Elements Are Reached in One Bucket
• What is the equals() and hashCode() Contract
• How HashMap Works in a Multi-threaded Environment
• What is ConcurrentHashMap and How Does It Differ from HashMap