ConcurrentHashMap 1.8 put 操作流程
结构：数组 + 链表/红黑树。
并发控制：CAS（无锁操作） + synchronized（锁住桶头部节点）。
改进：相比1.7的分段锁（Segment），1.8锁粒度更细，仅锁住单个桶。
流程图（文字描述）
START
↓
输入 key 和 value
↓
计算 hash 值：hash = spread(key.hashCode()) // 高低位异或，减少冲突
↓
获取数组长度 n = tab.length，计算索引 i = (n - 1) & hash
↓
获取桶位置 tab[i] 的头节点 f = tabAt(tab, i) // 通过Unsafe.getObjectVolatile获取
↓
[条件分支] f == null ?
是 → 使用 CAS 插入新节点
↓
casTabAt(tab, i, null, new Node(hash, key, value)) // CAS尝试将null替换为新节点
↓
[成功] → 结束
[失败] → 返回循环重试
否 → 检查 f 的状态
↓
[条件分支] f.hash == -1 ? // -1表示正在扩容或初始化
是 → 协助扩容：helpTransfer(tab, f)
否 → 进入同步逻辑
↓
synchronized (f) { // 锁住桶头节点
↓
再次检查 tab[i] == f // 确保锁住的节点未变
↓
[链表操作]
如果 f 是链表节点：
遍历链表，查找 key
↓
[存在] → 更新 value
[不存在] → 尾部插入新节点
↓
检查链表长度 >= 8 ? → treeifyBin() // 转红黑树
[红黑树操作]
如果 f 是红黑树节点：
putTreeVal() // 红黑树插入
↓
} // synchronized 结束
↓
更新 size：addCount(1L, binCount) // CAS更新元素计数，可能触发扩容
↓
END
流程图关键点说明
1.CAS 使用：
初始化桶：当桶为空（tab[i] == null），用 casTabAt（基于Unsafe的CAS操作）插入新节点，无锁高效。
更新size：addCount 用 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);
}
2.synchronized 使用：
当桶不为空，锁住头节点 f，确保同一桶的并发操作线程安全。
锁粒度细化：只锁当前桶，不影响其他桶。
示例代码：
synchronized (f) {
if (tabAt(tab, i) == f) {
// 链表或红黑树操作
}
}
3.CAS + synchronized 结合：
- CAS 用于无竞争场景（如空桶插入、计数更新），减少锁开销。
- synchronized 用于有竞争场景（如链表追加、红黑树操作），保证一致性。
- 这种组合避免了1.7的全段锁，提高并发性能。
完整put方法源码（精简版）
final V putVal(K key, V value, boolean onlyIfAbsent) {
int hash = spread(key.hashCode());
int binCount = 0;
Node<K,V>[] tab = table;
for (;;) {
int n = tab.length, i;
Node<K,V> f;
if (tab == null || n == 0)
tab = initTable(); // 初始化表
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // CAS插入成功
} else if (f.hash == -1) // 扩容中
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { // 锁住头节点
if (tabAt(tab, i) == f) {
if (f.hash >= 0) { // 链表
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
if (e.hash == hash && e.key.equals(key)) {
oldVal = e.val;
if (!onlyIfAbsent) e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
} else { // 红黑树
TreeNode<K,V> p = (TreeNode<K,V>)f;
oldVal = p.putTreeVal(this, tab, hash, key, value);
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i); // 转红黑树
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); // 更新计数
return null;
}
面试记录要点
1.流程简述：
计算hash -> 检查桶 -> CAS插入（空桶）或synchronized操作（非空桶） -> 更新size。
2.CAS作用：
空桶插入：casTabAt。
计数更新：addCount。
3.synchronized作用：
锁桶头节点，保证链表/红黑树操作安全。
4.性能优化：
CAS减少锁使用，synchronized细化锁粒度。
5.画图提示：
画一个数组，标注桶状态（空/链表/红黑树）。
用箭头表示CAS（空桶）和synchronized（链表操作）分支。
手绘流程图建议
- 顶层：输入key/value，计算hash。
- 分支1：tab[i] == null -> CAS插入 -> 结束。
- 分支2：tab[i] != null
- 子分支1：f.hash == -1 -> 协助扩容。 子分支2：f.hash >= 0 ->
- synchronized锁头节点 -> 链表/红黑树操作。 - 底部：更新size，结束。
口述练习：
“put 时先算 hash，桶为空用 CAS 插入；不为空用 synchronized 锁头节点，链表操作或转红黑树，最后 CAS 更新 size。”