并发哈希表：分段锁、桶锁、协作扩容与分裂有序表
内容提要
本文梳理并发哈希表的核心难题：锁粒度与扩容搬迁。并发表仅保证单操作原子，get后put仍会丢更新，应改用merge等原子方法。对比JDK7分段锁、JDK8桶锁加协作扩容、分裂有序表不搬元素、NonBlockingHashMap及Go sync.Map等实现，并给出桶长分布、扩容复制比例约六分之一等实测数据。
延伸解读
并发哈希表不等于操作序列线程安全
文章通过实验表明，ConcurrentHashMap 只保证单个操作原子，get 后 put 这类复合操作仍会丢失更新。两个线程各加 100 万次，用 get 加 put 写，5 次运行丢掉了 58 万到 90 万次更新；换成 merge 则一次不丢。因此，需要复合逻辑时应使用 merge、compute、putIfAbsent 等原子方法，而不是先查后写。
扩容是并发哈希表的核心难题
文章指出，锁粒度细化早已实现，真正的难点在于扩容时元素搬迁。一次 CAS 只能改一个字，无法原子地移动链表节点，因此需要复制或协作。JDK 8 采用 ForwardingNode 和 transferIndex 让多线程分段协作，实测扩容时约 16.6% 的节点被复制，其余原样挂到新表，与源码注释的“约六分之一”一致。
分裂有序表用不搬元素换扩容无锁
分裂有序表通过反转哈希位序，使桶在链表中保持连续，扩容时只需插入哑节点，不移动任何元素。实测 2 线程每线程 20 万键压力测试通过，扩容移动节点数为 0。但代价是哑节点永不删除，表只增不减，且反转位序必不可少：不反转时每次查找越过的节点数从 0.78 涨到 4081，与键数成正比。
不同实现把代价放在不同位置
文章对比了多种并发哈希表：JDK 7 分段锁并发度固定，size() 可能锁全表；JDK 8 桶锁加协作扩容，但不缩容；NonBlockingHashMap 开放寻址、槽位状态机，依赖 GC 回收；Linux rhashtable 用 RCU 读和后台搬迁，可选缩容；Go 1.24 的 sync.Map 换成 HashTrieMap，覆盖已有键时每次分配 48 字节，旧实现仅 16 字节。选择时需权衡负载模式与内存开销。
Q&A
为什么用了 ConcurrentHashMap 还是可能丢数据？
ConcurrentHashMap 只保证单个操作（如 get、put）的原子性，但 get 后再 put 是两个操作，中间可能被其他线程修改。实验显示两个线程各用 get+put 自增 100 万次，5 次运行丢失了 58 万到 90 万次更新。应改用 merge、compute、putIfAbsent 等原子方法。
JDK 7 和 JDK 8 的 ConcurrentHashMap 在锁的实现上有什么主要区别？
JDK 7 使用分段锁（Segment），默认 16 个 Segment，每个 Segment 继承 ReentrantLock，锁粒度是 Segment；JDK 8 以后去掉了 Segment，锁的单位变成一个桶，空桶用 CAS 插入，非空桶锁住首节点，并发度更高。
JDK 8 的 ConcurrentHashMap 扩容时多个线程如何协作？
扩容时，线程通过 CAS 修改 transferIndex 来认领一段桶（步长 stride = max(16, (n/8)/NCPU)），每个线程负责一段，从高下标往低下标搬。搬完的桶放置 ForwardingNode，其他线程遇到 ForwardingNode 会帮忙搬迁。
分裂有序表扩容时为什么不需要搬移元素？
分裂有序表将所有元素放在一条按反转位序排序的无锁链表中，桶数组只存储指向链表中哑节点的指针。扩容时只需 CAS 更新表长，并按需插入新的哑节点来分割链表，元素本身不移动。
JDK 8 的 ConcurrentHashMap 在扩容时大约复制多少比例的节点？
根据源码注释和实验，扩容时大约有六分之一的节点需要复制。实验显示表从 2^18 翻倍到 2^19 时，复制比例在 16.54% 到 16.61% 之间，与理论推导的 16.61% 一致。
Go 1.24 的 sync.Map 实现有什么变化？
Go 1.24 将 sync.Map 的实现从原来的 read/dirty 双 map 换成了 HashTrieMap（哈希前缀树），每个内部节点有 16 个子指针，锁分布在树的节点上。覆盖已有键时新实现每次分配 48 字节，旧实现 16 字节；持续加新键时新实现分配次数更少。
