java - 关于ConcurrentHashMap的putVal方法源代码的一个困惑

Question

以下是 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;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();  // lazy Initialization
        //step1,tabAt(...) is CAS
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //step2,casTabAt(...) is CAS
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
       ...
    return null;
}  

假设当前有两个线程，A和B，当A执行step1时，获取 true ，但同时 B 也执行 step1 并获取 true 。 A 和 B 都执行 step2。

从这种情况来看，B的Node取代了A的Node，或者说A的数据被B替换，这是错误的。

不知道是对还是错，谁能帮我解决一下吗？

Answer 1

以下是 casTabAt 的实现方式:

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

而U声明如下:private static final sun.misc.Unsafe U;。此类的方法在低级别保证原子性。从这个用法来看:

casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))

我们可以看到，assuming that the third parameter of compareAndSwapObject is expected value, that ，由于保证了原子性，首先执行 compareAndSwapObject 的 A 或 B 线程将看到 null 这里和 compareAndSwapObject 实际上会替换对象，而下一个执行 compareAndSwapObject 的线程不会更改该值，因为 实际值不再为 null，而 null 被期望作为对值进行更改的条件。