当前位置：首页 > article >正文

画出ConcurrentHashMap 1.8的put流程图，记住CAS和synchronized的结合

article 2025/3/22 2:50:04

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，结束。