Java8 ConcurrentHashMap 底层数据结构与核心方法流程

3. 定位桶位置

• 根据 (n - 1) & hash 计算数组下标 i。
• 获取该位置的节点 f。

4. 插入逻辑 (核心分支)

这里分为三种情况：

• 情况 A：桶为空 (f == null)
  • 使用 CAS 尝试将新节点插入到该位置。
  • 如果 CAS 成功，直接结束。
  • 如果 CAS 失败（说明有其他线程竞争），进入自旋重试。
• 情况 B：正在扩容 (f.hash == MOVED)
  • 说明当前桶的节点是 ForwardingNode。
  • 调用 helpTransfer()，当前线程会 协助扩容，将旧数组的数据迁移到新数组 nextTable 中。
• 情况 C：桶不为空且未扩容 (哈希冲突)
  • 使用 synchronized (f) 锁定该桶的头节点。
  • 再次检查 头节点是否变化（双重检查）。
  • 链表插入: 遍历链表。
    • 如果找到相同 key，根据 onlyIfAbsent 决定是否覆盖 value。
    • 如果没找到，尾插法插入新节点。
    • 插入后检查链表长度，如果 >= 8，调用 treeifyBin 尝试转为红黑树（需数组长度 >= 64，否则先扩容）。
  • 红黑树插入: 如果 f 是 TreeBin 类型，调用 putTreeVal 插入树节点。
  • 解锁。

5. 计数与扩容检查

• 调用 addCount(1L, binCount) 更新元素个数。
• 检查是否达到扩容阈值，如果达到，触发 transfer() 进行扩容（容量翻倍）。

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key 和 value 不能为空
    if (key == null || value == null)
        throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        // f = 目标位置元素
        Node<K,V> f;
        int n, i, fh; // fh 后面存放目标位置的元素 hash 值
        if (tab == null || (n = tab.length) == 0)
            // 数组桶为空，初始化数组桶（自旋+CAS)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
            // no lock when adding to empty bin
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用 synchronized 加锁加入节点
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 说明是链表
                    if (fh >= 0) {
                        binCount = 1;
                        // 循环加入新的或者覆盖节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                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, null);
                                break;
                            }
                        }
                    } else if (f instanceof TreeBin) {
                        // 红黑树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

三、get() 方法执行流程

get 操作是 无锁 的，这是 CHM 高性能的关键之一。

1. 计算 Hash 与定位

• 计算 key 的 hash 值。
• 定位数组下标 i = (n - 1) & hash。
• 获取该位置的第一个节点 tab[i]。

2. 遍历查找

• 匹配头节点: 如果头节点的 hash 和 key 匹配，直接返回 value。
• 链表遍历: 如果不匹配且 next 不为 null，遍历链表查找。
• 红黑树查找: 如果节点类型是 TreeBin，调用 find 方法在红黑树中查找。
• 扩容处理: 如果节点是 ForwardingNode，说明正在扩容，需要在 nextTable (新数组) 中继续查找。

3. 返回结果

• 找到则返回 value，找不到返回 null。
• 注意: 整个过程中没有使用任何锁，依靠 volatile 保证读取到最新的数据。

public V get(Object key) {
    Node<K,V>[] tab;
    Node<K,V> e, p;
    int n, eh;
    K ek;
    // key 所在的 hash 位置
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果指定位置元素存在，头结点 hash 值相同
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // key hash 值相等，key 值相同，直接返回元素 value
                return e.val;
        } else if (eh < 0) // 头结点 hash 值小于 0，说明正在扩容或者是红黑树，find 查找
            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;
}

四、size() 方法执行流程

Java 8 中 size() 的返回类型是 int，但底层统计逻辑基于 long。它不是 O(1) 的操作，而是一个估算值（在并发修改时）。

1. 计数机制 (LongAdder 思想)

为了减少高并发下对单一计数变量的竞争，CHM 采用了类似 LongAdder 的机制：

• baseCount: 基础计数值。
• CounterCell[]: 一个数组，当并发竞争激烈时，线程会将计数累加到不同的 CounterCell 单元格中，最后求和。

2. 执行流程 (sumCount())

1. 读取 baseCount。
2. 遍历 counterCells 数组，累加所有非空单元格的值。
3. 总和 = baseCount + counterCells 之和。

3. 返回值

• size() 方法内部调用 sumCount()，如果结果超过 Integer.MAX_VALUE 则返回最大值，否则强转为 int。
• 注意: 由于并发修改，size() 返回的值可能不是强一致性的（即调用瞬间的真实大小），但在大多数场景下足够准确。如果需要强一致性大小，需要加锁统计，但性能会大幅下降。

五、put 元素时如何更新计数？

put 操作通过 addCount 方法更新计数，涉及 baseCount 和 CounterCell 数组的原子操作，具体实现细节可参考官方源码文档。

六、核心优化点总结 (面试加分项)

1. 锁粒度优化: 从 Java 7 的 Segment 分段锁（锁整个段）变为 Java 8 的 桶级别锁 (synchronized)。JVM 对 synchronized 做了大量优化（偏向锁、轻量级锁），在低冲突下性能极高。
2. CAS 无锁插入: 如果桶为空，直接 CAS 插入，无需加锁。
3. 红黑树优化: 当哈希冲突严重时，链表转为红黑树，查找时间复杂度从 O(n) 降为 O(log n)。
4. 协同扩容: 扩容时，多个线程可以一起帮助迁移数据 (helpTransfer)，加快了扩容速度，避免了单线程迁移导致的停顿。
5. 读写分离: get 操作完全无锁，put 操作仅在冲突时加锁，极大提高了读多写少场景的性能。