JAVA基础（四）HashMap线程不安全问题分析

妖狐艹你老母 2022-02-19 05:41 257阅读 0赞

### HashMap线程不安全 ###

*   *  resize()死循环
     *   *  过程分析
         *  原因分析

## resize()死循环 ##

> 在JDK1.8之前，HashMap在动态扩容时复制旧table中的链表结点到新扩容后的newTab中使用的是头插法，每个节点都是插入在链表的头部，这也是导致多线程环境下出现环形链表死循环的根本原因。

### 过程分析 ###

清晰思路只简化出核心代码：

while(null != e) { 
    	//①断开链表前读取下一个节点，否则将会丢失链表
        Entry<K,V> next = e.next;
        //头插法，
        e.next = newTable[i];
        //复制节点到新数组
        newTable[i] = e;
        e = next;
    }

假设目前HashMap的table的长度为2，扩容阈值为1。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]

1.  线程T1向HashMap中插入k3，当执行到代码①处时cpu执行时间耗尽，暂时被挂起。  
    此时：  
    原table中已经插入k3，并触发扩容，创建了新数组newTab，但是还没开始复制操作。核心代码中的e指针指向k3，next则指向k4  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 1]
2.  此时线程T2开始运行，T2向HashMap中插入k2，并完成了整个扩容操作。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 2]
3.  T1获得CPU时间继续运行，此时e–>k3，next–>k4。按照代码顺序运行，可以得出循环中每次复制的节点队列：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 3]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 4]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 6]  
    此时k3–>k4，k4–>k3，形成了环形链表，在读取时会出现死循环。

### 原因分析 ###

线程T2扩容复制进新的数组时使用的是头插法，所以导致了链表插入的倒序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]: /images/20220219/df34f923d0ac4a9484c619ae1a9032b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 1]: /images/20220219/5742be5ccfe34e7f8371ce20bed29ec8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 2]: /images/20220219/d3bdd4bf236e436390a6990a25ba8d64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2019041516083719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190415161406285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 5]: /images/20220219/085b320fda624f329efc5a1a47466b38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 6]: /images/20220219/a46379c8ca8c4259b72dc6715292d6f4.png