ConcurrentHashMap ⭐⭐⭐

// ==================== 两级定位过程（概念图） ====================
// 
// 假设 key = "hello", hash(key) = 0x7A3B_F10E
//
// 第一级定位 Segment：用 hash 的 【高位】
//   segmentIndex = (hash >>> segmentShift) & segmentMask
//   例：segmentShift=28, segmentMask=15 → segmentIndex = 7
//   → 锁住 Segment[7]
//
// 第二级定位 HashEntry 桶：用 hash 的 【低位】
//   bucketIndex = hash & (table.length - 1)
//   例：table.length=4, → bucketIndex = hash & 3 = 2
//   → 在 Segment[7] 的 HashEntry[2] 链表上操作

// ==================== Segment 核心源码（JDK 7 简化版） ====================
 
// Segment 直接继承 ReentrantLock，自身就是一把可重入锁
static final class Segment<K,V> extends ReentrantLock implements Serializable {
 
    private static final long serialVersionUID = 2249069246763182397L;
 
    // 当前 Segment 下实际存储的 entry 数量
    transient volatile int count;
 
    // 结构修改次数，用于跨段一致性校验（如 size() 方法）
    transient int modCount;
 
    // 扩容阈值 = table.length * loadFactor（注意：每个 Segment 独立扩容）
    transient int threshold;
 
    // 哈希桶数组，每个元素是 HashEntry 链表的头节点
    // volatile 保证数组引用的可见性（扩容时替换新数组）
    transient volatile HashEntry<K,V>[] table;
 
    // 负载因子，继承自构造参数
    final float loadFactor;
 
    // ======== put 操作（必须先获取锁） ========
    final V put(K key, int hash, V value, boolean onlyIfAbsent) {
        // tryLock() 尝试非阻塞获取锁
        // 获取失败则进入 scanAndLockForPut 自旋 + 阻塞逻辑
        HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
        V oldValue;
        try {
            HashEntry<K,V>[] tab = table;            // 获取当前桶数组
            int index = (tab.length - 1) & hash;     // 用 hash 低位定位桶
            HashEntry<K,V> first = entryAt(tab, index); // 取出链表头节点
 
            for (HashEntry<K,V> e = first;;) {       // 遍历链表
                if (e != null) {
                    K k;
                    // 如果找到相同 key，更新 value
                    if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                        oldValue = e.value;
                        if (!onlyIfAbsent) {         // putIfAbsent 语义控制
                            e.value = value;
                            ++modCount;              // 记录修改次数
                        }
                        break;
                    }
                    e = e.next;                      // 继续遍历下一个节点
                } else {
                    // 链表中没有相同 key，头插法插入新节点
                    if (node != null)
                        node.setNext(first);         // 新节点的 next 指向原头节点
                    else
                        node = new HashEntry<K,V>(hash, key, value, first);
                    int c = count + 1;               // 计算新的 entry 数量
                    // 超过阈值且未达最大容量时，触发 Segment 内部扩容
                    if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                        rehash(node);                // 仅扩容当前 Segment！
                    else
                        setEntryAt(tab, index, node);// 将新节点设为桶的头节点
                    ++modCount;
                    count = c;                       // volatile 写，保证可见性
                    oldValue = null;
                    break;
                }
            }
        } finally {
            unlock();                                // 操作完成，释放锁
        }
        return oldValue;
    }
}

// ==================== scanAndLockForPut 源码（JDK 7 简化版） ====================
 
// 当 tryLock() 快速获取锁失败时，进入此方法
// 在自旋等待锁的过程中，预先遍历链表查找/创建节点，充分利用 CPU 时间
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    // 根据 hash 定位到桶的第一个节点
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;                      // 预创建的新节点
    int retries = -1;                                 // 重试计数器，-1 表示还在扫描链表阶段
 
    while (!tryLock()) {                              // 反复尝试获取锁
        HashEntry<K,V> f;
 
        if (retries < 0) {
            // === 扫描阶段：利用等待时间预处理 ===
            if (e == null) {
                // 链表遍历完毕，未找到相同 key → 预先创建新节点
                if (node == null)
                    node = new HashEntry<K,V>(hash, key, value, first);
                retries = 0;                          // 进入自旋计数阶段
            }
            else if (key.equals(e.key))
                retries = 0;                          // 找到相同 key，进入自旋计数
            else
                e = e.next;                           // 继续遍历链表
        }
        else if (++retries > MAX_SCAN_RETRIES) {
            // === 自旋超过最大次数（单核1次，多核64次） ===
            // 放弃自旋，进入阻塞队列排队等待
            lock();                                   // 阻塞式获取锁
            break;
        }
        else if ((retries & 1) == 0 &&
                 (f = entryForHash(this, hash)) != first) {
            // === 每隔一次自旋检查链表头是否变化 ===
            // 如果头节点变了（说明其他线程修改了链表），重新扫描
            e = first = f;
            retries = -1;                             // 回到扫描阶段
        }
    }
    return node;                                      // 返回预创建的节点（可能为 null）
}

