jdk 1.7 HashMap 多线程导致的死循环问题

缺乏、安全感 2022-11-05 05:26 131阅读 0赞

一、先来看1.7 HashMap，里面的扩容代码

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                //代码1：获取e指向的Entry
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //代码2：获取下标
                int i = indexFor(e.hash, newCapacity);
                //代码3：e指向扩容后的下标对应的newTable
                e.next = newTable[i];
                //代码4：将e放入数组中，头插
                newTable[i] = e;
                //代码5：将next赋给e
                e = next;
            }
        }
    }

二、在**单线程**执行1.7 HashMap扩容时，我们假设下面是**线程T1**执行的扩容

1、进入while循环，执行到代码1：Entry<K,V> next = e.next；

假设代码2计算出i下标为2：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70][]

2、执行到代码3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1][]

3、执行到代码4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 2][]

4、执行到代码5，至此。while循环第一次完成；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 3][]

5、在旧的table，原数组节点上是a，这个链表执行完内while循环迁移以后：

总结，HashMap 1.7采用的是头部插入法，扩容后，在哈希冲突链表上，会将元素存储倒置；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 4][]

三、那么在有多个线程执行，都执行到扩容时：

1、假设线程T2也来执行到扩容方法，但是在T2线程执行到while第一次循环，代码3：e.next = newTable\[i\]，这之前发生了cpu调度，T2线程挂起；

T1线程执行完扩容以后，再回来执行T2的时候，那么就是现在下图中这样一个执行状态，e还是指向最开始的元素a，next指向元素b；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 5][]

2、好了，T2线程回来了，他计算出来的下标i可能是3，newTable\[3\] ，从上次挂起的地方，开始继续执行代码3：e.next = newTable\[i\]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 6][]

3、执行代码4：newTable\[i\] = e

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 7][]

4、执行代码5：e = next

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 8][]

5、开始第二次while循环，代码1：Entry<K,V> next = e.next

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 9][]

6、继续执行代码3、4、5：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 10][]

7、while中第三次，最后造成了循环链表，发生死循环；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 11][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70]: /images/20221023/59be9fc59e7b4bf991f8c80bc775b9dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/544cf5038cb54df8ae32978ab482128b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/0ec8fe75837643218da6add4283647ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/6b0ed9460d6a4fbb8e33048fd2d4f621.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/6d5e3327925944ada3fad545d5c375c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 5]: /images/20221023/f8b0f099d61e4b048f39e0aa67cd5771.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 6]: /images/20221023/c69e1a7f7e8148a19c052a5db0c37f1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 7]: /images/20221023/516034280f3f404f9fce2037fadc061a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 8]: /images/20221023/395ae0f1216c4ef4a06326f003a0dc51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 9]: /images/20221023/c0e4b10941f942238c960e3b8f296c61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 10]: /images/20221023/0641bff0109d45088eb961d6306f9f43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 11]: /images/20221023/1e85655b40254fb68c2d05a6af4fa8c4.png