HashMap高并发死循环问题

当你研究Java并发送一个容器和框架时，当你想使用ConcurrentHashMap时，原因之一是：HashMap中的线程是不安全的，并发执行PUT操作时会导致死亡循环，因为多线程会导致Hashmap的entry 链表构成环形数据结构，一看就会陷入死循环。

1.HashMap添加元素时，HashMap容器​​的扩展会导致原理不再解释，直接附上代码，如下：

/** 
    * 
        * Add elements to the table. If the element is inserted, the Table length is not enough, and the resize method will be called. 
    */  
   void addEntry(int hash, K key, V value, int bucketIndex) {  
Entry<K,V> e = table[bucketIndex];  
       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
       if (size++ >= threshold)  
           resize(2 * table.length);  
   }    
   /** 
        * Resize () method is as follows, it is important to add the elements in the old table to a new table.
    */  
   void resize(int newCapacity) {  
       Entry[] oldTable = table;  
       int oldCapacity = oldTable.length;  
       if (oldCapacity == MAXIMUM_CAPACITY) {  
           threshold = Integer.MAX_VALUE;  
           return;  
       }    
       Entry[] newTable = new Entry[newCapacity];  
       transfer(newTable);  
       table = newTable;  
       threshold = (int)(newCapacity * loadFactor);  
   }  

2.参考上面的代码，介绍了Transfer方法，(介绍)这就是造成死循环的根本原因，结合TRANSFER的源码，讲解死循环的原理，先上TRANSFER代码(这是JDK7的源码)，如下：

/**
     * 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;            ---------------------(1)
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity); 
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } // while 
        }
    }

3.假设：

Map<Integer> map = new HashMap<Integer>(2);  // Only two elements can be placed, where Threshold is 1 (when only one element is filled in the table), that is, the insertion element is 1 when the element is 1 (known by the Addentry method)
// Place 2 elements 3 and 7, to place the element 8 (not equal to 1 after the Hash mapping), can cause expansion

假设放置结果如下：

现在有两个线程A和B，都实现了，即向表中添加元素，即线程a和线程b会看到上面的状态快照。

执行顺序如下：

Execute 1：线程A在Transfer function(1)中执行(在Transfer function代码中标注)。此时栈中的线程a

e = 3
next = 7

执行2：线程B 执行Transfer函数中的While循环，将原表变成新表(线程b自己的栈)，然后写入内存。如下图(假设新的Hash函数下两个元素会映射到同一个位置)

执行三：线程A敲了，然后执行(还是老表看到的)，即从Transfer代码(1)，当前E=3，Next=7，上面已经说明了。

(1)处理元素3，将3放入线程A栈中的新表中(新表在线程A栈中，是线程私有的影响，未施肥线程2)，处理3后的绘图3如下：

(2)线程A复制了元素7，当前E=7，由于线程b被修改，next值已经修改了它的引用，所以NEXT为3，处理后的新表如下图。

(3)由于上面的next=3，那么While循环，即当前进程为3，next为NULL，退出while循环，执行While循环后，new表中的内容如下：

(4)操作完成后会陷入HashMap高并发死循环!