// ==================== ConcurrentHashMap 构造函数（JDK 7 简化版） ====================
 
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    // 参数校验
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
 
    // concurrencyLevel 上限为 65536 (1 << 16)
    if (concurrencyLevel > MAX_SEGMENTS)
        concurrencyLevel = MAX_SEGMENTS;
 
    // ===== 计算 Segment 数量（必须是 2 的幂） =====
    int sshift = 0;            // segment 位移量，用于后续 hash 定位
    int ssize = 1;             // segment 数组的实际大小
    while (ssize < concurrencyLevel) {
        ++sshift;              // 每翻倍一次，位移量 +1
        ssize <<= 1;          // ssize 不断左移直到 >= concurrencyLevel
    }
    // 例：concurrencyLevel=16 → ssize=16, sshift=4
 
    this.segmentShift = 32 - sshift;   // 32-4=28，hash 右移 28 位取高 4 位
    this.segmentMask = ssize - 1;      // 16-1=15=0x0F，掩码
 
    // ===== 计算每个 Segment 内的初始桶数（也必须是 2 的幂） =====
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
 
    int c = initialCapacity / ssize;   // 将总容量均分到每个 Segment
    if (c * ssize < initialCapacity)
        ++c;                           // 向上取整
    int cap = MIN_SEGMENT_TABLE_CAPACITY; // 最小桶数为 2
    while (cap < c)
        cap <<= 1;                     // 找到 >= c 的最小 2 的幂
 
    // ===== 创建 Segment[0] 作为原型（Prototype） =====
    // 其他 Segment 在首次访问时懒加载，复用 s0 的参数
    Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor), 
                                        (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize]; // 创建 Segment 数组
    UNSAFE.putOrderedObject(ss, SBASE, s0);                  // 将 s0 放入 ss[0]
    this.segments = ss;
}

// ==================== ensureSegment：懒加载 Segment（JDK 7） ====================
 
private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE;           // 计算 segments[k] 的内存偏移量
    Segment<K,V> seg;
 
    // 第一次检查（无锁读取 volatile 语义）
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        // 以 Segment[0] 为原型，复用其参数
        Segment<K,V> proto = ss[0];
        int cap = proto.table.length;           // 复制桶数组容量
        float lf = proto.loadFactor;            // 复制负载因子
        int threshold = (int)(cap * lf);        // 计算扩容阈值
 
        // 创建新的 HashEntry 桶数组
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
 
        // 第二次检查（Double-Check，防止其他线程已经创建了）
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // 自旋 CAS 写入，保证只有一个线程成功
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
                if (UNSAFE.compareAndSwapObject(ss, u, null, s)) {
                    seg = s;                    // CAS 成功，返回新创建的 Segment
                    break;
                }
            }
        }
    }
    return seg;
}

// 三种常见构造方式
// 1. 默认构造：initialCapacity=16, loadFactor=0.75, concurrencyLevel=16
ConcurrentHashMap<String, Integer> map1 = new ConcurrentHashMap<>();
 
// 2. 指定初始容量：concurrencyLevel 仍为默认 16
ConcurrentHashMap<String, Integer> map2 = new ConcurrentHashMap<>(256);
 
// 3. 完整参数：指定并发度为 32
// 实际 Segment 数量 = 32（恰好是 2 的幂，无需向上取整）
ConcurrentHashMap<String, Integer> map3 = new ConcurrentHashMap<>(256, 0.75f, 32);
 
// 4. 如果 concurrencyLevel=20，实际 Segment 数量 = 32（向上取整到最近的 2 的幂）
ConcurrentHashMap<String, Integer> map4 = new ConcurrentHashMap<>(256, 0.75f, 20);

// ==================== size() 方法（JDK 7 简化） ====================
 
public int size() {
    final Segment<K,V>[] segments = this.segments;
    long sum = 0;            // 总元素数
    long last = 0;           // 上一轮的统计结果
    int retries = -1;        // 重试计数
    boolean overflow = false; // 是否溢出 int 范围
 
    try {
        for (;;) {
            // 如果连续两次无锁统计的结果一致 → 直接返回
            // 如果尝试 RETRIES_BEFORE_LOCK(=2) 次仍不一致 → 锁住所有 Segment
            if (retries++ == RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    ensureSegment(j).lock();           // 逐个获取所有 Segment 的锁！
            }
 
            sum = 0L;
            overflow = false;
            for (int j = 0; j < segments.length; ++j) {
                Segment<K,V> seg = segmentAt(segments, j);
                if (seg != null) {
                    sum += seg.count;                  // 累加每个 Segment 的 count
                    if (seg.count < 0)
                        overflow = true;
                }
            }
            // 如果 sum 等于上一轮的结果，说明期间没有修改，结果可信
            if (sum == last)
                break;
            last = sum;                                // 记录本轮结果，下一轮对比
        }
    } finally {
        if (retries > RETRIES_BEFORE_LOCK) {
            for (int j = 0; j < segments.length; ++j)
                segmentAt(segments, j).unlock();       // 释放所有锁
        }
    }
    return overflow ? Integer.MAX_VALUE : (int)sum;
}

// ========== 1. 基础节点：链表节点 ==========
// 类似 HashMap.Node，但 val 和 next 都用 volatile 修饰
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;       // 哈希值，一旦计算不可变
    final K key;          // 键，不可变
    volatile V val;       // 值，volatile 保证可见性（支持无锁读）
    volatile Node<K,V> next; // 下一个节点的引用，volatile 保证链表结构变更对读线程可见
 
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;  // 存储 spread() 处理后的 hash
        this.key = key;
        this.val = val;
        this.next = next;
    }
}
 
