During the period of resize, hashMap had the possibility of concurrent dead loops. With curiosity about its formation reasons, the author read many blog posts. Although the reason was generally understood at last, the process of understanding was painful, so there must be an easier way to understand. This is also the motivation for writing this article

Map internal storage structure

The map stores an array internally

An array holds nodes, which are structured as follows

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}
Copy the code

This is what people call the internal implementation of a Map an array, and each element in the array is a linked list

The cause of the dead cycle

The root cause is that a loop is formed in the linked list during expansion and reconstruction, which leads to a dead loop in the loop during subsequent GET

The rebuilt core code is as follows:

/**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
 
            while(null ! = e) { Entry<K,V> next = e.next; / / 1if (rehash) { e.hash = null == e.key ? Zero:hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

Why do they form rings? The table Entry array is shared by threads, while next and E are thread private. Now assume that thread 2 suspends after running 1, and thread 1 does the rebuild and completes. The state of the Entry changes as shown below

conclusion

What is thread unsafe? Thread operation data will first copy from main storage to its local storage, subsequent operations are to operate on local storage, only when necessary will refresh the main memory, so that multiple threads concurrent operation will appear data inconsistency problem

Due to the randomness of program execution, there are many possibilities for thread unsafe programs to have problems. It is not very meaningful to explore the cause, but the key is to understand the root cause.

Blog.csdn.net/zhuqiuhui/a… www.importnew.com/22011.html blog.csdn.net/chenxuegui1… Juejin. Cn/post / 684490… Coolshell. Cn/articles / 96…