写点什么

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

  • 2023-04-15
    湖南
  • 本文字数:4305 字

    阅读完需:约 14 分钟

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

用户头像

喜欢就点个关注吧~ 2023-04-10 加入

持续更新Java

评论

发布
暂无评论
阿里巴巴灵魂一问:说说触发HashMap死循环根因_hashmap_会踢球的程序源_InfoQ写作社区