// ========== 2. 树节点：红黑树中的实际节点 ==========
// 继承自 Node，额外维护红黑树的父/左/右/前驱指针和颜色
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // 父节点（红黑树结构）
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 前驱节点（用于删除时拆链）
    boolean red;           // 红黑颜色标记
 
    TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) {
        super(hash, key, val, next); // 调用 Node 构造器
        this.parent = parent;
    }
}
 
// ========== 3. 树桶容器：桶的头节点，封装了一棵红黑树 ==========
// hash 固定为 TREEBIN（-2），持有读写锁以保护树结构
static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;    // 红黑树的根节点
    volatile TreeNode<K,V> first; // 链表顺序的第一个节点（TreeNode 同时维护链表结构）
    volatile Thread waiter; // 等待获取写锁的线程
    volatile int lockState; // 锁状态：0=无锁, 1=写锁, 2/4/6...=读锁计数
    // ... 省略读写锁逻辑和树操作方法
}
 
// ========== 4. 转发节点：扩容时的占位标记 ==========
// hash 固定为 MOVED（-1），持有新表引用
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable; // 指向扩容后的新数组
    ForwardingNode(Node<K,V>[] tab) {
        super(MOVED, null, null, null); // hash = -1 作为标识
        this.nextTable = tab;
    }
}

// ConcurrentHashMap 中的核心常量
static final int MOVED     = -1; // ForwardingNode 的 hash 标记，表示该桶已迁移
static final int TREEBIN   = -2; // TreeBin 的 hash 标记，表示该桶是红黑树
static final int RESERVED  = -3; // ReservationNode 的 hash 标记，用于 computeIfAbsent 等方法的占位
 
static final int TREEIFY_THRESHOLD = 8;   // 链表长度 >= 8 时触发树化判断
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树节点 <= 6 时退化为链表
static final int MIN_TREEIFY_CAPACITY = 64; // 只有 table 长度 >= 64 才真正树化，否则优先扩容

// table 引用本身是 volatile 的
transient volatile Node<K,V>[] table;
 
// Node 的 val 和 next 也是 volatile 的
volatile V val;
volatile Node<K,V> next;

// ConcurrentHashMap 中常用的 Unsafe 操作
 
// 获取 table[i] 处的 Node（volatile 语义读）
// 等价于：return table[i]，但绕过数组边界检查，直接按内存偏移量读取
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 设置 table[i] 的值：期望为 null，设为新 Node
// 仅当 table[i] 当前确实为 null 时才成功，返回 true
// 这是往空桶插入第一个节点的唯一方式
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);
}
 
// volatile 写 table[i]（不需要 CAS，用于已获取锁后的确定性写入）
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

// put 操作的核心并发控制片段（简化版）
Node<K,V> f = tabAt(tab, i);       // 读取桶头节点
if (f == null) {
    // 空桶：用 CAS 无锁插入
    if (casTabAt(tab, i, null, new Node<>(hash, key, value, null)))
        break;                      // CAS 成功，结束
    // CAS 失败说明有竞争，回到循环重试
} else if (f.hash == MOVED) {
    // 桶正在迁移：当前线程协助扩容（后续章节详解）
    tab = helpTransfer(tab, f);
} else {
    // 非空桶：synchronized 锁住头节点 f
    synchronized (f) {              // 锁的对象是桶的第一个 Node
        if (tabAt(tab, i) == f) {   // double-check：确认 f 仍然是头节点
            // ... 遍历链表或操作红黑树，执行插入/更新
        }
    }
}

// 时间线演示：为什么需要 double-check
// 假设线程 A 和线程 B 同时对桶 i 操作
 
// T1: 线程 A 读到 f = tabAt(tab, i)         => f 是 Node X
// T2: 线程 B 也读到 f = tabAt(tab, i)       => f 也是 Node X
// T3: 线程 A 先获得 synchronized(f)，执行完操作后释放锁
//     操作中 A 可能因为扩容导致 tab[i] 指向了新的头节点 Y
// T4: 线程 B 获得 synchronized(f)
//     但此时 tab[i] 已经不是 f（Node X）了！
//     如果不 double-check，B 会在一个"过时的"链表上操作，导致数据丢失

// 内存视角：synchronized 锁的是什么？
//
// table:  [  桶0  |  桶1  |  桶2  |  桶3  | ... |  桶n  ]
//                     |
//                     v
//              +-- Node A (头节点) <--- synchronized 锁的就是这个对象
//              |    hash=33, key="x", val="1"
//              |    next ──> Node B
//              |              hash=65, key="y", val="2"
//              |              next ──> null
//              |
//              +--- 整条链表在 Node A 的锁保护下操作
 
// 线程 1 锁住桶 1 的头节点 A，对桶 1 的链表做插入
// 线程 2 可以同时 CAS 操作桶 0（空桶）—— 完全无阻塞
// 线程 3 可以同时 synchronized 锁住桶 3 的头节点 —— 与线程 1 互不干扰
// 只有线程 4 也要操作桶 1 时，才需要等待线程 1 释放锁

