今天在看《分布式java应用》这本书的时候看到作者提到HashMap在多线程并发的环境下有可能出现死循环,导致cpu100%的现象,看了下源码结合网上的分析说明下这种可能性。可能出现问题的地方是在扩容的时候
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)(newCapacity * loadFactor);
}
这个方法本身没有问题,问题出在transfer(newTable);这个方法是用来移动oldTable里的数据到newTable里。
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
//(1)
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
//(2)
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
//(3)
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
下面分析可能出现的情况,假设原来oldTable里存放a1,a2的hash值是一样的,那么entry链表顺序是:
P1:oldTable[i]->a1->a2->null
P2:oldTable[i]->a1->a2->null
线程P1运行到(1)下面这行时,e=a1(a1.next=a2),继续运行到(2)下面时,next=a2。这个时候切换到线程P2,线程P2执行完这个链表的循环。如果恰a1,a2在新的table中的hash值又是一样的,那么此时的链表顺序是:
主存:newTable[i]->a2->a1->null
注意这个时候,a1,a2连接顺序已经反了。现在cpu重新切回P1,在(3)这行以后:e.next = newTable[i];即:a1.next=newTable[i];
newTable[i]=a1;
e=a2;
开始第二次while循环(e=a2,next=a1):
a2.next=newTable[i];//也就是
a2.next=a1
newTable[i]=a2
e=a1
开始第三次while循环(e=a1,next=null)
a1.next=newTable[i];//也就是
a1.next=a2
这个时候a1.next=a2,a2.next=a1,形成回环了,这样就造成了死循环,在get操作的时候next永远不为null,造成死循环。
可以看到很偶然的情况下会出现死循环,不过一旦出现后果是非常严重的,多线程的环境还是应该用ConcurrentHashMap。
转载地址:
http://blog.csdn.net/ykdsg/article/details/6303694
分享到:
相关推荐
HashMap死循环原因分析.docx
详 解 hashmap 1.7 扩 容 机 制 的 数 据 迁 移 以 及 出 现 环 形 列 表 导 致 死 锁 情 况 视 频
疫苗:Java HashMap的死循环
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
HashMap导致CPU100% 的分析
hashMap存储分析hashMap存储分析
HASHMAP基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)下面小编来带大家详细了解下吧
深入浅出HashMap,源码分析, HashMap存取实现,数据结构
HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析HashMap 1.7源码分析
详细分析HashMap的存储原理,key值的hash地址以及扩容
java1.8 HashMap用的是数组+链表+红黑树实现的,采用尾插法实现的,解决了死循环的问题,今天分析的就是1.8 // 初始容量为16 static final int DEFAULT_INITIAL_CAPACITY = 1 <>> 16); } /** * Implements ...
hashMap基本工作原理,图解分析,基础Map集合
hashmap的底层及源码解析,很适合大家的学习,不要积分。
比如,当前集合数组长度为2,已经有两个元素被放在了下标为0的节点里形成了链表结构,此时,有两个线程都同时向集合添加新元素,所以每个线程在添加时都会对原集合数组进行扩容。 插入前的数组 : 1)线程一先执行...
TBB 开源库及并发 Hashmap 的使用
计算机后端-Java-Java核心基础-第25章 集合02 12. HashMap在JDK8中的源码分析.avi
计算机后端-Java-Java核心基础-第25章 集合02 11. HashMap在JDK7中的源码分析.avi
hashmap实例 hashmap实例hashmap实例hashmap实例