乐趣区

关于java:11张图让你彻底明白jdk17-hashmap的死循环是如何产生的

jdk1.7 hashmap 的循环依赖问题是面试常常被问到的问题,如何答复不好,可能会被扣分。明天我就带大家一下梳理一下,这个问题是如何产生的,以及如何解决这个问题。

一、hashmap 的数据结构

先一起看看 jdk1.7 hashmap 的数据结构

数组 + 链表

hashmap 会给每个元素的 key 生成一个 hash 值,而后依据这个 hash 值计算一个在数组中的地位 i。i 不同的元素放在数组的不同地位,i 雷同的元素放在链表上,最新的数据放在链表的头部。

往 hashmap 中保留元素会调用 put 办法,获取元素会调用 get 办法。接下来,咱们重点看看 put 办法。

二、put 办法

重点看看 put 办法

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);
     }
     if (key == null)
         return putForNullKey(value);
     // 依据 key 获取 hash 
     int hash = hash(key);
     // 计算在数组中的下表
     int i = indexFor(hash, table.length);
     // 变量汇合查问雷同 key 的数据,如果曾经存在则更新数据
     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++;
     // 如果不存在雷同 key 的元素,则增加新元素
     addEntry(hash, key, value, i);
     return null;
}

再看看 addEntry 办法

void addEntry(int hash, K key, V value, int bucketIndex) {
     // 当数组的 size >= 扩容阈值,触发扩容,size 大小会在 createEnty 和 removeEntry 的时候扭转
     if ((size >= threshold) && (null != table[bucketIndex])) {
         // 扩容到 2 倍大小,后边会跟进这个办法
         resize(2 * table.length);
         // 扩容后从新计算 hash 和 index
         hash = (null != key) ? hash(key) : 0;
         bucketIndex = indexFor(hash, table.length);
     }
     // 创立一个新的链表节点,点进去能够理解到是将新节点增加到了链表的头部
     createEntry(hash, key, value, bucketIndex);
 }

看看 resize 是如何扩容的

 void resize(int newCapacity) {Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     if (oldCapacity == MAXIMUM_CAPACITY) {
     threshold = Integer.MAX_VALUE;
     return;
     }
     // 创立 2 倍大小的新数组
     Entry[] newTable = new Entry[newCapacity];
     // 将旧数组的链表转移到新数组,就是这个办法导致的 hashMap 不平安,等下咱们进去看一眼
     transfer(newTable, initHashSeedAsNeeded(newCapacity));
     table = newTable;
     // 从新计算扩容阈值 (容量 * 加载因子)
     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

出问题的就是这个 transfer 办法

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];
             // 这行才是真正把数据插入新数组中,后面那行代码只是设置以后节点的 next
             // 这两行代码决定了倒序插入
             // 比方:以前同一个地位上是:3,7,前面可能变成了:7、3
             newTable[i] = e;
             // 将下一个元素赋值给以后元素,以便遍历下一个元素
             e = next;  
         }  
     }
}

我来给大家剖析一下,为什么这几个代码是头插法,网上很多技术文章都没有说分明。

三、头插法

咱们把眼光聚焦到这几行代码:

 // 获取下一个元素,记录到一个长期变量,以便前面应用
 Entry<K,V> next = e.next;
 // 计算节点在新数组中的下标
 int i = indexFor(e.hash, newCapacity);
 // 将旧节点插入到新节点的头部
 e.next = newTable[i];
 // 这行才是真正把数据插入新数组中,后面那行代码只是设置以后节点的 next
 newTable[i] = e;
 // 将下一个元素赋值给以后元素,以便遍历下一个元素
 e = next;

假如刚开始 hashMap 有这些数据

调用 put 办法须要进行一次扩容,刚开始会创立一个空的数组,大小是以前的 2 倍,如图所示:

开始第一轮循环:

 //next= 7   e = 3  e.next = 7
 Entry<K,V> next = e.next;
 // i=3
 int i = indexFor(e.hash, newCapacity);
 //e.next = null,刚初始化时新数组的元素为 null
 e.next = newTable[i];
 // 给新数组 i 地位 赋值 3
 newTable[i] = e;
 // e = 7
 e = next;

