Java集合——HashMap扩容的死锁问题

Java集合——HashMap扩容的死锁问题 摘要:本文主要了解了HashMap在多线程并发情况下扩容产生的死锁问题。 死锁问题 在JDK的1.7版本进行扩容时,因为是头插法插入节点,并且在一个线程扩容后...

Java集合——HashMap扩容的死锁问题

摘要:本文主要了解了HashMap在多线程并发情况下扩容产生的死锁问题。

死锁问题

在JDK的1.7版本进行扩容时,因为是头插法插入节点,并且在一个线程扩容后会替换掉之前的数组,所以在多线程环境下可能会产生死锁。
 
 1 // 扩容。
 2 void resize(int newCapacity) {
 3     // 判断是否需要扩容。
 4     Entry[] oldTable = table;
 5     int oldCapacity = oldTable.length;
 6     if (oldCapacity == MAXIMUM_CAPACITY) {
 7         threshold = Integer.MAX_VALUE;
 8         return;
 9     }
10     // 创建扩容后的新数组,并且在扩容后替换老数组。
11     Entry[] newTable = new Entry[newCapacity];
12     transfer(newTable, initHashSeedAsNeeded(newCapacity));
13     table = newTable;
14     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
15 }
16 
17 // 扩容。
18 void transfer(Entry[] newTable, boolean rehash) {
19     int newCapacity = newTable.length;
20     for (Entry<K,V> e : table) {
21         while(null != e) {
22             Entry<K,V> next = e.next;
23             if (rehash) {
24                 e.hash = null == e.key ? 0 : hash(e.key);
25             }
26             int i = indexFor(e.hash, newCapacity);
27             e.next = newTable[i];
28             newTable[i] = e;
29             e = next;
30         }
31     }
32 }
 
以上是扩容相关的代码,可以发现,多线程情况下,每个线程都有自己的新数组,并且在扩容后会替换以前的数组。
 
这就有可能导致A线程和B线程同时对一个数组扩容,A线程扩容后替换掉老数组,这时B线程使用的数组实际上是A线程扩容后的数组,就会产生线程安全问题。

死锁原因

比如,当前集合数组长度为2,已经有两个元素被放在了下标为0的节点里形成了链表结构,此时,有两个线程都同时向集合添加新元素,所以每个线程在添加时都会对原集合数组进行扩容。
 
插入前的数组如图:
 
 
1)线程一先执行,当它执行完上面代码“Entry<K,V> next = e.next;”以后,e指向A,next指向B,时间片用完,线程一挂起。此时,如图:
 
 
2)线程二后执行,并且完成了整个扩容操作,而且扩容后的新数组替换了原数组。此时,如图:
 
 
3)线程一继续执行,e指向A,next指向B。此时,原数组已经被线程二扩充了。
 
在执行了“e.next = newTable[i];”之后,e的下一节点指向了新数组下标为0的节点。此时,如图:
 
 
在执行了“newTable[i] = e;”之后,将e作为新数组下标为0的节点,e指向了A,A的下一节点指向null。此时,如图:
 
 
在执行了“e = next;”之后,e指向了B。此时,如图:
 
 
4)线程一继续执行,开始第二轮循环。
 
在执行了“Entry<K,V> next = e.next;”之后,e指向B,next指向A。此时,如图:
 
 
在执行了“e.next = newTable[i];”之后,e的下一节点指向了新数组下标为0的节点。此时,如图:
 
 
在执行了“newTable[i] = e;”之后,将e作为新数组下标为0的节点,e指向了B,B的下一节点指向null。此时,如图:
 
 
在执行了“e = next;”之后,e指向了A。此时,如图:
 
 
5)线程一继续执行,开始第三轮循环。
 
在执行了“Entry<K,V> next = e.next;”之后,e指向A,next指向null。此时,如图:
 
 
在执行了“e.next = newTable[i];”之后,e的下一节点指向了新数组下标为0的节点。此时,如图:
 
  • 发表于 2020-07-29 21:20
  • 阅读 ( 91 )
  • 分类:网络文章

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除