1. ConcurrentHashMap 实现原理

Node + CAS + Synchronized

jdk 1.7 时采用 ReentrantLock + Segment + HashEntry, 把 HashMap 分成多个段, 每个段一个锁.
jdk 1.8 时采用 Node + CAS + Synchronized + 链表/红黑树, 每个 bin 一个锁(bin 的首节点).
1.8 相较于 1.7 实现更清晰, 锁的粒度更低, 性能更高.

2. ConcurrentHashMap 在 JDK 1.8 中, 为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock ?

Segment 继承 ReentrantLock

锁的粒度降低了
ReentrantLock 的内存消耗比 synchronized 更大

3. ConcurrentHashMap 的并发度是什么？

A: 程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数. 默认为 16, 且可以在构造函数中设置. 当用户设置并发度时, ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度 (假如用户设置并发度为17, 实际并发度则为32)

4. 为什么 ConcurrentHashMap 的读操作不需要加锁?

//会发现源码中没有一处加了锁
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;
}

5. 实现原理

特殊的 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 的包装, 而是包装了整个红黑树, 所有对红黑树的操作都是从这个节点触发.

5.1. 初始化 initTable

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

5.2. put 方法

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

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

5.3. get 方法

5.4. 什么时候加锁

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

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

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

Raven's Wiki

concurrenthashmap-faq