jdk1.7HashMap链表头插法导致的死循环

我不是女神ヾ 2022-01-28 08:51 280阅读 0赞

jdk1.7的HashMap的源码分析参考我之前整理的[HashMap][]，之前也有整理头插法导致的死循环，这里再整理一下。[参考连接][Link 1]  
**扩容的核心源码如下：**

void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                	//1， 获取旧表的下一个元素
                    Entry<K,V> next = e.next;
                    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;
                }
            }
        }

1, 假设旧表的初始长度为2，此时已经在下标为1的位置存放了两个元素，再put第三个元素的时候考虑需要扩容；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70]  
2, 此刻有两个线程A,B都进行put操作，线程A先扩容，执行到代码Entry<K,V> next = e.next;执行完这段代码，线程A挂起；  
然后线程B开始执行transfer函数中的while循环，会把原来的table变成一个table（线程B自己的栈中），再写入到内存中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 1]  
注意，因为线程A的e指向了key(3), next指向了key(7), 其在线程B rehash后，指向了线程B重组后的链表。我们可以看到链表的顺序被反转了。  
3, 线程A被唤醒，继续执行：

*  先是执行newTable\[i\] = e ;
 *  然后是e = next , **导致了e指向了key(7);**
 *  而下一次循环的next = e.next 导致next指向了key(3)  
    如下图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 2]  
    4， 当前循环：  
    e.next = newTable\[i\];  
    newTable\[i\] = e ;  
    e = next;  
    将key(7)摘下来采用头插法，放到newTable\[i\]的第一个元素中，下一个结点指向key(3)  
    下一次循环：  
    next = e.next; **此时e为key(3)**  
    此时next = null; 不会在往下循环了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 3]  
    5，***此时key(3)采用头插法又放到newTable\[i\]的位置，导致key(3)指向key(7)，注意此时key(7).next已经指向了key(3)，所以环形链表就出现了。如下图：***  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 4]  
    ***于是当我们的线程A调用get()方法时，如果下标映射到3处，则会出现死循环。***

总结：  
线程A先执行，执行完Entry<K,V> next = e.next;这行代码后挂起，然后线程B完整的执行完整个扩容流程，接着线程A唤醒，继续之前的往下执行，**当while循环执行3次后会形成环形链表**。

[HashMap]: https://blog.csdn.net/thqtzq/article/details/90146880
[Link 1]: https://coolshell.cn/articles/9606.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70]: /images/20220128/9b8fcc23a61d411da4ebc756718b41a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 1]: /images/20220128/c5f7b1622f38417dbe10359f2f4077c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 2]: /images/20220128/0f5033c1220f42b499d05d00166745eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 3]: /images/20220128/c8904e414d4a4969819e08cd912178ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RocXR6cQ_size_16_color_FFFFFF_t_70 4]: /images/20220128/b930e3cc9ba34733bfe741df29d0271c.png