// 假设 100 个 put 操作的 hash 分布较为均匀
//
// JDK 7（16 Segments，每个 Segment 管 64 个桶）:
//   - 100 个线程竞争 16 把锁
//   - 平均每把锁有 ~6 个线程排队
//   - 如果 6 个线程恰好都落在不同的桶，它们本不该互相阻塞
//   - 但因为同一个 Segment 只有一把锁，仍然串行执行
//
// JDK 8（1024 个桶）:
//   - 100 个线程竞争 1024 个桶位
//   - 两个线程落在同一个桶的概率（生日问题）≈ 1 - e^(-100*99/(2*1024)) ≈ 99.2%
//   - 虽然几乎肯定有冲突，但冲突只影响那两个碰撞的线程
//   - 绝大多数线程（~90+）互不阻塞，接近真正的并行
//   - 而且如果目标桶为空，连 synchronized 都不需要，CAS 一步搞定

// ConcurrentHashMap.spread() —— 扰动函数
static final int spread(int h) {
    // h ^ (h >>> 16)：将高 16 位异或到低 16 位，让高位信息也影响索引
    // & HASH_BITS：HASH_BITS = 0x7fffffff，强制最高位为 0，保证结果为非负数
    return (h ^ (h >>> 16)) & HASH_BITS;
}

原始 hashCode:   1100 0011 0010 1010 | 0001 1100 0110 1001
                 ----高16位----       ----低16位----
 
h >>> 16:        0000 0000 0000 0000 | 1100 0011 0010 1010
 
XOR 结果:        1100 0011 0010 1010 | 1101 1111 0100 0011
                                       ↑ 高位信息混入低位
 
& 0x7fffffff:    0100 0011 0010 1010 | 1101 1111 0100 0011
                 ↑ 最高位归零，保证非负

// 定位桶的核心表达式（出现在 putVal 方法内）
// n 是 table 数组长度，必定为 2 的幂
// i 就是最终的桶索引
int i = (n - 1) & hash;
 
// 通过 Unsafe/VarHandle 读取桶头节点（volatile 语义）
Node<K,V> f = tabAt(tab, i);

假设 n = 16 (0001 0000)
n - 1 = 15  (0000 1111)
 
hash  = ...1010 1101 1111 0100 0011
n - 1 = ...0000 0000 0000 0000 1111
         ─────────────────────────
AND   = ...0000 0000 0000 0000 0011  → 索引 = 3

// tabAt —— 以 volatile 语义读取数组元素
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    // U 是 Unsafe 实例
    // ABASE 是 Node[] 数组首元素的内存偏移量
    // ASHIFT 是每个数组元素的偏移位移量
    return (Node<K,V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);
}

// putVal 方法中处理空桶的代码片段
if (f == null) {
    // 利用 CAS 尝试将新 Node 放入空桶
    // 期望值: null（桶为空）
    // 新值: 新创建的 Node
    if (casTabAt(tab, i, null,
                 new Node<K,V>(hash, key, value, null)))
        break;  // CAS 成功，跳出 for 循环，put 完成
    // CAS 失败说明有其他线程抢先写入，继续 for 循环重试
}

// casTabAt —— 对数组元素执行 CAS 操作
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                     Node<K,V> c, Node<K,V> v) {
    // compareAndSwapObject(对象, 偏移量, 期望值, 新值)
    // 如果 tab[i] 当前 == c，则原子地设为 v，返回 true
    // 否则不修改，返回 false
    return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
}

// putVal 方法中处理非空桶的核心代码
else {
    V oldVal = null;
    // 锁住桶头节点 f —— 只锁这一个桶，其他桶不受影响
    synchronized (f) {
        // 双重检查：确认 f 仍然是桶头节点
        // 防止在获取锁的过程中，该桶被其他线程修改（如扩容搬迁）
        if (tabAt(tab, i) == f) {
            // 正常链表节点（hash >= 0）
            if (fh >= 0) {
                // ... 链表遍历和插入逻辑（见下一节）
            }
            // 红黑树节点（TreeBin）
            else if (f instanceof TreeBin) {
                // ... 红黑树插入逻辑（见下一节）
            }
        }
    }
    // ... 后续处理
}

// 链表遍历 + 尾插法
if (fh >= 0) {                          // fh 是头节点的 hash 值，>= 0 说明是普通链表节点
    binCount = 1;                        // binCount 记录链表长度，从 1 开始（头节点算一个）
    for (Node<K,V> e = f; ; ++binCount) { // 从头节点开始遍历
        K ek;
        // 判断是否找到了相同的 key
        if (e.hash == hash &&            // 先比较 hash 值（快速过滤）
            ((ek = e.key) == key ||      // 再比较引用是否相同
             (ek != null && key.equals(ek)))) {  // 最后用 equals 比较内容
            oldVal = e.val;              // 记录旧值
            if (!onlyIfAbsent)           // 默认 put 是覆盖模式
                e.val = value;           // 直接更新 value（Node.val 是 volatile 的）
            break;                       // 找到了就退出循环
        }
        Node<K,V> pred = e;             // pred 保存当前节点（即下一次循环的"前驱"）
        if ((e = e.next) == null) {      // 移动到下一个节点
            // 到达链表尾部，说明 key 不存在，执行尾插
            pred.next = new Node<K,V>(hash, key, value, null);
            break;                       // 插入完成，退出循环
        }
    }
}

