JDK 7:Segment分段锁
┌─────────────────────────────────────────────┐
│ Segment[] (默认16段) │
│ ┌──────────┐ ┌──────────┐ │
│ │Segment 0 │ │Segment 1 │ ... │
│ │ Reentrant│ │ Reentrant│ │
│ │ Lock │ │ Lock │ │
│ │ ┌──────┐ │ │ ┌──────┐ │ │
│ │ │HashEn│ │ │ │HashEn│ │ │
│ │ │try[] │ │ │ │try[] │ │ │
│ │ │ ↓↓↓ │ │ │ │ ↓↓↓ │ │ │
│ │ │链表 │ │ │ │链表 │ │ │
│ │ └──────┘ │ │ └──────┘ │ │
│ └──────────┘ └──────────┘ │
└─────────────────────────────────────────────┘
并发度 = Segment数量(默认16,创建后不可变)
JDK 8:CAS + synchronized + 细粒度锁
┌─────────────────────────────────────────────┐
│ Node[] table(和HashMap类似的结构) │
│ ┌─────┐ │
│ │ [0] │ → null │
│ ├─────┤ │
│ │ [1] │ → Node → Node → ... (链表) │
│ ├─────┤ │
│ │ [2] │ → TreeBin → TreeNode... (红黑树) │
│ ├─────┤ │
│ │ [3] │ → ForwardingNode (迁移中标记) │
│ └─────┘ │
│ │
│ 锁粒度:单个桶的头节点(synchronized) │
│ 并发度 = 数组长度(可动态扩展) │
└─────────────────────────────────────────────┘
| 对比项 | JDK 7 | JDK 8 |
|---|---|---|
| 数据结构 | Segment[] + HashEntry[] + 链表 | Node[] + 链表 + 红黑树 |
| 锁机制 | Segment级别ReentrantLock | 桶级别CAS + synchronized |
| 并发度 | 固定(默认16) | 动态(=数组长度) |
| 查询复杂度 | O(n)链表 | O(log n)红黑树 |
| 扩容 | 各Segment独立扩容 | 多线程协助扩容 |
// sizeCtl 的多种含义(非常重要!)
// -1 : 表正在初始化(只有一个线程能初始化)
// -(1 + nThreads) : 有n个线程正在参与扩容
// 0 : 表还没初始化
// > 0 : 下次扩容的阈值(capacity * loadFactor)
// 其他关键节点类型
static final int MOVED = -1; // ForwardingNode(迁移中)
static final int TREEBIN = -2; // TreeBin(红黑树根节点)
static final int RESERVED = -3; // ReservationNode(computeIfAbsent占位)
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); // 扰动函数
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// ① 延迟初始化table
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// ② 桶为空 → CAS插入(无锁!)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break;
}
// ③ 桶头是ForwardingNode → 协助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// ④ 桶不为空 → 加锁插入
else {
synchronized (f) { // 锁住桶头节点!
if (tabAt(tab, i) == f) { // double-check
if (fh >= 0) {
// 链表处理
int binCount = 0;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// key已存在,更新value
V oldVal = e.value;
if (!onlyIfAbsent || oldVal == null)
e.value = value;
afterNodeAccess(e);
return oldVal;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
}
}
else if (f instanceof TreeBin) {
// 红黑树处理
Node<K,V> p;
int binCount = 0;
if ((p = ((TreeBin<K,V>)f).findTreeNode(hash, key, null)) != null) {
V oldVal = p.value;
if (!onlyIfAbsent || oldVal == null)
p.value = value;
afterNodeAccess(p);
return oldVal;
}
// 插入新节点到红黑树...
}
}
}
}
// ⑤ 检查是否需要扩容
addCount(1L, binCount);
}
return null;
}
putVal流程图:
┌──────────────────────────────────────────────────────────────┐
│ ConcurrentHashMap.putVal │
├──────────────────────────────────────────────────────────────┤
│ │
│ table未初始化? → initTable()(CAS自旋,只允许一个线程) │
│ │
│ 桶为空? → casTabAt() 无锁CAS插入 │
│ │成功 → break │
│ │失败 → 自旋重试 │
│ │
│ 桶头hash==MOVED? → helpTransfer() 协助扩容 │
│ │
│ 桶不为空 → synchronized(桶头节点) 加锁 │
│ ├── double-check桶头是否变化 │
│ ├── 链表:遍历查找/尾插 │
│ │ └── binCount≥8 → treeifyBin() │
│ └── 红黑树:TreeBin.findTreeNode/putTreeNode │
│ │
│ addCount(1, binCount) → 检查是否需要扩容 │
│ │
└──────────────────────────────────────────────────────────────┘
// 使用Unsafe进行volatile读取(保证可见性)
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// CAS设置桶的节点
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);
}
// 为什么不直接用 tab[i]?
// 因为Node数组元素本身不是volatile的(避免所有写都触发MESI协议)
// 而是通过Unsafe的getObjectVolatile/compareAndSwapObject
// 实现对单个桶的精确volatile读写
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // sizeCtl=-1,其他线程正在初始化,让出CPU
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
// CAS成功,获得初始化权
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] nt = (Node<K,V>[])new Node[n];
table = tab = nt;
sc = n - (n >>> 2); // sc = 0.75 * n
}
} finally {
sizeCtl = sc; // 设置扩容阈值
}
break;
}
}
return tab;
}
扩容触发条件:元素总数 > sizeCtl(即 capacity * 0.75)
核心机制:多线程分段迁移
原数组(长度=32):
[0][1][2][3]...[15][16][17]...[31]
线程A负责迁移:桶 0~7
线程B负责迁移:桶 8~15
线程C负责迁移:桶 16~23
线程D负责迁移:桶 24~31
迁移过程:
1. 每个线程用CAS领取一段桶(默认每段16个桶:stride = NCPU > 1 ? (n >>> 3) / NCPU : n)
2. 从后往前迁移每个桶
3. 迁移完一个桶后,在该桶放入ForwardingNode(hash=MOVED)
4. 其他线程put时发现桶是ForwardingNode → helpTransfer协助迁移
5. 所有桶迁移完成后,切换到新数组
ForwardingNode:
- hash = MOVED (-1)
- 指向新数组 nextTable
- get操作时:如果遇到ForwardingNode,到新数组中查找
// transfer 核心逻辑(简化)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 计算每个线程迁移的步长
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // 最小16
// 第一个发起扩容的线程负责初始化nextTab
if (nextTab == null) {
Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1]; // 2倍
nextTab = nt;
nextTable = nt;
transferIndex = n; // 从数组末尾开始分配
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
for (int i = 0, bound = 0;;) {
// 领取迁移区间:CAS修改 transferIndex
// bound = 本次的起始索引, i = 当前处理的索引
// ...
// 迁移桶 i(和HashMap一样的高低位拆分)
// 迁移完成后 tab[i] = fwd (ForwardingNode)
}
}
// ConcurrentHashMap如何统计元素个数?
// 不能用单个AtomicLong(高并发下CAS竞争激烈)
// 参考 LongAdder 的思路:分散计数
// baseCount + CounterCell[]
// 无竞争时 CAS更新 baseCount
// 有竞争时(CAS失败)→ 使用CounterCell分散计数
private transient volatile CounterCell[] counterCells;
private transient volatile long baseCount;
// size() 方法:求和
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 : (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}
final long sumCount() {
CounterCell[] as = counterCells;
long sum = baseCount;
if (as != null) {
for (CounterCell a : as) {
if (a != null)
sum += a.value;
}
}
return sum;
}
// addCount中的计数逻辑
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 尝试CAS更新baseCount
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// CAS失败 → 分散到CounterCell
CounterCell a; long v; int m;
// ... 在CounterCell[]中CAS更新某个Cell ...
}
// 检查是否需要扩容
if (check >= 0) {
// s = sumCount() > sizeCtl → 扩容
}
}
counterCell结构图:
┌──────────────────────────────────────────┐
│ 元素计数 │
│ │
│ baseCount: 1000 │
│ │
│ CounterCell[]: │
│ ┌───────┬───────┬───────┬───────┐ │
│ │ 200 │ 150 │ null │ 300 │ ... │
│ └───────┴───────┴───────┴───────┘ │
│ │
│ 总数 = baseCount + Σ(counterCells) │
│ = 1000 + 200 + 150 + 300 = 1650 │
│ │
│ 分散计数减少CAS竞争 │
└──────────────────────────────────────────┘
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)
// hash<0 特殊节点处理
// ForwardingNode → 到nextTable查找
// TreeBin → 红黑树查找
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;
}
// get全程无锁!
// Node的val和next都是volatile的,保证可见性
// 即使正在扩容,也能通过ForwardingNode找到正确的数据
Q1: ConcurrentHashMap的key/value能为null吗?
不能。如果get(key)返回null,无法区分是"key不存在"还是"value就是null"。HashMap可以通过containsKey判断,但ConcurrentHashMap在并发环境下containsKey和get之间数据可能变化。
Q2: ConcurrentHashMap的并发度是多少?
JDK 7:并发度=Segment数量(默认16)。JDK 8:并发度=数组长度(动态变化),理论上每个桶可以并行操作。
Q3: 为什么JDK 8用synchronized而不是ReentrantLock?
(1) JDK 6后synchronized经过锁升级优化,轻量级场景下性能不亚于ReentrantLock;(2) synchronized不需要手动unlock,不会忘记释放;(3) synchronized的锁升级(偏向→轻量→重量)更适合"读多写少、锁持有时间短"的场景;(4) 减少内存开销(每个桶如果用ReentrantLock,需要大量Lock对象)。
Q4: ConcurrentHashMap能完全替代Hashtable吗?
功能上可以。ConcurrentHashMap在性能、内存、并发度上全面优于Hashtable。Hashtable的每个方法都加synchronized(全表锁),性能极差。但如果需要"强一致性"遍历(如遍历时锁定整个表),ConcurrentHashMap不提供这种语义。
Q5: size()方法返回的是精确值吗?
不是精确值。由于counterCell分散计数,sumCount()时可能存在并发修改,结果可能不完全准确。这是一个"最终一致性"的设计:性能优先于精确性。
1. 画出JDK 8 ConcurrentHashMap的putVal完整流程图,标注CAS和synchronized的使用位置。
2. 解释sizeCtl在不同阶段的各种值及其含义(初始化前、初始化中、正常运行中、扩容中)。
3. 为什么get操作可以完全无锁?volatile修饰了哪些字段?
4. 描述transfer扩容时多线程协助迁移的机制:线程如何领取任务、如何标记已完成、put操作如何感知扩容。
5. 比较ConcurrentHashMap的counterCell计数和LongAdder的Cell计数,有什么异同?