HashMap为何线程不安全？HashMap，HashTable，ConcurrentHashMap对比

时间：2022-11-30 18:06:15

这两天写爬虫帮组里收集网上数据做训练，需要进一步对收集到的json数据做数据清洗，结果就用到了多线程下的哈希表数据结构，猛地回想起自己看《Java并发编程的艺术》框架篇的时候，在ConcurrentHashMap的章节看到过使用HashMap是线程不安全的，HashTable虽然安全但效率很低，推荐使用ConcurrentHashMap巴拉巴拉，突然有了兴趣来查阅一下各自的源码，看看具体区别在哪里呢？HashMap为什么线程不安全？顺带记录下来，还是那句话，好记性不如烂笔头

我们知道的Java中的哈希表数据结构有下面三种

  • HashMap
  • HashTable
  • ConcurrentHashMap

下面就依次来看看它们是如何保证并发时可靠的，各自有什么优缺点

HashMap

首先是大家都很熟悉的哈希表：HashMap，刷算法题必备哈希表数据结构。它的存储结构如下图所示

HashMap为何线程不安全？HashMap，HashTable，ConcurrentHashMap对比

很好看懂的一个图，简单来说就是HashMap采用的是拉链法处理哈希冲突。所谓哈希冲突就是由于哈希表根据哈希值索引目标节点来对随机存取获得O(1)的时间复杂度，那么每个哈希值当然只能站一个节点，如果存在多个节点计算出的哈希值一致就发生了哈希冲突，此时一般有三种思路：

  • 拉链法：在一个哈希值上设置一个数据集结构，也就是一个哈希值代表一个数据集，我们对数据集的随机存取获得O(1)时间复杂度，对数据集内获取目标Key节点获得O(m)时间复杂度，如果哈希值的数量远多于数据集内节点的数量，那么我们近似取到O(1)时间复杂度
  • 开放定址法：一旦碰到哈希冲突就顺延后来的节点的哈希值，比如节点A取哈希为1，而哈希值1,2,3上都已经有节点在了，那么我们根据顺延规则取4作为该节点的真实存储位置，这种方案一般表现比较糟糕
  • 再哈希法：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个，第四个等等等等的其他的哈希函数计算地址，直到不发生冲突为止。虽然不易发生聚集，但是大大增加了计算时间

这里我们常用的三种哈希表结构全部是采用的拉链法，这是一种认可度较高的解决方案，那么拉链法就要求我们每个哈希值都独立设置一个链表来存储哈希冲突的节点。那么我们关于多线程安全的问题自然也就来自于此。
总的来说，HashMap在多线程时视使用的Java版本有以下三大问题

  • 数据覆盖(一直存在)
  • 死循环(JDK1.7前存在)
  • 数据丢失(JDK1.7前存在)
    我们一个一个来看

数据覆盖

顾名思义，两个线程同时往里面放数据，但是其中一个数据放丢了，这个问题是根本问题，目前的HashMap依然有这个问题，出问题的原因也很简单，HashMap本来就没做多线程适配当然出问题，但是原理还是值得一看。