// 红黑树插入
else if (f instanceof TreeBin) {         // f 是 TreeBin 类型
    Node<K,V> p;
    binCount = 2;                        // 树节点的 binCount 设为 2（非 0 非 1 即可，后续不会触发树化）
    // 调用 TreeBin 的 putTreeVal 方法，在红黑树中查找或插入
    if ((p = ((TreeBin<K,V>) f).putTreeVal(hash, key, value)) != null) {
        oldVal = p.val;                  // 如果 key 已存在，p 指向已有节点
        if (!onlyIfAbsent)
            p.val = value;               // 覆盖旧值
    }
}

// synchronized 块之后的树化判断
if (binCount != 0) {
    // TREEIFY_THRESHOLD = 8
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);             // 尝试将链表转为红黑树
    if (oldVal != null)
        return oldVal;                   // 如果是更新操作，返回旧值
    break;                               // 如果是新插入，跳出 for 循环
}

// treeifyBin 的简化逻辑
private final void treeifyBin(Node<K,V>[] tab, int index) {
    if (tab != null) {
        int n = tab.length;
        // MIN_TREEIFY_CAPACITY = 64
        if (n < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);          // 表太小，先扩容而不是树化
        else {
            // 真正执行链表 → 红黑树的转换
            // ... 将所有 Node 转为 TreeNode，构建红黑树，用 TreeBin 包装
        }
    }
}

// putVal 方法末尾
addCount(1L, binCount);  // 元素数 +1，同时传入 binCount 用于判断是否需要扩容检查
return null;              // 新插入返回 null

// addCount 方法中的扩容触发逻辑（简化）
private final void addCount(long x, int check) {
    // ---- 第一部分: 更新计数（baseCount + CounterCell，此处省略） ----
 
    // ---- 第二部分: 检查是否需要扩容 ----
    if (check >= 0) {                    // check 即 binCount，>= 0 时需要检查扩容
        Node<K,V>[] tab, nt;
        int n, sc;
        // s 是当前元素总数
        // sizeCtl（sc）在非扩容状态下存储的是扩容阈值（threshold = capacity * loadFactor）
        while (s >= (long)(sc = sizeCtl)  // 元素数 >= 阈值
               && (tab = table) != null
               && (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);      // 根据当前容量 n 生成一个扩容标识戳
            if (sc < 0) {
                // sc < 0 说明已经有线程在扩容
                // 判断是否可以加入帮助扩容
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs  // 标识戳不匹配
                    || sc == rs + 1                     // 扩容已完成
                    || sc == rs + MAX_RESIZERS           // 帮助线程数已达上限
                    || (nt = nextTable) == null          // nextTable 已清空
                    || transferIndex <= 0)               // 所有桶已分配完
                    break;                               // 不需要帮助，退出
                // CAS 将 sc + 1，表示又多了一个线程参与扩容
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);                   // 帮助搬迁数据
            }
            else {
                // 当前没有线程在扩容，由本线程发起扩容
                // CAS 将 sizeCtl 设为负值（高 16 位=rs，低 16 位=参与线程数+1）
                if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);                 // 发起扩容，nextTable 由 transfer 内部创建
            }
            s = sumCount();              // 重新统计元素数，继续循环检查
        }
    }
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // Step 0: 空值检查 —— ConcurrentHashMap 不允许 null key/value
    if (key == null || value == null) throw new NullPointerException();
 
    // Step 1: 计算扰动 hash
    int hash = spread(key.hashCode());
    int binCount = 0;                    // 记录桶内节点数（用于树化判断）
 
    // Step 2: 自旋（死循环），直到操作成功
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
 
        // Step 3: 如果 table 未初始化，先初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();           // 内部使用 CAS + sizeCtl 控制只有一个线程执行初始化
 
        // Step 4: 定位桶，如果桶为空，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;                   // 成功就结束
 
        // Step 5: 如果桶头是 ForwardingNode（hash == MOVED），协助扩容
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);  // 搬完后拿到新 table，继续循环
 
        // Step 6: 非空桶，synchronized 插入
        else {
            V oldVal = null;
            synchronized (f) {           // 锁住桶头节点
                if (tabAt(tab, i) == f) { // 双重检查
                    if (fh >= 0) {       // 链表
                        // ... 遍历链表，尾插或更新
                    } else if (f instanceof TreeBin) { // 红黑树
                        // ... putTreeVal 插入或更新
                    }
                }
            }
            // Step 7: 链表过长则树化
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
 
    // Step 8: 元素计数 +1，必要时触发扩容
    addCount(1L, binCount);
    return null;
}

// ConcurrentHashMap 的核心节点定义（JDK 8 源码简化）
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;       // hash 值，final 修饰，创建后不可变
    final K key;          // 键，final 修饰，创建后不可变
    volatile V val;       // 值，volatile 修饰，保证可见性
    volatile Node<K,V> next; // 下一个节点指针，volatile 修饰，保证可见性
}

// table 数组也是 volatile 的
transient volatile Node<K,V>[] table;

