ConcurrentHashMap 不允许插入 key 为 null 的键

ConcurrentHashMap 比 HashTable 性能更好

HashTable 采用方法级同步, 同一时间只能读或者写, 由于锁的粒度比较粗, 并发情况下, 锁的竞争比较激烈, 性能较差;
jdk 1.8 中 ConcurrentHashMap 采用 CAS + Synchronized, 锁的力度比较细. 其中 Synchronized 作用在链表/红黑树的头结点上.

数据结构:

jdk 1.7: Segment+HashEntry;
jdk 1.8: 数组+链表/红黑树, 通过 CAS + synchronized 保证并发一致性

1.8 相较于 1.7 实现更清晰, 锁的粒度更低, 性能更高.

1. 实现原理

特殊的 hash 值:

MOVED: -1, 表示正在迁移的节点
TREEBIN: -2, 红黑树节点
RESERVED: -3, hash for transient reservations
正数: 表示链表节点

sizeCtl:

-1: 表示正在初始化
-N: 表示有 n -1 个线程正在进行扩容
0: 表示还没有初始化
正数: 表示下次要扩容的大小

类型:

Node: 其他节点的父类, 对 value 和 next 都增加了 volatile, 保证节点在修改时的可见性.
ForwardingNode: 其 hash 值为 -1, 当扩容时替换 bin, 标识节点扩容去了, 其中的属性 nextTable 指向正在扩容的 table.
TreeBin: 其 hash 值为 -2, 本身并不负责 key-value 的包装, 而是包装了整个红黑树, 所有对红黑树的操作都是从这个节点触发.

1.1. 初始化 initTable

对 sizeCtl 做 cas, 如果成功则做扩容
如果正在扩容则等待
如果已经完成扩容则返回

1.2. put 方法

循环以下操作, 知道 put 完成

如果发现没有初始化, 则初始化
如果发现没有首节点, 则 cas 创建首节点
如果发现 bin 正在进行扩容, 则帮助扩容
加同步锁, 对 bin 中内容进行 put 操作

2. get 方法

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()); //计算hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
        if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值为负值表示正在扩容, 这个时候查的是ForwardingNode的find方法来定位到nextTable来
        //eh=-1, 说明该节点是一个ForwardingNode, 正在迁移, 此时调用ForwardingNode的find方法去nextTable里找. 
        //eh=-2, 说明该节点是一个TreeBin, 此时调用TreeBin的find方法遍历红黑树, 由于红黑树有可能正在旋转变色, 所以find里会有读写锁. 
        //eh>=0, 说明该节点下挂的是一个链表, 直接遍历该链表即可. 
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode, 那就往下遍历
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

2.1. 什么时候加锁 ?

对 bin 进行加锁, 也就是 bin 的首节点

当对 bin 中内容做修改时需要加锁:
putVal
replaceNode
clear
transfer
treeifyBin

当对 map 做计算的时候需要加锁:
computeIfAbsent
computeIfPresent
compute
merge

3. 常见问题

3.1. ConcurrentHashMap 死循环

在使用 computeIfAbsent() 时, 会新建 ReservationNode, 之后在 tranfer() 方法中, 由于没有处理 ReservationNode, 导致无法跳出循环.

如: jasypt-spring-boot-starter 2.1.0 服务起不来的 bug:
DefaultLazyEncryptor 中的 getProperty() 会用到 ConcurrentHashMap#computeIfAbsent 导致死循环后服务起不来.

中间关联的是使用了 org.springframework.cache.concurrent.ConcurrentMapCache#get() 方法

public <T> T get(Object key, Callable<T> valueLoader) {
    return (T) fromStoreValue(this.store.computeIfAbsent(key, k -> {
        try {
            return toStoreValue(valueLoader.call());
        }
        catch (Throwable ex) {
            throw new ValueRetrievalException(key, valueLoader, ex);
        }
    }));
}

4. Resource

https://www.jianshu.com/p/d10256f0ebea