ConcurrentHashMap

数组 + 链表 + 红黑树，CAS

ConcurrentHashMap 使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制称为分段锁（Lock Striping），在这种机制中：

• 任意数量的读取线程可以并发地访问 Map

• 执行读取操作的线程和执行写入操作的线程可以并发地访问 Map

• 一定数量的写入线程可以并发地修改 Map

ConcurrentHashMap 带来的结果是，在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。

ConcurrentHashMap 的迭代器不会抛出 ConcurrentModificationException。

ConcurrentHashMap 返回的迭代器具有弱一致性（Weakly Consistent），而并非“及时失败”。弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以（但是不保证）在迭代器被构造后将修改操作反映给容器。

对于一些需要在整个 Map 上进行计算的方法，例如 size 和 isEmpty，这些方法的语义被略微减弱了以反映容器的并发特性。由于 size 返回的结果在计算时可能已经过期了，它实际上只是一个估计值，因此允许 size 返回一个近似值而不是一个精确值。

虽然这看上去有些令人不安，但事实上 size 和 isEmpty 这样的方法在并发环境下的用处很小，因为它们的返回值总在不断变化。因此，这些操作的需求被弱化了，以换取对其他更重要操作的性能优化，包括 get、put、containsKey 和 remove 等。

ConcurrentHashMap

// volatile 和 final 用于保证可见性
volatile Node<K,V>[] table;
    
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    ...    
}

// get 方法未使用锁
public V get(Object key) {
    Node<K,V>[] tab; 
    Node<K,V> e, p; 
    int n, eh; 
    K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

public V put(K key, V value) {
    return putVal(key, value, false);
}

/**
 * 在 putVal 方法中使用了两种同步机制：
 *    1. CAS：使用 CAS 在 Node 数组中增加节点
 *    2. 分段锁：每一个哈希桶中的列表，都使用头节点作为锁对象
 */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    ...
    for (Node<K,V>[] tab = table;;) {
        ...
        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 {
            V oldVal = null;
            synchronized (f) {
               ...
            }
            ...
        }
    }
    addCount(1L, binCount);
    return null;
}

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

final long sumCount() {
    CounterCell[] cs = counterCells;
    long sum = baseCount;
    if (cs != null) {
        for (CounterCell c : cs)
            if (c != null)
                sum += c.value;
    }
    return sum;
}

/**
 * A padded cell for distributing counts.  Adapted from LongAdder
 * and Striped64.  See their internal docs for explanation.
 */
@jdk.internal.vm.annotation.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

JDK1.7 实现

在 JDK1.5 ~ 1.7 版本中，Java 使用了分段锁机制实现 ConcurrentHashMap：

• ConcurrentHashMap 在对象中保存了一个 Segment 数组，从而整个 Hash 表划分为多个分段；

• 而每个 Segment 元素，它通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全；

在执行 put 操作时首先根据 hash 算法定位到元素属于哪个 Segment，然后对该 Segment 加锁即可。Segment 数量默认是 16，理论上这个时候最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。