JDK8 ConcurrentHashMap 用 CAS 取代 Segment 锁

ConcurrentHashMap 锁粒度

JDK8 中，ConcurrentHashMap 的锁粒度变小，不再是对 Segment 加锁，而是对桶的头结点加锁，这样大大提高的并发的性能。

那么在没有锁的情况下，如何保证多个线程的 put 不会相互覆盖？

无锁实现：for 循环 + CAS

CAS，即 compareAndSwap，原子的执行比较并交换的操作：当前内存值如果和预期值相等，则将其更新为目标值，否则不更新。

JDK8 通过 for 循环 + CAS 操作，实现并发安全的方式就是无锁算法（lock free）的经典实现。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    ...
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        ...
        //key定位到的hash桶为空
        if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //cas设置tab[i]的头结点。
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;   //设置成功，跳出for循环
            
            //设置失败，说明tab[i]已经被另一个线程修改了。回到for循环开始处，
            //重新判断hash桶是否为空。如何往复，直到设置成功，或者hash桶不空。
        }else{
           synchronized (f) {
               //
           }
            
        }
    }
    ...
}

如下图所示，在不加锁的情况下：线程 A 成功执行 casTabAt 操作后，随后的线程 B 可以通过 tabAt 方法立刻看到 table[i] 的改变。原因如下：线程 A 的 casTabAt 操作，具有 volatile 读写相同的内存语义，根据 volatile 的happens-before 规则：线程 A 的 casTabAt 操作，一定对线程 B 的 tabAt 操作可见。

Java 原子类的自增操作，也是通过 for 循环 + CAS 操作的方式实现的：

//JDK7版本的 AtomicInteger 类的原子自增操作
public final int getAndIncrement() {
    for (;;) {
        //获取value
        int current = get();
        int next = current + 1;
        //value值没有变，说明其他线程没有自增过,将value设置为next
        if (compareAndSet(current, next))
            return current;
        //否则说明value值已经改变，回到循环开始处，重新获取value。
    }
}

参考：[简书] ConcurrentHashMap源码分析（JDK8） get/put/remove方法分析