// 代码截取自HashMap.java，方法final V putVal()中
for (int binCount = 0; ; ++binCount) {
    // 根据下面代码，我们看出其实插入新节点就是反复探测目前节点的next指针是否为空，若为空则在该指针上插入新节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

看完以后我们发现，其实就是很简单的探测链表尾部的方法，看该节点next指针是否为null，若为null说明是尾节点，在其后插入新节点，那么数据覆盖的真相也就很简单了：A，B两个线程同时向同一个哈希值的链表发起插入，A探测到C节点的next为空然后时间片用完被换下，此时B也探测到C的next为空并完成了插入，等到A再次换入时间片，完成插入，最终，A，B运行结束，但B插入的新节点就这样消失了。这就是数据覆盖问题。

死循环与数据丢失
其实这两个问题的核心都来自JDK1.7前，HashMap的扩容操作(扩容采用头插法插入)会重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。而头插法会将链表的顺序翻转，这也是造成死循环和数据丢失的关键。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 采用头插法
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

怎么一回事呢？

现在假设线程启动，有线程A和线程B都准备对HashMap进行扩容操作， 此时A和B指向的都是链表的头节点NodeA，而A和B的下一个节点的指针即head.next和head.next都指向NodeB节点。

那么，开始扩容，这时候，假设线程B的时间片用完，被换下CPU，而线程A开始执行扩容操作，一直到线程A扩容完成后，线程B才被唤醒。

此时因为HashMap扩容采用的是头插法，线程A执行之后，链表中的节点顺序已经倒转，本来NodeA->NodeB，现在变成了NodeB->NodeA。但就绪态的线程B对于发生的一切都不清楚，所以它指向的节点引用依然没变。那么一旦B被换上CPU，重复一次刚刚A做过的事情，就会导致NodeA和NodeB的next指针相互指向，导致死循环和数据丢失。

不过JDK1.8以后，HashMap的哈希值扩容改为了尾插法扩容，就不会再出现这些问题了。

HashTable

效率很差的一个类，根据我自己的周边统计学，我的感觉是这个玩意根本没人用，用它就类似于如果你给线上项目的MySQL突然整出个表级锁一样，等你的只能是一通臭骂！为什么呢？看下面

// 你就看这个synchronized关键字就可以了，不用往下看了
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

很明显了。HashTable采用了Synchronized关键字来保证线程安全。

我们知道Synchronized关键字的底层原理是给对象头上的MarkWord的内容做改动从而将该对象当作互斥变量使用，也就是说，这把锁是对象级别的。
问题就在于我本来哈希冲突只是一个哈希值上的冲突，而你的解决方案是锁住整个哈希表，这会不会有点太过分了？可以说表级锁的比喻是很贴切了。

不推荐使用，效率很低。

ConcurrentHashMap

《Java并发编程的艺术》里面提到的第一个并发结构，它的思路就是在HashTable表级锁的基础上把它改为行级锁，什么意思呢？放源码

// 截取自ConcurrentHashMap.java，final V putVal()方法
// 注意下面这句，f 是我们需要的哈希值对应的首节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
      if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
          break;                   // no lock when adding to empty bin
  }
  else if ((fh = f.hash) == MOVED)
      tab = helpTransfer(tab, f);
  else if (onlyIfAbsent // check first node without acquiring lock
           && fh == hash
           && ((fk = f.key) == key || (fk != null && key.equals(fk)))
           && (fv = f.val) != null)
      return fv;
  else {
      V oldVal = null;
// 来到这里，上面的都不用看，主要是排查初始化情况，这里synchronized(f)就解释清楚了我们的ConcurrentHashMap的方法
      synchronized (f) {
          if (tabAt(tab, i) == f) {
              if (fh >= 0) {
                  binCount = 1;
                  for (Node<K,V> e = f;; ++binCount) {
                      K ek;
                      if (e.hash == hash &&
                          ((ek = e.key) == key ||
                           (ek != null && key.equals(ek)))) {
                          oldVal = e.val;
                          if (!onlyIfAbsent)
                              e.val = value;
                          break;
                      }
                      Node<K,V> pred = e;
                      if ((e = e.next) == null) {
                          pred.next = new Node<K,V>(hash, key, value);
                          break;
                      }
                  }
              }

很明显，ConcurrentHashMap同样是通过Synchronized关键字来实现线程安全的，只不过这把锁从原来的表级锁，变为了以首节点为对象的行级锁，当我们并发的对ConcurrentHashMap操作时，锁只会锁住某一个哈希值，而不会锁住整个表，保证了我们的哈希表在高并发场景下的效率。

总结

HashMap只适用于非并发情况下，ConcurrentHashMap适用于并发情况下，而HashTable则不推荐使用

相关文章