public class HashMapTest extends Thread { private static HashMap<Integer, Integer> map = new HashMap<>(2); private static AtomicInteger at = new AtomicInteger(); @Override public void run() { while (at.get() < 1000000) { map.put(at.get(), at.get()); at.incrementAndGet(); } } public static void main(String[] args) { HashMapTest t0 = new HashMapTest(); HashMapTest t1 = new HashMapTest(); HashMapTest t2 = new HashMapTest(); HashMapTest t3 = new HashMapTest(); HashMapTest t4 = new HashMapTest(); HashMapTest t5 = new HashMapTest(); t0.start(); t1.start(); t2.start(); t3.start(); t4.start(); t5.start(); for (int i = 0; i < 1000000; i++) { Integer integer = map.get(i); System.out.println(integer); } } } 复制代码
反复执行几次,出现这种情况则表示死循环了:
由上可知,Thread-7由于HashMap的扩容导致了死循环。
1 void transfer(Entry[] newTable, boolean rehash) { 2 int newCapacity = newTable.length; 3 for (Entry<K,V> e : table) { 4 while(null != e) { 5 Entry<K,V> next = e.next; 6 if (rehash) { 7 e.hash = null == e.key ? 0 : hash(e.key); 8 } 9 int i = indexFor(e.hash, newCapacity); 10 e.next = newTable[i]; 11 newTable[i] = e; 12 e = next; 13 } 14 } 15 } 复制代码
我们先来看下单线程情况下,正常的rehash过程:
在单线程情况下,一切看起来都很美妙,扩容过程也相当顺利。接下来看下并发情况下的扩容。
有两个线程,分别用红色和蓝色标注了。
在线程1执行到第5行代码就被CPU调度挂起(执行完了,获取到next是7),去执行线程2,且线程2把上面代码都执行完毕。我们来看看这个时候的状态
注意::线程二已经完成执行完成,现在table里面所有的Entry都是最新的,就是说7的next是3,3的next是null;现在第一次循环已经结束,3已经安置妥当。
这个时候其实就出现了死循环了,3移动节点头的位置,指向7这个Entry;在这之前7的next同时也指向了3这个Entry。
出现问题的关键原因: 如果扩容前相邻的两个Entry在扩容后还是分配到相同的table位置上,就会出现死循环的BUG 。在复杂的生产环境中,这种情况尽管不常见,但是可能会碰到。
下面来介绍下元素丢失的问题。这次我们选取3、5、7的顺序来演示:
JDK 8 中采用的是位桶 + 链表/红黑树的方式,当某个位桶的链表的长度超过 8 的时候,这个链表就将转换成红黑树
HashMap 不会因为多线程 put 导致死循环(JDK 8 用 head 和 tail 来保证链表的顺序和之前一样;JDK 7 rehash 会倒置链表元素),但是还会有数据丢失等弊端(并发本身的问题)。因此多线程情况下还是建议使用 ConcurrentHashMap