HashMap 高并发导致的死循环

for (int j = 0; j < src.length; ++j) {
    
     Entry<K,V> e = src[j];//src 表示原table
        while(null != e) {
        //此处表示取出下一个位置的Entry(键值对)
        Entry<K<V> next = e.next;
        //计算得出在扩容后新数组table中的下标，因为扩容后要重新计算下标
        //未扩容前下标:index = hash(key) & (length-1)
        int i= indexFor(e.hash,newCapacity);
        //根据下标取出在新表newTable中的Entry<K,V>
        e.next = newTable[i];
        //将当前e 赋值给newTable[i](Entry<K,V>)
        newTable[i] = e;
		//将下一个next.Entry 赋值给当前的e	
        e = next;
    }
}

举例说明下：

原

table的信息排列是：

再次添加新元素的时候就需要扩容了，此时我们来类比下上述的代码：

for (int j = 0; j < src.length; ++j) {
    
     Entry<K,V> e = src[j];//src 表示原table
        while(null != e) {
        //next = Entry2
        Entry<K<V> next = e.next;
        //假设计算结果为3；循环第二次：假设Entry2计算的位置也是3
        int i= indexFor(e.hash,newCapacity);
       //第一次Entry1.next = newTable[3]，此时newTable[3]还为null；所以是Entry1.next地址指向null
       //循环第二次：Entry2.next = Entry1
        e.next = newTable[i];
       //newTable[3] = Entry1, 此时e是 Entry1;
       //循环第二次： newTable[3] = Entry2
        newTable[i] = e;
		//Entry1 = Entry2,e 指向了Entry2,好再次循环;
        //循环第二次：e = null,跳出循环
        e = next;
    }
}

变成如下：

上述是属于正常情况的那种，假设我们现在有两个线程同时去 put 元素，二者均发现需要做扩容处理，那么又会出现什么情况呢？

参考阅读网上的博客+自己理解记录

当线程一和线程二同时进行插入的时候刚好达到扩容的条件，然后同时开始进行 Resize 操作。

for (int j = 0; j < src.length; ++j) {
    //src 表示原table
     Entry<K,V> e = src[j];
        while(null != e) {
            Entry<K<V> next = e.next;//假设线程一执行到这里就被调度挂起了
            int i= indexFor(e.hash,newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
    }
}

线程一挂起，线程二继续操作，变成如下：

线程二是 rehash 之后的样子，如上图：

当前线程一来说：

e 是: key(3)

next 是： key(7)

线程一来了，被调度回来了，该人家执行了：


while(null != e) {//再次循环，e:key(7) next:key(3)
    		//假设线程一执行到这里就被调度挂起了,开始继续执行
    		//第二次循环：next = key(3),next 指向key(3)
    		//e:key(3) next:null
           Entry<K<V> next = e.next;
           int i= indexFor(e.hash,newCapacity);//根据线程二的计算不难推出线程一计算的i = 3
           //key(7).next 指向 key(3)
    		//key(3).next 指向 key(7)
           e.next = newTable[i];
    		//first :   newTable[3] = key(3)
    		//second ： newTable[3] = key(7)
    		//third :   newTable[3] = key(3)
           newTable[i] = e;
    		//e 指向key(7)
    		//e = key(3)
    		//e = null//退出循环
           e = next

这样就产生死循环了。

1 2	key(7).next 指向 key(3) key(3).next 指向 key(7)

当我们取出一个key(5) 的一个值时，恰巧也是 int i = 3 , 这样去取，就陷入key(3),key(7) 的死循环中去了。

为了更清晰的展示每一次循环，我决定分开来展示：

第一次：要从这个线程一恢复运行开始说起吧： e: key(3) ; next: key(7)

while(null != e) {
            Entry<K<V> next = e.next;//第一次的时候，线程一被卡住在这里，当时状态是：e:key(3),next:key(7)  这应该都没什么问题
    
    		//根据线程二的计算，这个值也应该是int i = 3
            int i= indexFor(e.hash,newCapacity);
    		//key(3).next = newTable[3], 此时newTable[3]为null, key(3).next指向null
            e.next = newTable[i];
    		//newTable[3] = key(3)
            newTable[i] = e;
    		//e = key(7),e指向key(7)
            e = next
}

OK, 由于e = key(7) 不为null ,循环继续：

第二次循环：经过上述循环，此时 e: key(7),next: key(3)

由于线程二已经改变了这个整体table 的结构，当遍历到key(7) 时， next: key(3)

while(null != e) {//e:key(7) 
    		//next = key(3)
            Entry<K<V> next = e.next;
    		//int i = 3
            int i= indexFor(e.hash,newCapacity);
    		//key(7).next = key(3) , key(7).next指向key(3)
            e.next = newTable[i];
    		//newTable[3] = key(7)
            newTable[i] = e;
    		//e = key(3) e指向key(3),不为null,循环继续
            e = next
}

第三次循环：e : key(3) next:null

while(null != e) {//e:key(3) 
    		//next = null next指向null
            Entry<K<V> next = e.next;
    		//int i = 3
            int i= indexFor(e.hash,newCapacity);
    		//key(3).next = key(7) key(3).next指向key(7)
            e.next = newTable[i];
    		//newTable[3] = key(3)
            newTable[i] = e;
    		//e = null, 循环结束
            e = next
}

此时 e : null, next:null.

1 2	//key(7).next指向key(3) //key(3).next指向key(7) 这里产生死循环

图就是这样的：最后newTable[3] = key(3)

over.