Why Java Switched HashMap Insertion to Tail and How It Affects Concurrency

Background

HashMap implementation changed from JDK 1.7 to JDK 1.8. JDK 1.7 used head insertion during resize, which could create circular linked lists under concurrent resize. JDK 1.8 switched to tail insertion, eliminating that issue and adding red‑black‑tree conversion for long chains.

Head‑Insertion in JDK 1.7

Mechanism

Insertion : e.next = newTable[i]; newTable[i] = e; – new node becomes the bucket head.

Complexity : O(1) per insertion.

Concurrent‑Resize Problem

When multiple threads resize simultaneously, each thread inserts nodes in reverse order, which can produce a cycle:

Original list: A → B → C
Thread A after resize: C → B → A
Thread B after resize: A → B → C → B → A  // circular

The circular list causes get to loop forever, consuming 100 % CPU.

Representative Code (JDK 1.7)

void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (e != null) {
            Entry<K,V> next = e.next;
            int i = indexFor(e.hash, newTable.length);
            e.next = newTable[i];   // head‑insertion
            newTable[i] = e;
            e = next;
        }
    }
}

Tail‑Insertion in JDK 1.8

Mechanism

Insertion : maintain a tail reference; append with tail.next = e; tail = e;. The bucket head is stored in head.

Benefits : preserves original order, prevents cycles, and works with red‑black‑tree conversion.

Sample Transfer Logic (JDK 1.8)

void transfer(Node<K,V>[] newTab) {
    Node<K,V> head = null, tail = null;
    for (Node<K,V> e = oldNode; e != null; e = e.next) {
        e.next = null;               // break old link
        if (tail == null) {
            head = e;
        } else {
            tail.next = e;
        }
        tail = e;
    }
    newTab[index] = head;
}

Concurrency Safety

All threads see the same forward order; no reverse‑order loops.

The explicit tail pointer guarantees that the list end is never lost.

Remaining Risks

Red‑Black Tree Conversion

When a bucket’s chain length reaches 8 and the table size is at least 64, HashMap converts the list to a red‑black tree. Concurrent conversion can corrupt the tree because tree insertion is not internally synchronized.

final void treeifyBin(Node<K,V>[] tab, int hash) {
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize();
    } else if ((e = tab[index]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) hd = p; else { p.prev = tl; tl.next = p; }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null) hd.treeify(tab);
    }
}

Unsynchronized Tail Insertion

Even with tail insertion, if multiple threads modify the same bucket without external synchronization, data loss or broken tail pointers may occur.

Best Practices

Prefer Thread‑Safe Collections

Use ConcurrentHashMap for any shared mutable map. It employs segment locks or CAS to guarantee thread safety.

Map<String,String> map = new ConcurrentHashMap<>();
map.put("key","value");

Avoid Direct Manipulation of HashMap Internals

Do not modify the bucket linked list or tree nodes directly.

Never change head/tail pointers in concurrent code.

Set an Appropriate Initial Capacity

Calculate capacity to reduce resize frequency:

int initialCapacity = (int)((expectedSize / 0.75f) + 1.0f);

Comparison Summary (JDK 1.7 vs JDK 1.8)

Insertion position : head vs tail.

Order preservation : reversed vs original order.

Concurrency safety : risk of circular list vs circular list eliminated.

Red‑black tree support : none vs enabled for chains ≥ 8.

Performance : degrades with many collisions vs improves in high‑collision scenarios.

Typical use case : single‑thread/low‑concurrency vs high‑concurrency/high‑collision.