灵魂一问：说说触发HashMap死循环根因

深藏阁楼爱情的钟 2024-03-25 16:58 31阅读 0赞

大家好，`JDK1.7 HashMap`在并发执行`put`操作时会引起死循环，导致CPU利用率接近100%，这个是八股文内容之一，想必各位小伙伴也知道；在问到此问题的时候，可能有些面试官也会让我们讲讲这个死循环发生的过程，工匠之前在面试某杭州电商的时候，也被问到过；如果回答不好，可能会被扣分。今天我就带大家一起梳理一下，这个问题是如何产生的。

本篇文章，工匠会先从`JDK1.7 HashMap底层数据结构`，`put()流程`，然后通过图解演示的方式给大家讲解死循环的发生过程。

### 1.HahsMap数据结构 ###

![format_png][]

`HashMap`内部维护了一个数组`table`，每个元素是一个链表的头结点。链表中存储了具有相同`hash值`的键值对。在JDK1.7中，`HashMap`中的键值对使用`Entry`类表示。`Entry`类包含四个属性： `key`, `value`, `hash` 值和用于单向链表的`next`。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        // 省略属性的访问get/set方法
    }
    
    复制代码

### 2.PUT流程及扩容机制 ###

总体来说，`put`方法的实现比较复杂，涉及到`哈希值`的计算、扩容、索引的计算、链表的遍历和修改等多个操作；为了便于理解，工匠先将整个逻辑用流程图的方式给大家呈现出来，然后逐行分析源码，源码分析的地方可能比较长，大家可通过先记流程图，然后看源码解析部分：

![format_png 1][]

#### 2.1 put ####

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            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++;
        addEntry(hash, key, value, i);
        return null;
    }
    复制代码

我们逐行解析这个方法：

1.  如果当前 `table` 为空，则调用 `inflateTable` 方法创建 `table` 数组；
2.  如果 `key` 为 `null`，则调用 `putForNullKey` 方法添加该键值对，该方法单独处理；
3.  通过调用`hash()`方法计算 `key` 的哈希值 `hash`，以及该键值对在 `table` 数组中的位置 `i`，索引 `i` 的定位通过调用方法`indexFor`；
4.  遍历 `table[i]` 链表，如果找到已存在的键值对，则将其 value 值替换为新值，并返回旧值；
5.  如果没有找到已存在的键值对，则将新的键值对添加到链表的头部，并返回 null

下面我们再依次讲解`inflateTable`、`putForNullKey`、`hash`、`indexFor`、`addEntry`等方法的源码：

2.1.1 inflateTable

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
    
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
    
    复制代码

这个方法会将 `table` 数组扩容到指定大小。首先调用 `roundUpToPowerOf2` 方法将 `toSize` 扩容到最接近的 2 的幂次方。然后计算新的阈值 `threshold`，并根据新的 `capacity` 创建一个新的 `table` 数组。最后，如果需要的话，会调用 `initHashSeedAsNeeded` 方法来初始化哈希种子

2.1.2 putForNullKey

private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
    复制代码

这个方法用于添加键为 `null` 的键值对。它会遍历 `table[0]` 链表，查找是否已经存在键为 `null` 的键值对。如果找到了，就将其 value 值替换为新值，并返回旧值。如果没有找到，就将新的键值对添加到链表头部，并返回 null。

最后，如果没有找到已存在的键值对，就会在 `modCount` 中增加 1，表示对 HashMap 进行了修改操作。这是 HashMap 用于实现 `fail-fast` 机制的一部分

2.1.3 hash

static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    复制代码

这个方法用于计算键的哈希值。如果键为 `null`，则哈希值为 0；否则，将计算出的哈希值右移 16 位，并将其与原始哈希值进行异或运算，以减少哈希碰撞的概率。

2.1.4 indexFor

static int indexFor(int h, int length) {
        return h & (length-1);
    }
    复制代码

`indexFor`这个方法用于计算键值对在`table` 数组中的索引位置。因为 `table` 的长度必须是 2 的幂次方，所以可以用位运算来代替取模运算，提高性能。看到这个方法，小伙伴应该知道，`hashMap`为要设置长度为2的幂次方了吧

2.1.5 addEntry

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 createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        size++;
    }
    复制代码

`addEntry` 方法用于在 `table` 中添加新的键值对。如果 `size` 大于等于 `threshold`，则表示 `table` 数组已经达到了负载因子，需要对 `table` 进行扩容，这里是调用 `resize` 方法进行扩容。然后再计算一次 `hash` 值和 `bucketIndex` 的值。接下来是调用 `createEntry` 方法创建一个新的键值对，并将其添加到 `table[bucketIndex]` 的头部，最后将 `size` 加 1