public V get(Object key) {
    Node<K,V>[] tab;  // 局部变量：引用 table 数组
    Node<K,V> e, p;   // e: 桶的头节点, p: 遍历过程中的当前节点
    int n, eh;         // n: 数组长度, eh: 头节点的 hash 值
    K ek;              // ek: 遍历节点的 key
 
    // ① 调用 spread() 方法计算 hash（高16位异或低16位，再与 HASH_BITS 按位与）
    //    目的：让 hash 分布更均匀，减少碰撞
    int h = spread(key.hashCode());
 
    // ② 判断 table 不为空 且 长度大于 0 且 目标桶的头节点不为空
    //    tabAt(tab, (n - 1) & h) 使用 Unsafe.getObjectVolatile() 读取
    //    保证每次都从主内存读取最新的头节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
 
        // ③ 先检查头节点：hash 相等 且 key 相等（引用相等 或 equals 相等）
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;  // 头节点就是目标，直接返回 val
        }
        // ④ 头节点 hash < 0，说明是特殊节点（红黑树 或 ForwardingNode）
        //    委托给节点自身的 find() 方法去查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
 
        // ⑤ 普通链表：从头节点的 next 开始逐个遍历
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;  // 找到匹配节点，返回 val
        }
    }
    // ⑥ 未找到，返回 null
    return null;
}

static final int HASH_BITS = 0x7fffffff; // 最高位置 0，保证 hash 非负
 
static final int spread(int h) {
    // 将原始 hashCode 的高 16 位与低 16 位异或
    // 再与 HASH_BITS 按位与，确保结果为正数
    // 负数 hash 在 ConcurrentHashMap 中有特殊含义（见下文）
    return (h ^ (h >>> 16)) & HASH_BITS;
}

hash 值含义：
┌──────────────────────────────────────────────┐
│  hash >= 0        → 普通 Node（链表节点）      │
│  hash == -1       → ForwardingNode（扩容标记） │
│  hash == -2       → TreeBin（红黑树的根代理）   │
│  hash == -3       → ReservationNode（占位节点） │
└──────────────────────────────────────────────┘

// 使用 Unsafe 提供的 volatile 语义读取数组指定位置的元素
// 即使 tab 本身是 volatile 的，数组元素的读取仍需要额外保证
// 因为 Java 中 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);
}

volatile Node<K,V>[] table;
 
// volatile 只保证 table 引用本身的可见性
// 即：线程 A 把 table 指向新数组后，线程 B 能立即看到新数组
// 但 table[i] 这个元素的读写并不带 volatile 语义！
 
// 所以必须通过 Unsafe.getObjectVolatile 来保证
// 读取 table[i] 时也能看到最新值

// ForwardingNode 在扩容时被放置在旧数组的已迁移桶位上
// 它内部持有对新数组 nextTable 的引用
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable; // 指向扩容后的新数组
 
    Node<K,V> find(int h, Object k) {
        // 循环是为了处理「新数组中的桶又是 ForwardingNode」的极端情况
        outer: for (Node<K,V>[] tab = nextTable;;) {
            Node<K,V> e; int n;
            // 在新数组中重新定位桶位
            if (tab == null || (n = tab.length) == 0 ||
                (e = tabAt(tab, (n - 1) & h)) == null)
                return null;              // 新数组中该桶为空，返回 null
            for (;;) {
                int eh; K ek;
                // 标准的 key 匹配逻辑
                if ((eh = e.hash) == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;             // 找到了，返回节点
                if (eh < 0) {
                    // 如果新数组中该桶又是 ForwardingNode（再次扩容）
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        continue outer;   // 跳到更新的数组继续查找
                    }
                    else
                        return e.find(h, k); // TreeBin 等其他特殊节点
                }
                // 遍历链表
                if ((e = e.next) == null)
                    return null;
            }
        }
    }
}

// TreeBin 是红黑树的代理节点，hash 固定为 -2 (TREEBIN)
// 它内部使用读写锁（基于 CAS 的轻量级锁）来协调读写
final Node<K,V> find(int h, Object k) {
    if (k != null) {
        // 从链表形态的 first 开始遍历（TreeBin 同时维护了链表结构）
        for (Node<K,V> e = first; e != null; ) {
            int s; K ek;
            // lockState 的第 2、3 位表示有写线程持锁或等待
            // 此时退化为遍历链表（避免和写线程在树结构上产生竞争）
            if (((s = lockState) & (WAITER|WRITER)) != 0) {
                // 有写操作正在进行，使用链表遍历（安全但稍慢）
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                e = e.next;  // 沿链表方向继续
            }
            // 没有写线程，CAS 增加读计数，然后走红黑树查找（O(logN)）
            else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                          s + READER)) {
                TreeNode<K,V> r, p;
                try {
                    // 从红黑树根节点开始查找
                    p = ((r = root) == null ? null :
                         r.findTreeNode(h, k, null));
                } finally {
                    Thread w;
                    // CAS 减少读计数，如果是最后一个读者且有等待的写者，唤醒它
                    if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                        (READER|WAITER) && (w = waiter) != null)
                        LockSupport.unpark(w);
                }
                return p;
            }
        }
    }
    return null;
}

时间线 →
Thread-A (get):  读取 tabAt(tab, i) ──→ 得到 null ──→ 返回 null
Thread-B (put):  ──→ CAS 将 Node 写入 tab[i] ──→ 成功
                      ↑
          A 读在 B 写之前：返回 null（正确，此时确实没有值）
          A 读在 B 写之后：volatile 保证看到新 Node，正常匹配

