HashMap为什么是线程不安全的

清疚 2022-02-21 13:12 310阅读 0赞

HashMap的容量是有限的，当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行resize。

影响发生resize的因素有两个：

1.capacity：HashMap数组长度，默认初始为16。HashMap的长度是2的幂。

2.loadFactor：负载因子，默认值为0.75f。

衡量HashMap是否进行resize的条件如下：HashMap.Size >= capacity \* loadFactor。

HashMap的resize不是简单的把长度扩大，而是经过下面两个步骤：

1.扩容

创建一个新的Entry空数组，长度是原数组的2倍。

2.ReHash

遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。让我们回顾一下Hash公式：index = HashCode（Key） & （Length - 1）

ReHash的Java代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
    
        createEntry(hash, key, value, bucketIndex);
    }
    
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
    
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                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;
            }
        }
    }

假设一个HashMap已经到了resize的临界点。此时有两个线程A和B，在同一时刻对HashMap进行put操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 1][]

此时达到resize条件，两个线程各自进行rezie的第一步，也就是扩容：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 2][]

这时候，两个线程都走到了ReHash的步骤。让我们回顾一下ReHash的代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 3][]

假如此时线程B遍历到Entry3对象，刚执行完红框里的这行代码，线程就被挂起。对于线程B来说：

**e = Entry3  
next = Entry2**

这时候线程A畅通无阻地进行着Rehash，当ReHash完成后，结果如下（图中的e和next，代表线程B的两个引用）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 4][]

直到这一步，看起来没什么毛病。接下来线程B恢复，继续执行属于它自己的ReHash。线程B刚才的状态是：

**e = Entry3  
next = Entry2**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 5][]

当执行到上面这一行时，显然 i = 3，因为刚才线程A对于Entry3的hash结果也是3。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 6][]

我们继续执行到这三行，Entry3放入了线程B的数组下标为3的位置，Entry3.next = null，并且e指向了Entry2。此时e和next的指向如下：

**e = Entry2  
next = Entry2**

整体情况如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 7][]

接着是新一轮循环，又执行到红框内的代码行：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 3][]

**e = Entry2  
next = Entry3**

整体情况如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 8][]

接下来执行下面的三行，用头插法把Entry2插入到了线程B的数组的头结点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 6][]

整体情况如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 9][]

第三次循环开始，又执行到红框的代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 3][]

**e = Entry3  
next = Entry3.next = null**

最后一步，当我们执行下面这一行的时候，见证奇迹的时刻来临了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 10][]

**next = null  
Entry2.next = Entry3  
Entry3.next = Entry2  
newTable\[i\] = Entry3  
e = null**

链表出现了环形！

整体情况如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 11][]

此时，问题还没有直接产生。当调用get查找一个不存在的key，而这个key的Hash结果恰好等于3的时候，由于位置3带有环形链表，所以程序将会进入死循环！

参考：

[https://blog.csdn.net/wufaliang003/article/details/80219296][https_blog.csdn.net_wufaliang003_article_details_80219296]

[https://blog.csdn.net/loveliness\_peri/article/details/81092360][https_blog.csdn.net_loveliness_peri_article_details_81092360]

[http://www.importnew.com/22011.html][http_www.importnew.com_22011.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70]: /images/20220221/cf781fa8f40c4fc0a7f27f474f445abf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 1]: /images/20220221/667780b1a98f4a12b62a01b7349f7c40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 2]: /images/20220221/608ce5f067f64e9d94066616fb8271e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 3]: /images/20220221/372da2ff8fd745aaaefd67ae46f23ca6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 4]: /images/20220221/45168302c271458fa1348ab6c8b8d6a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 5]: /images/20220221/15054819cd4d40f8b7c8ece8217e79f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 6]: /images/20220221/e639c879a0e447398315a1f673019a4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 7]: /images/20220221/6cae29fd60ab4a23861d7ccc199ebf27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 8]: /images/20220221/203fe3b9330c429982d6dacee3d63b9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 9]: /images/20220221/6fc2b4772090458a868f381f1ea1f50e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 10]: /images/20220221/574712008a0e438885715dbeb05097d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Rpd2Vpa2FuZw_size_16_color_FFFFFF_t_70 11]: /images/20220221/48924d460b804e678d248fd2ff73dbf1.png
[https_blog.csdn.net_wufaliang003_article_details_80219296]: https://blog.csdn.net/wufaliang003/article/details/80219296
[https_blog.csdn.net_loveliness_peri_article_details_81092360]: https://blog.csdn.net/loveliness_peri/article/details/81092360
[http_www.importnew.com_22011.html]: http://www.importnew.com/22011.html