梳理了新的键值对添加过程，我们再看看`resize`方法扩容逻辑

2.1.5.1 resize -扩容

`resize` 方法的实现如下：

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);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    void transfer(Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while (null != e) {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
    复制代码

`resize`方法首先将旧的 `table` 数组和阈值 `threshold` 存储起来，以便在扩容后使用。如果旧的 `table` 数组已经达到了最大容量 `MAXIMUM_CAPACITY`，就将阈值设置为 `Integer.MAX_VALUE`，表示不能再进行扩容。然后创建一个新的 `Entry` 数组 `newTable`，并调用 `transfer` 方法将旧的 `Entry` 对象复制到新的数组中。最后将 `table` 数组引用指向新的 `Entry` 数组，并重新计算阈值 `threshold`。

`transfer`该方法的作用是将HashMap对象的所有元素转移到新的哈希表数组中；具体的逻辑：

*  对于每个非空桶：会将旧表中当前桶的引用设置为null，会通过一个循环处理当前桶中的所有元素。在循环内部，它使用`indexFor`方法计算每个元素在新表中应该插入的位置。
 *  然后，它将当前元素的`next`指针保存到一个临时变量`next`中，以便在循环的下一次迭代中访问它。接下来，它将当前元素的`next`指针设置为新表中对应桶的头部。最后，它将新表中对应桶的头部设置为当前元素，将当前元素插入到新表中

因为`transfer`逻辑是理解死循环的重要流程，下面我再通过图解方式描述一下该方法逻辑：假设数据有三条，key分别是20,28,36：

![format_png 2][]

原链表的顺序为：20 -> 28 -> 36； 在经过`transfer`将数据转移到新的`table`之和，链表顺序为： 36 -> 28 -> 20

![format_png 3][]

总结下来：在转移链表数据的过程中，采用的是头插法。既待插入的`entry`都放到数组tab\[i\]的位置，然后将待插入的`entry`的`next`指针指向之前放入到tab\[i\]位置的 `entry`。

### 3.并发条件下的死循环 ###

乍一看，上面`transfer`方法转移链表数据的过程，没啥毛病啊，采用头插法，代码理解起来也贼容易，而且代码量也不多；当然，单线程环境下的确没啥毛病，那么我们来看看在并发环境下的过程：

假设初始状态下：HashMap有两个元素A,B，如下：

![format_png 4][]

假设有`Thread1`和`Thread2`两个线程向`HashMap`中添加数据，`Thread1`首先获取执行权，向`HashMap`插入数据的时候开始扩容，当创建一个新的数组，还没来得及转移旧的数据的时候，`Thread2`此时获得执行权；那么，对于`Thread1`而言，此时的`HashMap`结构如下，链表结构：A -> B

![format_png 5][]

假如`thread2`开始执行之后，添加数据的时候又开始扩容，并完成了扩容操作，则此时的`HashMap`结构如下，链表结果 B->A

![format_png 6][]

当`Thread2` 执行结束之后，放弃CPU执行权，`Thread1`继续之前未完成的扩容操作，在上面我们说过，对于`Thread1`而言，其链表结构是：A->B。此处，我们再拿`transfer`方法代码分析：

void transfer(Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while (null != e) {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
    复制代码

我们假设`Thread1`是执行到代码`newTable[i] = e`挂起的，从哪里挂起，就从哪里执行；那么当`Thread1`再次获取到执行权的时候，此时`e`就是`A`；执行下一步`e=next`，此时`next`为`B`，继续执行循环内容，但是此时因为`Thread2`的扩容，`B.next`已经指向了`A`，最终遍历`e`不为null，然后循环继续。此处就一直无限循环下去。

### 4.总结 ###

在`JDK1.7`中，`HashMap`扩容死循环的根本原因是由于在并发情况下，多个线程同时对同一个桶进行操作时，可能会导致链表形成`环形结构`。解决这个问题的方法有以下2种：

1.  使用线程安全的`HashMap`实现，例如`ConcurrentHashMap`，这些实现使用了锁或其他同步机制来保证线程安全。
2.  在put操作时使用`synchronized`关键字来保证线程安全，这样可以避免多个线程同时对同一个桶进行操作，从而避免链表形成环形结构。

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dd178631b58b4afca250b80574d97903.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c533767238234add8666c20bc0e8cd75.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7292736e866b4c6086ee10155881d20f.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7102be585c1f4576b6f549fec3d873b7.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c03b583a21d648c1a65162df9fd1eb71.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8dc93d172d074c1ab77177c8a1dbe2a6.png
[format_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/be3b34077eaa4dd795efcee798f3103d.png