时间线 →
Thread-A (get):  读取头节点 e ──→ 沿 e.next 遍历链表 ──→ 返回
Thread-B (put):  synchronized(头节点) { 在链尾追加新 Node }
 
关键点：next 是 volatile 的
- 如果 A 遍历到尾节点时，B 已经追加完成 → A 能看到新 next
- 如果 A 遍历到尾节点时，B 还没追加 → A 看到 next=null，返回旧结果
两种情况都不会出错，只是存在「弱一致性」

时间线 →
Thread-A (get):  读取 tab[i] ──→ 发现是 ForwardingNode ──→ 去 nextTable 查找
Thread-B (transfer): 正在将 tab[i] 的节点迁移到 nextTable
 
关键点：ForwardingNode 是在节点迁移完成后才放置的
所以 A 看到 ForwardingNode 时，新表中的数据一定已经就位

// 线程 A
map.put("key", "value1");  // 时刻 T1
 
// 线程 B（几乎同时）
map.get("key");             // 可能返回 null 或 "value1"
// 取决于 volatile 写和读的精确时序
 
// 但绝不会返回「半写入」的脏数据！

// addCount 方法中的扩容判定（简化版）
// s 是当前元素总数
if (s >= (long)(sc = sizeCtl)) {
    // 元素数量已超过阈值，需要扩容
    transfer(tab, null); // 启动数据搬运
}

// sizeCtl 在扩容期间的位结构
// |<---- 高16位: resizeStamp ---->|<---- 低16位: 线程计数 ---->|
// |  标识本次扩容的唯一戳记        |  当前参与搬运的线程数 + 1    |

// helpTransfer 方法 —— 协助扩容的入口（简化版）
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; // 新数组的引用
    int sc;
 
    // 条件判断：确认确实在扩容中
    // f 是 ForwardingNode，且它内部持有 nextTable 引用
    if (tab != null 
        && (f instanceof ForwardingNode)
        && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
 
        // 根据旧表长度计算本次扩容的唯一标记戳
        int rs = resizeStamp(tab.length);
 
        // 循环尝试加入扩容
        while (nextTab == nextTable  // 新表还没变（扩容还没结束）
               && table == tab       // 旧表还没被替换
               && (sc = sizeCtl) < 0) { // sizeCtl < 0 表示扩容进行中
 
            // 校验标记戳是否匹配、线程数是否已达上限等
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs // 标记戳不匹配
                || sc == rs + 1                    // 所有线程已完成
                || sc == rs + MAX_RESIZERS         // 达到最大协助线程数
                || transferIndex <= 0) {           // 所有桶已分配完毕
                break; // 无需加入
            }
 
            // CAS 将 sizeCtl 加 1，表示多了一个线程参与扩容
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab); // 加入搬运！
                break;
            }
        }
        return nextTab; // 返回新数组
    }
    return table; // 未在扩容，返回当前表
}

// 步长计算（简化逻辑）
// NCPU 是处理器核心数，n 是旧表长度
int stride = (NCPU > 1) ? (n >>> 3) / NCPU : n; // 每个线程负责的桶数量
if (stride < MIN_TRANSFER_STRIDE) {
    stride = MIN_TRANSFER_STRIDE; // 最小步长 = 16
}

