ConcurrentHashMap 深度剖析：put 流程、size 统计与扩容

// 常量：默认初始容量 16，负载因子 0.75，并发级别 16，最大段数 1 << 16
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
final Segment<K,V>[] segments;

static class Segment<K,V> extends ReentrantLock {
    transient volatile HashEntry<K,V>[] table; // 本段桶数组
    transient int count;    // 本段元素个数（size 统计用）
    transient int modCount; // 本段修改次数（一致性校验用）
    transient int threshold; // 本段扩容阈值 = 容量 × 0.75
}

static class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;          // volatile 保证读可见性
    volatile HashEntry<K,V> next; // volatile 且用 putOrderedObject 安全发布
}

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    // ① tryLock 成功直接往下走；失败则 scanAndLockForPut：
    //    在锁外先定位桶、顺带构造好新节点，自旋 retries 次后 lock() 阻塞等待
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                if (key 已存在) { 覆盖 value; break; }
                e = e.next;
            } else {
                // ② 头插法：新节点插到链表头部
                node.setNext(first);
                if (++count > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);        // ③ 本段独立扩容（2 倍）
                else
                    setEntryAt(tab, index, node);
                break;
            }
        }
    } finally { unlock(); }
    return oldValue;
}

// 普通链表节点：注意字段名是 val，不是 value（与 HashMap 不同）
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // 经 spread() 处理后的散列值
    final K key;       // key 不可变 → 读不用锁
    volatile V val;   // volatile 保证读可见性
    volatile Node<K,V> next;
}

// 红黑树桶的根包装：hash 固定为 TREEBIN(-2)
static final class TreeBin<K,V> extends Node<K,V> {
    volatile TreeNode<K,V> root;  // 树根
    volatile TreeNode<K,V> first; // 链表头（保留链表便于遍历）
    volatile Thread waiter;
    volatile int lockState;        // 0 空闲 / WRITER=1 / WAITER=2 / READER=4（按位叠加）
}

// 扩容占位节点：hash 固定为 MOVED(-1)，指向新数组
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable;
}

// computeIfAbsent 的临时占位节点：hash 固定为 RESERVED(-3)
static final class ReservationNode<K,V> extends Node<K,V> {}

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS; // 高 16 位参与散列，并保证结果非负
}

// ① 按 volatile 语义读数组元素 —— get 无锁的基石
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：空桶插入、初始化置位、transferIndex 分配全靠它
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);
}

// ③ 释放写（lazy set）：写链表/替换桶头后安全发布
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putOrderedVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ① CHM 不允许 null key/value（HashMap 允许，这是二者的一个重要差异）
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());   // ② 高低 16 位混合，保证非负
    int binCount = 0;                  // 记录桶内节点数，用于树化判断
    for (Node<K,V>[] tab = table;;) {   // ③ 自旋：CAS 失败 / 帮助扩容后重试
        Node<K,V> f; int n, i, fh;
        // ④ table 未初始化 → initTable()（sizeCtl CAS 置 -1）
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // ⑤ 桶头为 null：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（hash == MOVED）→ 帮别人扩容，然后重试
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
                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;      // ⑩ 覆盖已有 key
                                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;   // ⑪ 尾插法追加（1.7 是头插，1.8 改尾插）
                            }
                        }
                    }
                    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) {
                // ⑬ 链表节点数 ≥ 8 → treeifyBin（数组 < 64 则先扩容）
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null) return oldVal; // 覆盖返回旧值
                break;
            }
        }
    }
        addCount(1L, binCount);   // ⑭ 计数 +1，并顺带检查是否需要扩容
    return null;   // 新插入返回 null
}

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // ① 别人正在初始化：让出 CPU 自旋等待（不阻塞）
        if ((sc = sizeCtl) < 0)
            Thread.yield();
        // ② 抢初始化权：CAS 把 sizeCtl 从当前值改为 -1，成功者才干活
                else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    // ③ 初始容量：构造器传了就用，否则默认 16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    Node<K,V>[] nt = (Node<K,V>[]) new Node<?,?>[n];
                    table = tab = nt;
                    // ④ 阈值 = n - n/4 = 0.75n（等价于 容量 × 负载因子 0.75）
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;   // ⑤ 释放初始化权，同时写入阈值
            }
            break;
        }
    }
    return tab;
}

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // ① 数组长度 < 64：不树化，直接预扩容 2 倍（节点分散后冲突自然缓解）
                if ((n = tab.length) < MIN_TREEIFY_CAPACITY)   // 64
            tryPresize(n << 1);
        // ② 数组 ≥ 64 且桶头是普通链表（b.hash >= 0，排除已树化/迁移中）
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {               // 锁桶头，防止并发树化
                if (tabAt(tab, index) == b) {   // 二次校验
                    // ③ 把链表节点逐个转成 TreeNode，串成双向链表
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) { ... }
                    // ④ 用 TreeBin 包装树根，替换桶头（setTabAt 发布）
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

// @Contended 注解：把该对象填充到独立的 CPU 缓存行，避免伪共享（false sharing）
@sun.misc.Contended
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // ① 快速路径：无 cell 数组（低竞争）时直接 CAS baseCount
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        // ② 慢路径：按线程探针值选一个 cell，CAS 累加
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                        fullAddCount(x, uncontended);  // ③ cell 数组初始化/扩容/换 cell 重试，全在这
            return;
        }
        if (check <= 1) return;   // ④ 链表短（binCount ≤ 1）就不查扩容，省一次 sumCount
        s = sumCount();
    }
    // ⑤ check >= 0（put 场景）且 s >= sizeCtl → 进入扩容逻辑（下一站展开）
    if (check >= 0) { ... resizeStamp / transfer 分支 ... }
}