执行完之后,第一轮循环之后数据变成这样的

再接着开始第二轮循环:

 //next= 5   e = 7  e.next = 5
 Entry<K,V> next = e.next;
 // i=3
 int i = indexFor(e.hash, newCapacity);
 //e.next = 3,此时雷同地位上曾经有 key= 3 的值了,将该值赋值给以后元素的 next
 e.next = newTable[i];
 // 给新数组 i 地位 赋值 7
 newTable[i] = e;
 // e = 5
 e = next;

下面会形成一个新链表,连贯的程序正好反过来了。

因为第二次循环时,节点 key= 7 的元素插到雷同地位上已有元素 key= 3 的后面,所以说是采纳的头插法。

四、死循环的产生

接下来重点看看死循环是如何产生的?

假如数据跟元素数据统一,有两个线程:线程 1 和 线程 2,同时执行 put 办法,最初同时调用 transfer 办法。

线程 1 先执行,到  Entry<K,V> next = e.next; 这一行,被挂起了。

 //next= 7   e = 3  e.next = 7
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;

此时线程 1 创立的数组会创立一个空数组

接下来,线程 2 开始执行,因为线程 2 运气比拟好,没有被中断过,执行结束了。

过一会儿,线程 1 被复原了,从新执行代码。

 //next= 7   e = 3  e.next = 7
 Entry<K,V> next = e.next;
 // i = 3
 int i = indexFor(e.hash, newCapacity);
 // e.next = null,刚初始化时新数组的元素为 null
 e.next = newTable[i];
 // 给新数组 i 地位 赋值 3
 newTable[i] = e;
 // e = 7
 e = next;

这时候线程 1 的数组会变成这样的

再执行第二轮循环,此时的 e =7

 //next= 3   e = 7  e.next = 3
 Entry<K,V> next = e.next;
 // i = 3
 int i = indexFor(e.hash, newCapacity);
 // e.next = 3,此时雷同地位上曾经有 key= 3 的值了,将该值赋值给以后元素的 next
 e.next = newTable[i];
 // 给新数组 i 地位 赋值 7
 newTable[i] = e;
 // e = 3
 e = next;

这里特地要阐明的是 此时 e =7,而 e.next 为什么是 3 呢?

因为 hashMap 的数据是公共的,还记得线程 2 中的生成的数据吗?

此时 e =7,那么 e.next 必定是 3。

通过下面第二轮循环之后,线程 1 失去的数据如下:

此时因为循环判断还没有退出,判断条件是:while(null != e),所以要开始第三轮循环:

 //next= null   e = 3  e.next = null
 Entry<K,V> next = e.next;
 // i = 3
 int i = indexFor(e.hash, newCapacity);
 // e.next = 7,要害的一步,因为第二次循环是 key:7 .next = key:3,当初 key:3.next = key:7
 e.next = newTable[i];
 // 给新数组 i 地位 赋值 3
 newTable[i] = e;
 // e = null
 e = next;

因为 e =null,此时会退出循环,最终线程 1 的数据会是这种构造:

key:3 和 key:7 又复原了刚开始的程序,然而他们的 next 会互相援用,形成环形援用。

留神,此时调用 hashmap 的 get 办法获取数据时,如果只是获取循环链上 key:3 和 key:7 的数据,是不会有问题的,因为能够找到。就怕获取循环链上没有的数据,比方:key:11,key:15 等,会进入有限循环中导致 CPU 使用率飙升。

五、如何防止死循环

为了解决这个问题,jdk1.8 把扩容是复制元素到新数组由 头插法 改成了 尾插法。此外,引入了红黑树,晋升遍历节点的效率。在这里我就不过多介绍了,如果有趣味的敌人,能够关注我的公众号,前面会给大家详细分析 jdk1.8 的实现,以及 jdk1.7、jdk1.8 hashmap 的区别。

此外,HashMap 是非线程平安的,要防止在多线程的环境中应用 HashMap,而应该改成应用 ConcurrentHashMap。

所以总结一下要防止产生死循环的问题的办法:改成 ConcurrentHashMap

退出移动版