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

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

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

1.HahsMap 数据结构

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

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：

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

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

3.并发条件下的死循环

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

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

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

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

当 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 关键字来保证线程安全，这样可以避免多个线程同时对同一个桶进行操作，从而避免链表形成环形结构。