// 每个线程领取任务区间（在 transfer 方法内部）
// i 是当前处理的桶索引（从高到低），bound 是本次区间的下界
int nextIndex, nextBound;
if (--i >= bound || finishing) {
    // 当前区间还没处理完，继续
} else if ((nextIndex = transferIndex) <= 0) {
    // transferIndex <= 0，所有区间已被领完
    i = -1;
    advance = false;
} else if (U.compareAndSwapInt(this, TRANSFERINDEX,
                               nextIndex,
                               nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
    // CAS 成功，领取区间 [nextBound, nextIndex - 1]
    bound = nextBound;
    i = nextIndex - 1; // 从区间最右侧开始向左搬运
    advance = false;
}

// 核心判定：hash & n（n 是旧容量，且一定是 2 的幂）
// 如果结果为 0 → 留在低位
// 如果结果不为 0 → 搬到高位

假设旧容量 n = 16 (0b10000)
 
旧掩码 (n-1):     01111
新掩码 (2n-1):    11111
                   ^
                   这一位决定高低
 
hash = 0b10101 → hash & n = 10000 (!=0) → 高位: i + 16
hash = 0b00101 → hash & n = 00000 (==0) → 低位: i

// transfer 方法中链表搬运逻辑（简化但保留核心）
synchronized (f) { // f 是桶的头节点，对其加锁
    if (tabAt(tab, i) == f) { // double-check：确认头节点未被其他线程修改
 
        Node<K,V> ln, hn; // ln = lowNode 低位链, hn = highNode 高位链
        int runBit = fh & n; // fh 是头节点的 hash, n 是旧容量
        Node<K,V> lastRun = f; // lastRun: 尾部连续相同位的起始节点
 
        // ====== 第一次遍历：找到 lastRun ======
        // 目的：找到链表尾部一段连续的、都属于同一位（高/低）的子链
        // 这段子链可以直接复用，不需要逐个重建节点
        for (Node<K,V> p = f.next; p != null; p = p.next) {
            int b = p.hash & n; // 计算当前节点属于高位还是低位
            if (b != runBit) {  // 如果与前一个不同
                runBit = b;     // 更新 runBit
                lastRun = p;    // 更新 lastRun
            }
        }
 
        // 根据 lastRun 的最终归属，初始化高低位链的"尾巴"
        if (runBit == 0) {
            ln = lastRun; // lastRun 属于低位
            hn = null;
        } else {
            hn = lastRun; // lastRun 属于高位
            ln = null;
        }
 
        // ====== 第二次遍历：构建高低位两条链（到 lastRun 为止）======
        for (Node<K,V> p = f; p != lastRun; p = p.next) {
            int ph = p.hash;           // 当前节点的 hash
            K pk = p.key;              // 当前节点的 key
            V pv = p.val;              // 当前节点的 value
            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
 
        // ====== 在旧表对应位置放置 ForwardingNode ======
        setTabAt(tab, i, fwd);        // 标记该桶已搬运完毕
        advance = true;               // 推进到下一个桶
    }
}

旧表 bucket[5], n=16:
 
  [A] → [B] → [C] → [D] → [E] → [F] → null
   L      H      L      H      H      H
                              ↑ lastRun = D (从D开始都是H)
 
拆分结果:
 
低位链 (bucket[5]):    [C'] → [A'] → null
                       (头插法，所以顺序反转)
 
高位链 (bucket[21]):   [B'] → [D] → [E] → [F] → null
                       (新建)  (---- lastRun 复用 ----)
 
L = low (hash & n == 0)
H = high (hash & n != 0)

// 红黑树搬运逻辑（简化）
else if (f instanceof TreeBin) {
    TreeBin<K,V> t = (TreeBin<K,V>)f;
    TreeNode<K,V> lo = null, loTail = null; // 低位树节点链
    TreeNode<K,V> hi = null, hiTail = null; // 高位树节点链
    int lc = 0, hc = 0; // 低位计数、高位计数
 
    // 遍历 TreeNode 的链表结构（TreeNode 同时维护了链表指针）
    for (Node<K,V> e = t.first; e != null; e = e.next) {
        int h = e.hash;           // 当前节点 hash
        TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);
        if ((h & n) == 0) {       // 低位
            if ((p.prev = loTail) == null)
                lo = p;           // 第一个低位节点
            else
                loTail.next = p;  // 尾插法
            loTail = p;
            ++lc;                 // 低位计数+1
        } else {                  // 高位
            if ((p.prev = hiTail) == null)
                hi = p;
            else
                hiTail.next = p;
            hiTail = p;
            ++hc;                 // 高位计数+1
        }
    }
 
    // 判断拆分后是否需要退化为链表（节点数 <= UNTREEIFY_THRESHOLD = 6）
    ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : // 退化为普通链表
         (hc != 0) ? new TreeBin<K,V>(lo) :            // 重新构建红黑树
         t;                                              // 所有节点都在低位，复用原树
 
    hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
         (lc != 0) ? new TreeBin<K,V>(hi) :
         t;
 
    setTabAt(nextTab, i, ln);     // 低位放入新表
    setTabAt(nextTab, i + n, hn); // 高位放入新表
    setTabAt(tab, i, fwd);        // 旧表标记 ForwardingNode
    advance = true;
}

// ForwardingNode 的定义（JDK 源码简化）
static final class ForwardingNode<K,V> extends Node<K,V> {
    final Node<K,V>[] nextTable; // 指向新数组的引用
 
    ForwardingNode(Node<K,V>[] tab) {
        // hash = MOVED (-1), key = null, val = null, next = null
        super(MOVED, null, null, null);
        this.nextTable = tab; // 持有新表的引用
    }
 
    // 重写 find 方法：在新表中查找
    Node<K,V> find(int h, Object k) {
        // 转发到新表进行查找（支持递归，处理多次扩容的情况）
        outer: for (Node<K,V>[] tab = nextTable;;) {
            Node<K,V> e; int n;
            if (k == null || tab == null || 
                (n = tab.length) == 0 ||
                (e = tabAt(tab, (n - 1) & h)) == null)
                return null; // 未找到
            for (;;) {
                int eh; K ek;
                if ((eh = e.hash) == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e; // 在新表中找到
                if (eh < 0) {
                    if (e instanceof ForwardingNode) {
                        // 新表也在扩容！递归跳转到更新的表
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        continue outer;
                    } else
                        return e.find(h, k); // TreeBin 等特殊节点
                }
                if ((e = e.next) == null)
                    return null;
            }
        }
    }
}

// transfer 方法末尾的收尾逻辑（简化）
if (finishing) {
    // 最后一个线程负责收尾
    nextTable = null;        // 清空 nextTable 引用
    table = nextTab;         // 用新表替换旧表（volatile 写，对所有线程可见）
    sizeCtl = (n << 1) - (n >>> 1); // 新阈值 = 2n * 0.75 = 1.5n
    return;
}
 
// 非最后一个线程：CAS 递减 sizeCtl 中的线程计数
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
    // 检查是否是最后一个完成的线程
    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
        return; // 不是最后一个，直接返回
    // 是最后一个！设置 finishing = true，再循环一次做最终检查
    finishing = advance = true;
    i = n; // 重新扫描一遍，确保所有桶都已是 ForwardingNode
}