public int size() {
    long n = sumCount();   // 无锁遍历求和，不重试、不加锁
    return (n < 0L) ? 0 : (n > (Integer.MAX_VALUE)) ? Integer.MAX_VALUE : (int)n;
}

public long mappingCount() {   // 推荐用这个：long 精度，避免 int 溢出截断
    long n = sumCount();
    return (n < 0L) ? 0L : n;
}

// ① 无锁遍历两遍：若两次 modCount 总和一致 → 返回（快路径）
// ② 不一致 → tryLock 所有 Segment 再数一遍
// ③ 还不一致 → 全部加锁（lock()）重数，然后解锁
// 结论：1.7 的 size() 可能阻塞整表，1.8 的 size() 永远不阻塞——但都不保证精确

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // ① 每个线程认领的桶数：多核时 = 容量/8/核数，最少 16 个
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)  // 16
        stride = MIN_TRANSFER_STRIDE;
    // ② 发起者创建 2 倍长的新数组，并初始化 transferIndex = n
    if (nextTab == null) {
        Node<K,V>[] nt = (Node<K,V>[]) new Node<?,?>[n << 1];  // 2 倍
        nextTable = nextTab = nt;
        transferIndex = n;   // 待分配区间 [0, n)
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); // 迁移完成桶的占位
    ...

while (advance) {
    int nextIndex, nextBound;
    if (--i >= bound || finishing)      // 本片还没干完
        advance = false;
    else if ((nextIndex = transferIndex) <= 0) {  // 没有剩余区间了
        i = -1; advance = false;
    }
        else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
                             nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
        bound = nextBound;     // 认领成功：本片 [bound, nextIndex)
        i = nextIndex - 1;
        advance = false;
    }
}

// 只针对普通链表桶（fh >= 0），synchronized(f) 锁桶头后：
int runBit = fh & n;              // 桶头 hash 的第 n 位
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
    int b = p.hash & n;
    if (b != runBit) { runBit = b; lastRun = p; }  // 找最后一个分界点
}
// lastRun 优化：lastRun 及其之后的节点位相同，整段复用，不用逐个 new
Node<K,V> ln = (runBit == 0) ? lastRun : null;   // 低位链（留在 i）
Node<K,V> hn = (runBit == 0) ? null : lastRun;   // 高位链（去 i+n）
for (Node<K,V> p = f; p != lastRun; p = p.next) {
    int ph = p.hash; K pk = p.key; V pv = p.val;
    if ((ph & n) == 0)  ln = new Node<K,V>(ph, pk, pv, ln);  // 头插组装低位链
    else                  hn = new Node<K,V>(ph, pk, pv, hn);  // 头插组装高位链
}
setTabAt(nextTab, i, ln);        // 低位链 → 新表 i
setTabAt(nextTab, i + n, hn);    // 高位链 → 新表 i+n
setTabAt(tab, i, fwd);           // 旧表桶位换成 ForwardingNode（占位 + 指路）
advance = true;

