转载

HashMap在多线程下不安全问题(JDK1.7)

  1. 多线程put操作后,get操作导致死循环。
  2. 多线程put操作,导致元素丢失。

死循环场景重现

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);
        }
    }
}
复制代码

反复执行几次,出现这种情况则表示死循环了:

HashMap在多线程下不安全问题(JDK1.7)

由上可知,Thread-7由于HashMap的扩容导致了死循环。

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. 假设我们的hash算法是简单的key mod一下表的大小(即数组的长度)。
  2. 最上面是old hash表,其中HASH表的size=2,所以key=3,5,7在mod 2 以后都冲突在table[1]这个位置上了。
  3. 接下来HASH表扩容,resize=4,然后所有的<key,value>重新进行散列分布,过程如下:
HashMap在多线程下不安全问题(JDK1.7)

在单线程情况下,一切看起来都很美妙,扩容过程也相当顺利。接下来看下并发情况下的扩容。

并发情况下的扩容

  1. 有两个线程,分别用红色和蓝色标注了。

  2. 在线程1执行到第5行代码就被CPU调度挂起(执行完了,获取到next是7),去执行线程2,且线程2把上面代码都执行完毕。我们来看看这个时候的状态

HashMap在多线程下不安全问题(JDK1.7)
  1. 接着CPU切换到线程1上来,执行4-12行代码(已经执行完了第五行),首先安置健值为3这个Entry:
HashMap在多线程下不安全问题(JDK1.7)

注意::线程二已经完成执行完成,现在table里面所有的Entry都是最新的,就是说7的next是3,3的next是null;现在第一次循环已经结束,3已经安置妥当。

  1. 看看接下来会发生什么事情:
    • e=next=7;
    • e!=null,循环继续
    • next=e.next=3
    • e.next 7的next指向3
    • 放置7这个Entry,现在如图所示:
HashMap在多线程下不安全问题(JDK1.7)
  1. 放置7之后,接着运行代码:
    • e=next=3;
    • 判断不为空,继续循环
    • next= e.next 这里也就是3的next 为null
    • e.next=7,就3的next指向7.
    • 放置3这个Entry,此时的状态如图
HashMap在多线程下不安全问题(JDK1.7)

这个时候其实就出现了死循环了,3移动节点头的位置,指向7这个Entry;在这之前7的next同时也指向了3这个Entry。

  1. 代码接着往下执行,e=next=null,此时条件判断会终止循环。这次扩容结束了。但是后续如果有查询(无论是查询的迭代还是扩容),都会hang死在table[3]这个位置上。现在回过来看文章开头的那个Demo,就是挂死在扩容阶段的transfer这个方法上面。

出现问题的关键原因: 如果扩容前相邻的两个Entry在扩容后还是分配到相同的table位置上,就会出现死循环的BUG 。在复杂的生产环境中,这种情况尽管不常见,但是可能会碰到。

多线程put操作,导致元素丢失

下面来介绍下元素丢失的问题。这次我们选取3、5、7的顺序来演示:

  1. 如果在线程一执行到第5行代码就被CPU调度挂起:
HashMap在多线程下不安全问题(JDK1.7)
  1. 线程二执行完成:
HashMap在多线程下不安全问题(JDK1.7)
  1. 这个时候接着执行线程一,首先放置7这个Entry:
HashMap在多线程下不安全问题(JDK1.7)
  1. 再放置5这个Entry:
HashMap在多线程下不安全问题(JDK1.7)
  1. 由于5的next为null,此时扩容动作结束,导致3这个Entry丢失。

JDK 8 的改进

JDK 8 中采用的是位桶 + 链表/红黑树的方式,当某个位桶的链表的长度超过 8 的时候,这个链表就将转换成红黑树

HashMap 不会因为多线程 put 导致死循环(JDK 8 用 head 和 tail 来保证链表的顺序和之前一样;JDK 7 rehash 会倒置链表元素),但是还会有数据丢失等弊端(并发本身的问题)。因此多线程情况下还是建议使用 ConcurrentHashMap

原文  https://juejin.im/post/5d8c261de51d4577ea077e94
正文到此结束
Loading...