锁定老帖子 主题:HashMap 死循环的探究
精华帖 (5) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (1)
|
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
作者 | 正文 | |||||||||||||||
发表时间:2011-03-14
最后修改:2011-03-16
本文受http://pt.alibaba-inc.com/wp/dev_related_969/hashmap-result-in-improper-use-cpu-100-of-the-problem-investigated.html 的启发,引用了其中的思想,对此表示感谢。 来到杭州实习有一段日子了,很长时间都没有更新博客了,前几天,闲来无事,随便翻了一本书,毕玄的《分布式JAVA应用》,在看到HashMap那一节的时候,其中提到了HashMap是非线程安全的,在并发场景中如果不保持足够的同步,就有可能在执行HashMap.get时进入死循环,将CPU的消耗到100%。HashMap是线程不安全的,这个我知道的,但是在get操作会出现死循环,我还是第一次听说到。于是我google了一下,网上讨论的很多,原来很多人对这个都感兴趣啊,于是我深入到HashMap的源码去探究了一下。 大家都知道,HashMap采用链表解决Hash冲突,具体的HashMap的分析可以参考一下http://zhangshixi.iteye.com/blog/672697 的分析。因为是链表结构,那么就很容易形成闭合的链路,这样在循环的时候就会产生死循环。但是,我好奇的是,这种闭合的链路是如何形成的呢。在单线程情况下,只有一个线程对HashMap的数据结构进行操作,是不可能产生闭合的回路的。那就只有在多线程并发的情况下才会出现这种情况,那就是在put操作的时候,如果size>initialCapacity*loadFactor,那么这时候HashMap就会进行rehash操作,随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作,产生了闭合的回路。下面我们从源码中一步一步地分析这种回路是如何产生的。先看一下put操作: public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //存在key,则替换掉旧的value 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++; //table[i]为空,这时直接生成一个新的entry放在table[i]上 addEntry(hash, key, value, i); return null; } addEntry操作: void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } 可以看到,如果现在size已经超过了threshold,那么就要进行resize操作: 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]; //将旧的Entry数组的数据转移到新的Entry数组上 transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } 看一下transfer操作,闭合的回路就是在这里产生的: void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; /* * 在转换的过程中,HashMap相当于是把原来链表上元素的的顺序颠倒了。 * 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后 * 就变成了e2->e1->null */ for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { //我认为此处是出现死循环的罪魁祸首 Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 那么回路究竟是如何产生的呢,问题就出在next=e.next这个地方,在多线程并发的环境下,为了便于分析,我们假设就两个线程P1,P2。src[i]的链表顺序是e1->e2->null。我们分别线程P1,P2的执行情况。 首先,P1,和P2进入到了for循环中,这时候在线程p1和p2中,局部变量分别如下:
此时两个Entry的顺序是依然是最开始的状态e1->e2->null, 但是此时p1可能某些原因线程暂停了,p2则继续执行,并执行完了do while循环。这时候Entry的顺序就变成了e2->e1->null。在等到P2执行完之后,可能p1才继续执行,这时候在P1线程中局部变量e的值为e1,next的值为e2(注意此时两个元素在内存中的顺序变成了e2->e1->null),下面P1线程进入了do while循环。这时候P1线程在新的Entry数组中找到e1的位置, e.next = newTable[i]; newTable[i] = e; 下面会把next赋值给e,这时候e的值成为了e2,继续下一次循环,这时候
e2->next=e1,这个是线程P2的"功劳"。程序执行完这次循环之后,e=e1, 继续第三次循环,这时候根据算法,就会进行e1->next=e2。 这样在线程P1中执行了 e1->next=e2,在线程P2中执行了 e2->next=e1,这样就形成了一个环。在get操作的时候,next值永远不为null,造成了死循环。 实际上,刚开始我碰到这个说法的时候,还被吓了一跳,HashMap怎么还会出现这个问题呢,仔细分析一下,这个问题再高并发的场景下是很容易出现的。Sun的工程师建议在这样的场景下应采用ConcurrentHashMap。具体参考http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457 。 虽然这个问题再平时的工作中还没有遇到,但是以后需要注意。要在不同的场景下选择合适的类,规避类似HashMap这种死循环的问题。
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
好文章,多线程编程时还是要多考虑
|
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
wj_126mail 写道 好文章,多线程编程时还是要多考虑
确实好文章 |
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
以前只知道会出现死循环,但是具体原因不太清楚,呵呵,加精!
|
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
最后修改:2011-03-15
void transfer(Entry[] newTable) {
Entry[] src = table; int newCapacity = newTable.length; /* * 在转换的过程中,HashMap相当于是把原来链表上元素的的顺序颠倒了。 * 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后 * 就变成了e2->e1->null */ for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { //我认为此处是出现死循环的罪魁祸首 Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 你确定是倒序? 有点不解:在下慢慢道来 HashMap的put方法: public V put(K key, V value) { if (key == null) return putForNullKey(value); [color=red]int hash = hash(key.hashCode());[/color] int i = indexFor(hash, table.length); 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++; [color=red]addEntry(hash, key, value, i);[/color] return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new [color=red]Entry<K,V>(hash, key, value, e);[/color] if (size++ >= threshold) resize(2 * table.length); } Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; [color=red]hash = h;[/color] } static int indexFor(int h, int length) { return h & (length-1); } static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 以下是我测试indexFor的代码和结果,不知道问题出在哪: Entry[] newTable = new Entry[3]; int newCapacity = newTable.length; System.out.println(hash("p1".hashCode())+"-->"+indexFor(hash("p1".hashCode()), newCapacity)); System.out.println(hash("p2".hashCode())+"-->"+indexFor(hash("p2".hashCode()), newCapacity)); System.out.println(hash("p3".hashCode())+"-->"+indexFor(hash("p3".hashCode()), newCapacity)); 结果:3334-->2 3333-->0 3332-->0 |
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
快来看看!
|
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
chenyongxin 写道 void transfer(Entry[] newTable) {
Entry[] src = table; int newCapacity = newTable.length; /* * 在转换的过程中,HashMap相当于是把原来链表上元素的的顺序颠倒了。 * 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后 * 就变成了e2->e1->null */ for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { //我认为此处是出现死循环的罪魁祸首 Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 你确定是倒序? 有点不解:在下慢慢道来 HashMap的put方法: public V put(K key, V value) { if (key == null) return putForNullKey(value); [color=red]int hash = hash(key.hashCode());[/color] int i = indexFor(hash, table.length); 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++; [color=red]addEntry(hash, key, value, i);[/color] return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new [color=red]Entry<K,V>(hash, key, value, e);[/color] if (size++ >= threshold) resize(2 * table.length); } Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; [color=red]hash = h;[/color] } static int indexFor(int h, int length) { return h & (length-1); } static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 以下是我测试indexFor的代码和结果,不知道问题出在哪: Entry[] newTable = new Entry[3]; int newCapacity = newTable.length; System.out.println(hash("p1".hashCode())+"-->"+indexFor(hash("p1".hashCode()), newCapacity)); System.out.println(hash("p2".hashCode())+"-->"+indexFor(hash("p2".hashCode()), newCapacity)); System.out.println(hash("p3".hashCode())+"-->"+indexFor(hash("p3".hashCode()), newCapacity)); 结果:3334-->2 3333-->0 3332-->0 在resize操作之前,table数组上的某一个元素Entry=tabel[i]上,可能的顺序是e1->e2->null,在resize之后,新的table数组上某个元素Entry=table[j](正常情况下,i!=j,因为新的table和旧的table的大小都不一样了,是吧)。但是e1,e2还是会在同一个链上,因为它们的hash值是相同的。这时候,resize操作针对元素特定的hash值会重新设置next。resize的算法就是先从旧的链表上取第一个,然后放在新的链表上的头部,新链表之前的元素成为了这个元素的next。这样,旧table[i]的顺序是e1->e2->null,那么新的table[j]的顺序不就是e2->e1->null。 这么做是在只需要遍历一边就可以完成整个链表的转换。你可以试着源码静下心分析一下。 |
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-15
chenyongxin 写道 void transfer(Entry[] newTable) {
Entry[] src = table; int newCapacity = newTable.length; /* * 在转换的过程中,HashMap相当于是把原来链表上元素的的顺序颠倒了。 * 比如说 原来某一个Entry[i]上链表的顺序是e1->e2->null,那么经过操作之后 * 就变成了e2->e1->null */ for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { //我认为此处是出现死循环的罪魁祸首 Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 你确定是倒序? 有点不解:在下慢慢道来 HashMap的put方法: public V put(K key, V value) { if (key == null) return putForNullKey(value); [color=red]int hash = hash(key.hashCode());[/color] int i = indexFor(hash, table.length); 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++; [color=red]addEntry(hash, key, value, i);[/color] return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new [color=red]Entry<K,V>(hash, key, value, e);[/color] if (size++ >= threshold) resize(2 * table.length); } Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; [color=red]hash = h;[/color] } static int indexFor(int h, int length) { return h & (length-1); } static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 以下是我测试indexFor的代码和结果,不知道问题出在哪: Entry[] newTable = new Entry[3]; int newCapacity = newTable.length; System.out.println(hash("p1".hashCode())+"-->"+indexFor(hash("p1".hashCode()), newCapacity)); System.out.println(hash("p2".hashCode())+"-->"+indexFor(hash("p2".hashCode()), newCapacity)); System.out.println(hash("p3".hashCode())+"-->"+indexFor(hash("p3".hashCode()), newCapacity)); 结果:3334-->2 3333-->0 3332-->0 实际上,因为HashMap可以存放(null,value)即key可以是null,在resize的时候,所以需要遍历一边,否则,你怎么判断这个table[i]上到底有没有元素呢? |
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-16
写多了, 就成月经贴了。
|
||||||||||||||||
返回顶楼 | ||||||||||||||||
发表时间:2011-03-16
最后修改:2011-03-16
sdh5724 写道 写多了, 就成月经贴了。
刚去查了一下,才知道什么叫做月经贴,out了。 师兄在哪个部门?有时间交流一下! |
||||||||||||||||
返回顶楼 | ||||||||||||||||