if (i < 0 || i >= n || i + n >= nextn) {   // 自己认领的区间干完了
    int sc;
    if (finishing) {                          // ③ 扫尾确认全表迁移完
        nextTable = null;
        table = nextTab;                     // 正式切换主数组引用
        sizeCtl = (n << 1) - (n >>> 1);      // 新阈值 = 1.5n = 0.75 × 2n
        return;
    }
    // ① 退出前 CAS sizeCtl - 1（自己不再是活跃迁移线程）
    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        // ② 若减完后不等于 (rs << 16) + 1，说明还有别的线程在干，直接走人
        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
            return;
        finishing = advance = true;   // 自己是最后一个 → 再扫一遍全表
        i = n;
    }
}

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    // ① 三重校验：确实是 FWD、nextTable 已建好、table 还是旧的
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);   // 由旧表长度算出本次扩容的 stamp
        while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
            // ② 以下情况不参与：stamp 不匹配（扩容已换代）/ 只剩最后线程 / 满员 / 没有剩余区间
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            // ③ CAS sizeCtl + 1 记账，然后真正进 transfer 干活
                        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

static final int resizeStamp(int n) {
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); // 高位置 1
}

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) {   // ① volatile 读桶头
        if ((eh = e.hash) == h) {   // ② 头节点直接命中（快速路径）
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // ③ hash < 0：FWD(扩容转发) / TreeBin(树查) / Reservation(占位，返回 null)
                else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // ④ 普通链表：顺着 volatile next 遍历
        while ((e = e.next) != null) {
            if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

final V replaceNode(Object key, V value, Object cv) {
    // 与 putVal 同构：定位 → MOVED 则 helpTransfer → 否则 synchronized(f) 锁桶头
    for (Node<K,V>[] tab = table;;) {
        // 桶空 / 桶头为 null → 直接 break（不存在）
        if (tab == null || ... || (f = tabAt(tab, i = (n - 1) & hash)) == null) break;
        else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {   // 链表：摘除节点
                        for (Node<K,V> e = f, pred = null;;) {
                            if (命中 key) {
                                if (pred == null) setTabAt(tab, i, e.next); // 删桶头
                                else pred.next = e.next;                    // 摘中间节点
                                break;
                            }
                            pred = e; if ((e = e.next) == null) break;
                        }
                    }
                    else if (f instanceof TreeBin) {   // 树：删除并可能退化
                        if (t.removeTreeNode(p))
                            setTabAt(tab, i, untreeify(t.first));  // 树过小 → 还原链表
                    }
                }
            }
            if (validated) {
                if (oldVal != null) {
                    if (value == null)
                        addCount(-1L, -1);   // 计数 -1，check=-1 跳过扩容检查
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

// ① 场景变了：1.7 锁粒度是 Segment，竞争相对激烈，需要 tryLock 无阻塞尝试 +
//    scanAndLockForPut 自旋，这是 ReentrantLock 的强项（lock() 可中断/可超时）
// ② 1.8 锁粒度细到桶，临界区极短、竞争极低：synchronized 的偏向/轻量级锁
//    在低竞争下就是一次 CAS 或几条指令，性能不输 ReentrantLock
// ③ synchronized 是 JVM 内建：锁消除、锁粗化等优化开箱即用；代码也更简洁
// ④ 结论不是「synchronized 比 ReentrantLock 强」，而是「桶级低竞争下 synchronized 够用且更省」

// HashMap 允许 null key/value，CHM 不允许 —— 老代码直接换容器会莫名 NPE
map.put(null, "x");   // HashMap OK；CHM → NullPointerException
// 排查：查 putVal 第一行 if (key == null || value == null) throw new NullPointerException();

// ① 递归：mappingFunction 里再对同一个 key 调 computeIfAbsent → IllegalStateException("Recursive update")
map.computeIfAbsent(key, k -> map.computeIfAbsent(k, ...));  // 递归更新，直接抛异常

// ② 重活：mappingFunction 内部做 RPC/DB 查询（耗时 100ms）→ 持有桶锁，同桶线程全部阻塞
map.computeIfAbsent(userId, k -> userService.query(k));  // 桶锁被占 100ms，吞吐骤降
// 正确姿势：先 get 快速路径；mappingFunction 只做轻量构造；重活放锁外再 putIfAbsent
V v = map.get(key);
if (v == null) { v = expensiveLoad(key); map.putIfAbsent(key, v); }