hashmap引起死循环

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

今天开发环境压测的时候出现cpu用满了情况，看线程堆栈，一堆线程都停留在org.apache.commons.collections4.map.AbstractHashedMap.put(AbstractHashedMap.java:285)，查看google源代码

public Object put(Object key, Object value) {
key = convertKey(key);
int hashCode = hash(key);
int index = hashIndex(hashCode, data.length);
HashEntry entry = data[index];
while (entry != null) {
if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
Object oldValue = entry.getValue();
updateEntry(entry, value);
return oldValue;
}
entry = entry.next;
}

addMapping(index, hashCode, key, value);
return null;
}

方法是非线程安全的，而addMapping方法会触发ensureCapacity扩容，而并发扩容就会容易导致死循环, 具体原因参考文章https://www.cnblogs.com/dongguacai/p/5599100.html

解决方法：

1、使用ConcurrentHashMap。

2、使用Collections.synchronizedMap(Mao<K,V> m)方法把HashMap变成一个线程安全的Map。

我copy了部分文章内容

正常的扩容过程

我们先来看下单线程情况下，正常的rehash过程

1、假设我们的hash算法是简单的key mod一下表的大小（即数组的长度）。

2、最上面是old hash表，其中HASH表的size=2，所以key=3,5,7在mod 2 以后都冲突在table[1]这个位置上了。

3、接下来HASH表扩容，resize=4，然后所有的<key,value>重新进行散列分布，过程如下：

在单线程情况下，一切看起来都很美妙，扩容过程也相当顺利。接下来看下并发情况下的扩容。

并发情况下的扩容

1、首先假设我们有两个线程，分别用红色和蓝色标注了。

2、扩容部分的源代码：

 1 void transfer(Entry[] newTable) {

 2         Entry[] src = table;

 3         int newCapacity = newTable.length;

 4         for (int j = 0; j < src.length; j++) {

 5             Entry<K,V> e = src[j];

 6             if (e != null) {

 7                 src[j] = null;

 8                 do {

 9                     Entry<K,V> next = e.next;

10                     int i = indexFor(e.hash, newCapacity);

11                     e.next = newTable[i];

12                     newTable[i] = e;

13                     e = next;

14                 } while (e != null);

15             }

16         }

17     }