1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public class HashMapInfiniteLoop {
private static HashMap<Integer,String> map = new HashMap<Integer,String>( 2 , 0 .75f);
public static void main(String[] args) {
map.put( 5 , "C" );
new Thread( "Thread1" ) {
public void run() {
map.put( 7 , "B" );
System.out.println(map);
};
}.start();
new Thread( "Thread2" ) {
public void run() {
map.put( 3 , "A" );
System.out.println(map);
};
}.start();
}
}
|
其中,map初始化为一个长度为2的数组,loadFactor=0.75,threshold=2*0.75=1,也就是说当put第二个key的时候,map就需要进行扩容。
考虑这样一种情况:
线程1、线程2都添加了数据之后,线程1执行到transfer()方法的第一行就被调度挂起了,这时线程2被调度来执行扩容操作。线程2的扩容操作结束之后,线程1被调度回来继续执行,此时由于线程2的执行,e已经指向了线程2修改之后的反转链表,但是线程1并不知道线程2已经在它之前做过这些操作了,于是它继续往下走,此时next=key(7),
然后计算索引。索引计算完之后执行e.next=newTable[i],此时e.next=key(7)。继续往下走,newTable[i]=e,此时newTable[i]=key(3),再往下,e=next,此时e指向了key(7),本次循环结束。从线程二重组链表结束,到线程1第一轮循环结束的变化图如下:

一切看起来都还没有什么问题。然后新一轮循环开始
这一轮循环我们不需要走完,就能发现问题。
第一句,执行后为:next=null;
第二句,计算索引,还是i
第三句,在这里就出问题了,这句话执行的是e.next=newTable[i],我们看上图,newTable[i]指向的是key(3),因此出现链表末尾的元素的next指针指向了链表头,循环链表就出现了。(按道理,HashMap是不存在循环链表的。)
第四句话,将链表头的元素换成key(7),而循环链表依然存在。
第五句,e=null,执行到这循环结束,因为e=null了。
整个过程并不会发生明显的异常。看起来一切安好。顺利的完成了rehash,但是悲剧在后面:当我们调用get()这个链表中不存在的元素的时候,就会出现死循环。go die