问题来源

在JDK1.7下在多线程环境中并发的使用HashMap会造成死循环的问题。
如下测试类：

  1. public class HashMapInfiniteLoop {  
  3.     private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
  4.     public static void main(String[] args) {  
  5.         map.put(5， "C");  
  7.         new Thread("Thread1") {  
  8.             public void run() {  
  9.                 map.put(7, "B");  
  10.                 System.out.println(map);  
  11.             };  
  12.         }.start();  
  13.         new Thread("Thread2") {  
  14.             public void run() {  
  15.                 map.put(3, "A);  
  16.                 System.out.println(map);  
  17.             };  
  18.         }.start();        
  19.     }  
  20. }

其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。此时会产生死循环的问题。

问题分析

扩容函数resize源码如下：

  1.     void resize(int newCapacity) {   //传入新的容量
  2.         Entry[] oldTable = table;    //引用扩容前的Entry数组
  3.         int oldCapacity = oldTable.length;
  4.         if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
  5.             threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
  6.             return;
  7.         }
  9.         Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
  10.         transfer(newTable);                         //！！将数据转移到新的Entry数组里
  11.         table = newTable;                           //HashMap的table属性引用新的Entry数组
  12.         threshold = (int) (newCapacity * loadFactor);//修改阈值
  13.     }
  15.     void transfer(Entry[] newTable) {
  16.         Entry[] src = table;                   //src引用了旧的Entry数组
  17.         int newCapacity = newTable.length;
  18.         for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
  19.             Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
  20.             if (e != null) {
  21.                 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
  22.                 do {
  23.                     Entry<K, V> next = e.next;
  24.                     int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
  25.                     e.next = newTable[i]; //标记[1]
  26.                     newTable[i] = e;      //将元素放在数组上
  27.                     e = next;             //访问下一个Entry链上的元素
  28.                 } while (e != null);
  29.             }
  30.         }
  31.     }

扩容流程是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
image.png
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
image.png
image.png
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
image.png
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。

参考链接

https://tech.meituan.com/2016/06/24/java-hashmap.html