高并发读写场景下的无锁哈希结构设计

一、从一道面试题说起

“请手写一个哈希结构的写入方法。”

这通常是考察候选人对哈希表底层实现理解程度的第一问。数组加链表的基本结构、哈希扰动函数的写法、桶下标计算、扩容条件判断——这些内容如果平时读过源码，回答起来并不困难。真正的分水岭出现在后续追问：如果要求这个结构支持高并发，并且读多写少、QPS 过万，你会如何改造？

这个问题表面上在问并发容器，实际上考察的是对锁竞争、内存可见性、数据一致性三者之间权衡的系统性思考。本文尝试把这条追问链条完整展开，给出一条从有锁到无锁、从整体拷贝到局部更新的设计演进路径。

二、第一层：并发改造的常规思路

2.1 直接加锁为什么不行

最朴素的做法是给整个哈希结构加一把互斥锁。写操作持锁修改，读操作持锁读取。这种方案在并发量低时可用，但当 QPS 过万、且读操作占绝大多数时，所有读请求都要竞争同一把锁，吞吐量会急剧下降。锁的获取与释放本身有开销，线程阻塞与唤醒更会带来上下文切换成本，读多写少的场景下这种开销被放大得尤为明显。

2.2 读写分离锁

第一层优化是引入读写锁：读锁之间不互斥，多个读线程可以并行进入；写锁与读锁、写锁与写锁之间互斥。这比全局互斥锁好了不少，但在极高并发下仍有两个问题：一是读锁的获取本身仍是一次原子操作，大量读线程争抢同一缓存行会导致明显的缓存一致性流量；二是写操作发生时会阻塞所有读操作，如果写操作本身耗时较长（例如涉及扩容或链表遍历），读请求的尾延迟会显著上升。

2.3 允许短时脏读的妥协

如果业务上允许读操作在极短时间内读到旧数据，设计空间会立刻变大。此时可以让读操作完全不加锁，写操作在修改数据时先操作一份副本，修改完成后通过一次原子写把引用切换到新副本。读线程要么读到旧引用，要么读到新引用，不会看到中间状态。这就是写时复制（Copy-on-Write）的核心思想。

Copy-on-Write 的优势在于读操作零锁开销，读性能极高；代价是每次写操作都要复制一份数据，内存占用和写延迟都会增加。因此它天然适合读多写少、数据量可控的场景。

三、第二层：无锁更新的关键机制

3.1 用 CAS 替代互斥锁

即使采用写时复制，切换引用这一步如果用互斥锁保护，写操作之间仍然会互相阻塞。更好的做法是使用比较并交换（CAS）指令：写线程先读取当前引用，基于它构造新副本，然后用 CAS 尝试把引用从旧值替换为新值。如果 CAS 失败，说明期间有其他写线程完成了更新，当前线程重新读取最新引用并重试。

CAS 的好处是没有线程阻塞，失败方自旋重试，避免了上下文切换。代价是高竞争下自旋会浪费 CPU，因此通常需要配合退避策略或限制重试次数。

3.2 快照与引用切换的语义

这里需要厘清一个容易混淆的概念：写时复制中那份“副本”，在工程语境下常被称作快照，但它与业务意义上的快照并不完全相同。业务快照通常强调某一时刻数据的完整、一致视图；而这里的副本只是写线程私有的中间状态，尚未发布给读线程。真正对外可见的“视图切换”发生在 CAS 成功的那一刻。理解这一点，有助于在设计时明确：读线程能看到的数据一致性边界在哪里。

四、第三层：拷贝成本的分治

4.1 整体拷贝的瓶颈

写时复制最大的问题是拷贝成本与数据规模成正比。如果哈希结构里存了十万条数据，每次写操作都复制整份数据，写延迟和内存分配压力都无法接受。即便数据量不大，链表的逐节点复制也远比数组复制昂贵。

4.2 分段拷贝

自然的优化思路是分段：把整个结构划分为若干独立段，每段维护自己的引用。写操作只复制被修改的那一段，CAS 也只更新该段的引用。这样拷贝成本从 O(总数据量) 降到 O(段大小)，且不同段的写操作可以完全并行，互不干扰。

分段带来一个新问题：如何划分段边界。按哈希桶范围划分是最直接的方式，段内可以继续沿用数组加链表的结构。读操作需要先定位段，再在段内查找，多了一层间接寻址，但读路径依然无锁。

4.3 链表中间节点更新的难题

分段解决了数组层面的拷贝粒度问题，但链表层面的问题依然存在。假设要更新链表中部的某个节点，能否只复制该节点及其后续节点，而不是整条链表？

这里要考虑几个现实约束。第一，链表节点通常存储的是键值对的引用，节点本身很小，复制单节点的成本并不高；第二，链表在哈希结构中通常很短，很多实现还会在链表长度超过阈值时转为树结构，进一步压缩查找深度；第三，如果要实现“只复制部分链表”，就需要处理前驱节点的指针更新问题——前驱节点也必须被复制，否则会破坏旧链表的完整性，而旧链表可能仍被读线程持有。

一种可行的设计是：写线程从链表头开始遍历，找到目标位置后，复制从目标节点到链表尾的部分，再复制目标节点的前驱，把前驱的 next 指向新复制的子链。这样旧链表中目标节点之前的节点保持不变，读线程即使持有旧头节点，也能安全地读到旧数据。这个过程的实现复杂度较高，需要非常小心地处理并发读下的内存可见性与节点回收问题——旧节点何时可以安全释放，通常需要借助引用计数或垃圾回收机制。

五、设计取舍的总结

把这条演进路径串起来，可以看到几个关键决策点：

• 一致性要求：是否允许短时脏读，决定了能否采用写时复制。
• 锁的粒度：从全局锁到读写锁，再到 CAS 无锁，核心是减少阻塞与竞争。
• 拷贝粒度：从整体拷贝到分段拷贝，再到链表局部拷贝，核心是控制写操作的放大成本。
• 读路径复杂度：每一层优化都要保证读操作仍然高效且无锁，否则读多写少的优势就丧失了。

回到面试场景，这类问题的价值不在于是否有唯一正确答案，而在于候选人能否在追问下逐步暴露自己的思考过程：能否识别瓶颈、能否提出方案、能否在方案被质疑时继续细化。手写哈希方法只是入场券，真正的考察从“改造并发版本”才刚刚开始。平时多问自己几个“如果这样不行，还能怎样”，比背诵某个并发容器的源码更有助于应对这类开放式设计问题。