HashMap为什么会发生死循环？

蔚落 2023-09-23 16:28 92阅读 0赞

Java的HashMap是线程不安全的，所以在jdk1.7中，多线程的HashMap扩容采用头插法会发生死循环问题。为什么会发生这种情况呢？

## 正常扩容 ##

当我们向HashMap中添加值的时候，调用的是`Put()`方法。

public V put(K key, V value) {
            //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
            //此时threshold为initialCapacity 默认是1<<4(24=16)
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
           //如果key为null，存储位置为table[0]或table[0]的冲突链上
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
            int i = indexFor(hash, table.length);//获取在table中的实际位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
            addEntry(hash, key, value, i);//新增一个entry
            return null;
        }
    复制代码

put方法主要进行添加操作的是`addEntry()`方法。

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    复制代码

addEntry方法中会对当前HashMap的容量进行判断。当个数大于等于阈值且当前要添加的数组下标位置已经存在元素了(准备添加时发生哈希冲突)的时候,就会调用扩容方法`resize(2 * table.length)`HashMap的容量扩大两倍

void resize(int newCapacity) {
        //旧Entry数组
        Entry[] oldTable = table;
        //旧Entry数组长度
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //新Entry数组，长度为旧的两倍（2 * table.length）
        Entry[] newTable = new Entry[newCapacity];
        //将旧Entry数组中的值重新计算，添加到新Entry数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //指向新Entry数组
        table = newTable;
        //得到新的阈值（2*table.length*0.75=2*16*0.75=24）
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    复制代码

resize创建了新的Entry数组，并通过`transfer()`方法中原来的数组添加到新的Entry数组中。

这里就是发生死循环的地方了。首先我们假设出正常情况下的该方法图示。

*  我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
 *  最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table\[1\]这里了。
 *  接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程

![format_png][]

扩容之后rehash过程。

![format_png 1][]

这就是单线程正常情况下的状况。

## 并发扩容 ##

\*\*假设我们有两个线程。\*\*我用红色和浅蓝色标注了一下。

我们再回头看一下我们的 transfer代码中的这个细节：

![format_png 2][]

由于线程二的头插法，最开始的e和next所指的元素已经换掉了位置。接着线程一继续按照头插法操作。就会出现如下

e.next = newTable[i];
       newTable[i] = e;
       e = next;
    复制代码

![format_png 3][]

此时就出现了循环。问题终于找到了！！！

## 总结 ##

1.  HashMap是线程不安全的。
2.  HashMap正常扩容是不会出现问题的。
3.  死循环问题是出现在并发下扩容采用头插法从而导致出现死循环。

这里引出了个问题虽然现如今我们工作中使用的都是JDK8，由于JDK8下的HashMap采用的是尾插法所以是不会出现死循环问题，但是它还是不安全的。那么有没有一种线程安全的Map呢？？？

答案是有的，那就是JUC下的`ConcurrentHashMap`。挖坑ing...

[format_png]: https://img-blog.csdnimg.cn/img_convert/0a9c37fc7a04965e72d488d8749ecf50.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/4e6f9f0c36591dc1daec3a5b13fc756d.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/75cc0cd20773fc4d6d92b5a0c4445f6d.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/cc8ed4a2041b936138b66a3674f2116d.webp?x-oss-process=image/format,png