ConcurrentHashMap 线程安全实现
1. JDK 1.7 vs 1.8 的演进首先咱们吃水不忘打井人来看一下历程维度JDK 1.7JDK 1.8数据结构Segment 数组 HashEntry 数组 链表Node 数组 链表 红黑树锁机制分段锁ReentrantLockCAS synchronized锁桶头节点锁粒度锁一段默认 16 段锁单个桶粒度更细并发度最多 16 个线程同时写理论上限 数组长度这信息量还是很大的之前也写过2. JDK 1.8 线程安全的四大支柱支柱一volatile 保证可见性Node 节点的val和next也是 volatile 的。这意味着一个线程写入后其他线程立刻能看到最新值读操作完全无锁。transient volatile NodeK,V[] table; // 哈希桶数组volatile 保证扩容后对所有线程可见 transient volatile NodeK,V[] nextTable; // 扩容期间的新数组非扩容时为 null transient volatile int sizeCtl; // 核心控制字段下面详解 transient volatile int transferIndex; // 扩容时记录迁移进度 transient volatile long baseCount; // 基础计数值sizeCtl是一个多态字段不同值代表不同含义sizeCtl 的值含义-1正在初始化其他线程自旋等待-(1N)有 N 个线程正在扩容正数下次扩容的阈值容量 × 0.750未初始化使用默认容量这个字段用一个 int 同时表达了初始化状态 扩容线程数 扩容阈值三重语义是 Doug Lea 的经典设计。支柱二CAS 实现无锁插入当目标桶是空的不需要加锁直接用 CAS 原子操作插入final V putVal(K key, V value, boolean onlyIfAbsent) { // ① 禁止 null key 和 null value if (key null || value null) throw new NullPointerException(); // ② 二次哈希扰动函数和 HashMap 一样 int hash spread(key.hashCode()); int binCount 0; // ③ 外层无限循环CAS 自旋 for (NodeK,V[] tab table;;) { NodeK,V f; int n, i, fh; // 情况1数组还没初始化CAS 初始化 if (tab null || (n tab.length) 0) tab initTable(); // 内部用 CAS 保证只有一个线程能初始化 // 情况2目标桶是空的CAS 直接插入无锁 else if ((f tabAt(tab, i (n - 1) hash)) null) { if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; // CAS 成功跳出循环 // CAS 失败说明有别的线程抢先了继续循环重试 } // 情况3桶头节点是 ForwardingNodehash MOVED -1 // 说明正在扩容当前线程加入扩容大军 else if ((fh f.hash) MOVED) tab helpTransfer(tab, f); // 情况4桶不为空发生冲突 → 加锁 else { V oldVal null; synchronized (f) { // 锁住桶的头节点 if (tabAt(tab, i) f) { // 双重检查确保桶没被换过 if (fh 0) { // 普通链表 binCount 1; for (NodeK,V e f;; binCount) { if (e.hash hash (e.key key || key.equals(e.key))) { oldVal e.val; if (!onlyIfAbsent) e.val value; // 覆盖旧值 break; } NodeK,V pred e; if ((e e.next) null) { pred.next new NodeK,V(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 红黑树 NodeK,V p; binCount 2; if ((p ((TreeBinK,V)f).putTreeVal(hash, key, value)) ! null) { oldVal p.val; if (!onlyIfAbsent) p.val value; } } } } // 链表长度 8尝试树化 if (binCount ! 0) { if (binCount TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! null) return oldVal; break; } } } // ⑤ 更新计数可能触发扩容 addCount(1L, binCount); return null; }支柱三synchronized 锁桶头节点当桶不为空发生冲突只锁住这个桶的头节点else { synchronized (f) { // f 是桶的头节点 if (tabAt(tab, i) f) { // 双重检查 if (fh 0) { // 链表操作遍历、插入 } else if (f instanceof TreeBin) { // 红黑树操作 } } } }这意味着不同桶的写操作互不阻塞只有操作同一个桶的线程才会竞争同一把锁。支柱四多线程协同扩容ConcurrentHashMap扩容不是单线程搬数据而是所有正在操作的线程一起帮忙搬else if ((fh f.hash) MOVED) // 发现桶里放的是 ForwardingNode迁移标记说明正在扩容 tab helpTransfer(tab, f); // 当前线程加入扩容大军当某个线程触发扩容时会在每个桶的头节点放一个ForwardingNodehash 值为 MOVED。其他线程插入时发现这个标记就知道“正在搬家”于是放下手中的活协助搬运数据。搬完后再回来继续插入。3. 为什么 key 和 value 不能为 null在单线程的 HashMap 中get(key)返回 null 可以区分“值为 null”和“key 不存在”用containsKey验证。但在并发环境下containsKey和get之间可能被其他线程插入或删除导致判断失效。为了消除二义性ConcurrentHashMap 直接禁止 null。4. size() 为什么是“估算值”JDK 1.8 用baseCount CounterCell[]分散计数类似 LongAdder 的思想。高并发下多个线程同时 CAS 更新 baseCount失败的就更新 CounterCell 数组中的某个槽位减少竞争。所以size()返回的是一个弱一致性的近似值在并发场景下足够用。核心总结知识点关键结论HashMap 定位(n-1) hash数组长度必须是 2 的幂扩容触发元素数 容量 × 0.75扩容迁移(hash oldCap) 0留原位否则移到原位 oldCap树化条件链表 ≥ 8且数组 ≥ 64退化条件红黑树节点 ≤ 6CHM 读操作完全无锁volatile 保证可见性CHM 写操作空桶 CAS冲突桶 synchronized 锁头节点CHM 扩容多线程协同ForwardingNode 标记迁移状态
