跳表必须用多级指针而非单链表堆叠，因各层需共享同一节点数据并独立维护next指针数组；插入须从底层向上CAS确保原子性；删除需延迟回收防use-after-free；内存操作必须配合适当fence保证顺序与可见性。
跳表的结构设计为什么必须用多级指针而非单链表
跳表不是简单堆叠几层链表，核心在于每层节点必须共享同一份数据（比如 value），但各自维护独立的 next 指针数组。如果为每层分配独立节点，插入/删除时无法原子更新所有层级，极易导致遍历断裂或内存泄漏。正确做法是定义一个节点结构体，包含 std::vector<:atomic>> next</:atomic>，其中 next[i] 指向第 i 层的后继——这样所有层级操作都围绕同一个 Node* 实例展开。
常见错误是把跳表写成“多个平行链表”，结果并发插入时某一层更新了，另一层没跟上，find() 在高层跳过目标后，在低层又找不到它。这本质上破坏了跳表的层级一致性约束。
- 层级数上限建议设为固定值（如 32），避免运行时动态扩容带来的竞争；
-
next数组大小在构造时确定，不 resize，所有std::atomic<node></node>初始化为nullptr； - 节点内存必须用
new分配（不能栈分配），且由跳表统一管理生命周期，否则并发 delete 可能踩内存。
如何用 CAS 实现无锁插入而不破坏层级链路
插入关键在于「先找位置、再逐层链接、最后更新指针」三步必须原子化。不能先改高层再改低层——中间若被其他线程打断，会出现某层已连上新节点，另一层还指向旧位置，导致后续查找漏掉该节点。
标准做法是：从最高层开始向下遍历，记录每层「待插入位置前驱节点」到数组 update[i] 中；然后从第 0 层（底层）向上逐层执行 compare_exchange_weak，只有当前层成功链接后，才继续上一层。任一层失败就重试整个插入流程。
立即学习“C++免费学习笔记（深入）”；
- 必须从低层往高层 CAS，否则高层先连上，低层还没连，别的线程可能通过高层跳过未完成插入的节点；
-
update[i]必须是原子读取的快照，不能边遍历边修改，否则并发遍历时看到脏数据； - CAS 失败不等于失败，要重新
find()获取最新前驱，而不是直接 return——这是最常被忽略的重试逻辑。
删除操作为何比插入更难处理内存释放
删除时不仅要断开所有层级的指针，还要确保没有其他线程正通过某一层访问该节点。直接 delete node 极易引发 use-after-free：A 线程刚 CAS 断开第 2 层指针，B 线程正在第 2 层遍历，此时 A delete，B 就访问了野指针。
必须引入延迟回收机制，典型方案是 Hazard Pointer 或 epoch-based reclamation（如 libcds 的 gc::HP）。C++20 前没有标准方案，硬实现的话，至少要做到：所有读操作（find、contains）进入临界区前标记自己正在引用哪些节点，删除线程等待所有标记清空后再 delete。
- 不要在 CAS 断链后立刻
delete，哪怕只有一层没断完也不行； - 即使用了
std::shared_ptr，也不能解决跨层引用问题——因为跳表遍历不经过智能指针，而是裸指针跳转； - 测试时加
std::this_thread::yield()在 CAS 失败后，否则高争用下容易饿死。
std::atomic_thread_fence 的位置决定是否真的线程安全
很多人以为只要所有指针都用 std::atomic<node></node> 就万事大吉，其实不然。x86 上 store() 默认带 acquire-release 语义，但 ARM/AArch64 不保证；更重要的是，节点字段（如 value）初始化和指针发布之间需要 fence 防止指令重排。
典型错误是在 new 节点后直接写 next[0].store(new_node)，而 value 字段可能还没写完就被其他线程读到未初始化值。正确顺序是：先初始化所有字段，再执行 std::atomic_thread_fence(std::memory_order_release)，最后发布指针。
-
find()中每次读next[i]后，必须紧跟std::atomic_thread_fence(std::memory_order_acquire)才能安全读该节点的value； - 不同 CPU 架构对 memory_order 的实际效果差异极大，别依赖 x86 的宽松模型去写跨平台代码；
- 用
clang++ -fsanitize=thread跑压力测试，比手动 review 更早暴露 fence 缺失问题。
并发跳表最难的不是写对逻辑，而是让每个内存操作的顺序和可见性都落在正确语义上。稍有偏差，bug 只在高负载下偶发，复现成本极高。
