HashMap多线程中引发的死循环

10月 1st, 2012 2,651 留下评论 阅读评论

串叔发现的问题,觉得很有意思,已有文章作详细描述,把原文翻译地讲一下。原文:http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html。

Java的HashMap本身就不支持多线程,是线程不安全的,不过代码中有一些机制来阻止多线程中的不安全因素,比如在多线程修改操作中抛出ConcurrentModificationException,但是HashMap忽视了数组扩容时候这一修改操作,从而导致可能在多线程中进行了不安全的操作。

java.util.HashMap 的 transfer方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
	Entry[] src = table;
	int newCapacity = newTable.length;
	for (int j = 0; j < src.length; j++) {
		Entry e = src[j];
		if (e != null) {
			src[j] = null;
			do {
				Entry next = e.next;				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			} while (e != null);
		}
	}
}

假设现在HashMap中的数组的size为2(桶0和桶1),现在有2个Entry A{key=3}和 B{key=7},于是都位于桶1中形成链表,假设A在B之前,就是array[1]=>A=>B=>null。

假设有2个线程T1和T2同时进行扩容操作,即会同时调用transfer方法。假设T1先于T2抢到CPU执行transfer方法执行到第9行后切换到T2执行,然后T2顺利执行完毕,然后T1继续执行完毕,看一下这个过程的具体。

T1先执行到第9行完毕,变量e=A,next=B。

T2顺利执行完毕,新的数组size为4(桶0-3),A和B还是hash到了同一个桶中,变为T2_newArray[3]=>B=>A=>null,此时A.next=null,B.next=A。

T1继续执行,第一次循环完毕,T1_newArray[3]=>A=>null,e=B,next=B,e!=null进入下一个循环,此时A.next=null,B.next=A。

第二次循环完毕,T1_newArray[3]=>B=>A=>null,e=A,next=A,e!=null进入下一个循环,此时A.next=null,B.next=A。

第三次循环完毕,T1_newArray[3]=>A<=>B,e=null,next=null,e==null跳出循环,此时A.next=B,B.next=A。此时桶3的EntryA和EntryB的next指针互相指向对象,没有一个指向null。

因为T1后执行完毕,HashMap采用T1_newArray作为新的array(见HashMap的resize方法)。

T1和T2的扩容操作完毕,并没有引发任何异常和错误,只是埋下了隐患。

当HashMap继续执行其他get和put操作时,并且得到的hash值为3,即在桶3上进行操作问题就出现了,会进入无限循环,而没有抛出任何异常。

总结

不要信任HashMap防止多线程错误的代码,不能对HashMap进行多线程修改的操作,并发读是可以的。

对HashMap进行线程安全的办法有很多,比如使用java.util.concurrent.ConcurrentHashMap或者使用java.util.Collections.synchronizedMap(Map<K,V> m)方法包装HashMap,或者在自己调用HashMap的方法中使用同步机制。

Categories: Java 标签:
  1. 10月 22nd, 2012 17:13

    HashMap在你使用的过程中,进行扩容和减容,都会引起异常。 以前经常遇到。bug还挺隐蔽的。

  2. 10月 1st, 2012 19:31

    这就是死循环吗??? 之前还是不知道的呢!!!