robin hood哈希表无法简单无锁化，因其探测距离维护、前向位移和墓碑传播依赖多步协同更新，易被抢占破坏一致性；必须重设计为原子打包桶结构（哈希+距离+状态合一）并用cas循环实现插入。
Robin Hood哈希表为什么不能简单“无锁化”
直接在原有 Robin Hood 哈希表（比如 robin_hood::unordered_map）上加 std::atomic 或用 std::shared_mutex，不是真正无锁（lock-free）。真正的无锁要求所有线程在任意时刻都能取得进展，而 Robin Hood 的核心操作——探测距离（probe distance）维护、前向位移（forward shift）、删除时的墓碑（tombstone）传播——都依赖多步内存状态协同更新。一旦中间被抢占，就会破坏探测链的语义一致性。
所以，不是“怎么把现有实现改成无锁”，而是“必须重设计数据结构和原子原语组合方式”。关键约束有三个：load/store 不能保证顺序一致性；compare_exchange_weak 是唯一能安全重试的原子操作；探测距离必须与键值对原子绑定，不能分离存储。
核心结构：每个桶必须是 std::atomic<uint64_t></uint64_t> 打包的键哈希+距离+有效位
传统 Robin Hood 把键、值、探测距离、状态（empty/deleted/occupied）分开放，这在并发下无法原子更新。正确做法是把它们压缩进一个 64 位整数（假设 64 位平台）：
- 低 1 位：有效位（0=empty，1=occupied；deleted 用特殊哈希值标记，如全 1）
- 接下来 7 位：探测距离（最大 127，足够覆盖常见负载因子
0.9下的分布） - 高 56 位：哈希值（截断后仍保留足够区分度）
值（value）单独存于并行数组中，索引与桶一一对应。这样每次插入/查找只需一次 atomic_load 获取哈希+距离+状态，再用该索引访问值数组——避免了读-改-写竞争。
注意：不能用 std::atomic<:pair t>></:pair>，因为 T 可能非 trivially copyable，且无法保证 128 位原子性（x86-64 不支持原生 128 位 CAS）。
插入逻辑必须用循环 CAS + 探测距离驱动前移
标准 Robin Hood 插入会比较当前桶和待插入项的探测距离，决定是否“抢位”。并发下这个判断必须和写入原子绑定，否则两个线程同时看到同一桶可插入，就会冲突。
实操要点：
- 从哈希位置开始线性探测，对每个桶执行
atomic_load得到当前状态 - 若为空（有效位=0），尝试用
compare_exchange_weak写入新打包值；失败则重试（可能被其他线程抢先） - 若为 occupied 且其探测距离
- 若为 occupied 且其探测距离 ≥ 待插入项距离，则尝试“挤入”：先 CAS 写入自己，再用另一个 CAS 把原值“推”到下一位置——但必须确保推的时候下一位置没被别人占用，否则要回滚整个链
这个“推”操作是难点：实际需用双字 CAS（double-word CAS）或借助 hazard pointer 避免 ABA 问题。多数工程实现会退化为：只允许插入到空桶或 tombstone，禁止运行时前移——牺牲一点空间利用率换取可实现性。
删除只能设 tombstone，且 tombstone 必须参与探测距离修正
无锁环境下不能真删，只能标记为 tombstone（例如哈希字段设为 0xffffffffffffffff）。但 Robin Hood 的探测链依赖距离连续性：如果中间有个 tombstone，后续查找必须知道“这里本该有东西，距离应比前一个+1”，否则会提前终止搜索。
所以查找逻辑必须识别 tombstone，并继续探测，同时累加逻辑距离；插入时遇到 tombstone，若其逻辑距离 ≤ 当前待插距离，就复用它——但复用前要 CAS 清除 tombstone 标记，且确保清除后没人正基于旧 tombstone 做距离计算（需配合版本号或 epoch-based reclamation）。
容易踩的坑：std::atomic_thread_fence 位置不对会导致编译器重排，让 tombstone 清除早于新值写入；GCC/Clang 对 __atomic_load_n 默认用 memory_order_seq_cst，性能差，应显式指定 memory_order_acquire。
真正可用的工业级实现极少，folly::AtomicUnorderedMap 放弃了 Robin Hood，改用带版本号的开放寻址；boost::lockfree::spsc_queue 类思路不适用哈希表场景。除非你控制全部使用模式（如单生产者多消费者、固定 key 集合），否则建议优先考虑带细粒度锁的 absl::flat_hash_map 或 tsl::robin_map。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
