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

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

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的节点。此时，如图：     在执行了“newTable[i] = e;”之后，将e作为新数组下标为0的节点，e指向了A，A的下一节点指向null。此时，如图：     在执行了“e = next;”之后，e指向了null。此时，如图：     6）线程一将新数组赋值给原数组，如图：    

 

如果再有线程尝试在下标为1的数组进行插入操作，就会引发死循环。  

2.11 扩容的死锁问题

 

在JDK的1.7版本进行扩容时，因为是头插法插入节点，并且在一个线程扩容后会替换掉之前的数组，所以在多线程环境下可能会产生死锁。

 

// 扩容。 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, initHashSeedAsNeeded(newCapacity));     table = newTable;     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }   // 扩容。 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];            newTable[i] = e;            e = next;        }     } }

 

以上是扩容相关的代码，可以发现，多线程情况下，每个线程都有自己的新数组，并且在扩容后会替换以前的数组。

 

这就有可能导致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的节点。此时，如图：

 

 

在执行了“newTable[i] = e;”之后，将e作为新数组下标为0的节点，e指向了A，A的下一节点指向null。此时，如图：

 

 

在执行了“e = next;”之后，e指向了null。此时，如图：

 

 

6）线程一将新数组赋值给原数组，如图：

 

 

如果再有线程尝试在下标为1的数组进行插入操作，就会引发死循环。