从put操作看ConcurrentHashMap如何解决线程安全问题

从put操作看ConcurrentHashMap如何解决线程安全问题

引用

CSDN

1.

https://blog.csdn.net/weixin_43810802/article/details/125089296

在多线程环境下，HashMap的线程不安全性可能导致数据丢失等问题。本文通过对比分析HashMap和ConcurrentHashMap的put操作实现，详细解释了ConcurrentHashMap如何使用CAS和自旋锁来保证线程安全。

HashMap的线程不安全性

HashMap（JDK 1.8）在多线程环境下是不安全的，其中一个典型体现是put方法的实现。我们来看一下put方法的大致逻辑：

如果原来table中没有相同hash值的节点，就会创建一个新的节点。假设线程A和线程B同时执行put操作，且key的hash值相同，那么它们会同时执行以下代码：

if ((p = tab[i = (n - 1) & hash]) == null)

假设之前没有hash冲突的节点存在，那么A和B线程就会都执行：

tab[i] = newNode(hash, key, value, null);

这样后执行的线程就会覆盖先执行的线程，导致数据丢失。

为了验证这个现象，我们可以编写如下测试代码：

public class TestHashMapThreadSafe {
    public static void main(String[] args) throws InterruptedException {
        HashMap<Integer, String> map = new HashMap<>();
        Thread thread1 = new Thread(() -> {
            map.put(1, "a");
        }, "A");
        thread1.start();
        Thread thread2 = new Thread(() -> {
            map.put(17, "b");
        }, "B");
        thread2.start();
        Thread.sleep(1000 * 5);
        System.out.println(map);
    }
}

为了让效果更明显，我们需要修改put方法的源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null){
        if(key instanceof Integer){
            Integer intKey = (Integer) key;
            if(intKey == 1 || intKey == 17){
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName() + " with key==" + key + " try to new node");
            }
        }
        tab[i] = newNode(hash, key, value, null);
    }
    ...
}

运行结果如下：

A with key==1 try to new node
B with key==17 try to new node
{17=b}

可以看到，最终只有一个元素，显然是有问题的。

ConcurrentHashMap的解决方案

ConcurrentHashMap是如何解决上面这个问题的呢？它使用了CAS（Compare and Swap）和自旋锁。自旋锁就是外面那个for循环，失败了就重试直到退出。

我们来看一下ConcurrentHashMap的putVal方法：

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        if(key instanceof Integer){
            Integer intKey = (Integer) key;
            if(intKey == 1 || intKey == 17){
                System.out.println(Thread.currentThread().getName() + " enter for loop...");
            }
        }
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if(key instanceof Integer){
                Integer intKey = (Integer) key;
                if(intKey == 1 || intKey == 17){
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + " with key==" + key + " try to new node");
                }
            }
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null))){
                if(key instanceof Integer){
                    Integer intKey = (Integer) key;
                    if(intKey == 1 || intKey == 17){
                        System.out.println(Thread.currentThread().getName() + " cas succeeds...");
                    }
                }
                break;                   // no lock when adding to empty bin
            }else {
                if(key instanceof Integer){
                    Integer intKey = (Integer) key;
                    if(intKey == 1 || intKey == 17){
                        System.out.println(Thread.currentThread().getName() + " cas fails...");
                    }
                }
            }
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            ...
        }
    }
}

运行结果如下：

A enter for loop...
A enter for loop...
B enter for loop...
B with key==17 try to new node
B cas succeeds...
A with key==1 try to new node
A cas fails...
A enter for loop...
{17=b, 1=a}

可以看到，只有一个线程会CAS成功，另一个线程会重新进入for循环并挂在前一个节点下面。这是因为ConcurrentHashMap使用了CAS操作来保证线程安全，同时使用自旋锁来处理竞争情况。