review

In JDK7, HashMap:: Transfer creates an infinite loop in multithreaded cases. In JDK8, however, HashMap gets a big makeover. Deadlocks in transfer are resolved. In addition, the storage structure of Table is changed from array + linked list in 7 to array + linked list/red-black tree.

In JDK8, HashMap is stored using arrays and linked lists in preference. When the number of Hash conflicts reaches eight, the Table is stored as an array and a red-black tree to improve the query efficiency in Hash conflicts.

An infinite loop problem in JDK7

HashMap dead-loops occur mainly during capacity expansion. The core code of deadlock is as follows. For the convenience of analysis, part of the code is omitted and the number of lines is marked on the important code for the convenience of later analysis.

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null ! = e) {// statement 1 Entry<K,V> next = e.next; Int I = indexFor(e.hash, newCapacity); e.next = newTable[i]; NewTable [I] = e; // statement 4 e = next; // statement 5}}}Copy the code

First, the conclusion. After an infinite loop occurs, the CPU spikes and the data in memory may look like this:

First loop, go! E points to element A and next points to a.next. Note that a.ext is still B at this point, because thread 1’s changes are not visible to thread 2. So next points to B. The data in memory after statement 5 is executed is as follows

Thread 2 loops for the second time, start!

Thread 2 loop 3, go!

The improvement of JDK8

In JDK8, I’ve improved on the endless loop in 7, and I’ve simplified the core code to make it easier to understand

private Node<K, V>[] resize() {/ /... some operation Node<K,V> loHead = null, loTail = null; Node<K,V> next;do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {
            if (loTail == null)
                loHead = e;
            elseloTail.next = e; loTail = e; }}while((e = next) ! = null);if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
    }
    
    // .... some operation
    return newTab;
}
Copy the code

The essential cause of deadlocks in 7 is the reordering of linked lists in reverse order, which is eliminated in JDK8. So in the case of multiple threads, the worst effect of this code is lost data, not an infinite loop.

An infinite loop problem under JDK8

Even though JDK8 is optimized for HashMap, it still creates an infinite loop in multithreading. With reference to the test code and stack information that HashMap also looped in 1.8, let’s start the analysis. The infinite loop occurs in the HashMap::TreeNode::root method, which is coded as follows

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            returnr; r = p; }}Copy the code

We can roughly deduce that the data structure in its memory should be as follows

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
    TreeNode<K,V> l, pp, lr;
    if(p ! = null && (l = p.left) ! = null) {// statement 1if((lr = p.left = l.right) ! = null) // statement 2 lr. Parent = p; / / 3if((pp = l.parent = p.parent) == null) // statement 4 (root = l).red =false;
        else if (pp.right == p)
            pp.right = l;
        elsepp.left = l; l.right = p; Statement 5 p.parent = l; }return root;
}
Copy the code

This code handles the right rotation of subtrees in four scenarios. Details are as follows. Here we ignore the discoloration and focus on the transformation of data.

At this point, also when both threads start right rotation at the same time, assume scenario 2. The data in memory is now (all unlabeled are assumed to be null)

extension

Data addressing is simplified in JDK8, and bit manipulation in resize is clever enough to be worth a look.

The left rotation core code is shown below

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    if(p ! = null && (r = p.right) ! = null) {if((rl = p.right = r.left) ! = null) rl.parent = p;if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r;
        else
            pp.right = r;
        r.left = p;
        p.parent = r;
    }
    return root;
}
Copy the code

This code handles left rotation of subtrees in four cases, as detailed below