在前面的文章中，我们讨论了无锁读写锁、单线程对象池以及支持并发的无锁对象池。今天，我们将挑战一个更为复杂的数据结构——无锁哈希表 (AtomicHashMap)。

哈希表是系统中极其常用的组件，但在高并发场景下，传统的 std::map 或 std::unordered_map 配合 std::mutex 往往会成为性能瓶颈。本文将带你解析一个基于**链表法（Separate Chaining）**实现的原子哈希表，看看它是如何通过 CAS 操作在保证线程安全的同时，实现极极致的读取性能。

一、为什么选择无锁？性能差异在哪里？

传统加锁方案

在传统的哈希表实现中，为了保证线程安全，我们通常会使用 std::mutex 或 std::shared_mutex。

• 锁的粒度：最简单的做法是一把大锁保护整个 Map，这意味着所有线程的读写都是串行的。稍好的做法是分段锁（Striped Locking），比如 Java 的 ConcurrentHashMap，锁住单个 Bucket。
• 开销：加锁最大的问题在于上下文切换和线程阻塞。当一个线程持有锁时，其他竞争线程会被挂起（Sleep），等待唤醒。这个过程涉及用户态与内核态的切换，开销巨大。

无锁方案 (Lock-Free)

无锁哈希表利用 CPU 提供的原子指令（如 CAS - Compare And Swap）来管理数据的并发修改。

• 非阻塞：线程不会因为竞争失败而挂起，它们会不断重试（Spinning/Looping），直到操作成功。
• 读操作 Wait-Free：这是无锁哈希表最大的优势。读操作通常只需要原子加载内存（load），不需要此时有任何写入者配合，也不会被写入者阻塞。对于读多写少的场景，性能提升是数量级的。

二、核心结构设计

我们的 AtomicHashMap 采用了 固定桶数组 + 有序单向链表 的结构。

整体架构

template <typename K, typename V, ...>
class AtomicHashMap {
private:
    Bucket table_[TableSize]; // 固定大小的 Bucket 数组
    uint64_t capacity_mask_;  // 用于快速计算索引的掩码
};

1. 固定 Bucket：为了简化扩容带来的极其复杂的并发问题，本实现选择了固定大小的 Bucket 数组。
2. 位运算定位：限制 TableSize 为 2 的幂，利用 key & (TableSize - 1) 来替代昂贵的取模运算 %，极大加速定位速度。

节点与桶 (Entry & Bucket)

这是数据存储的核心。每个 Bucket 维护一个链表。

struct Entry {
    K key = 0;
    std::atomic<V*> value_ptr{nullptr}; // Value 指针，方便原子替换
    std::atomic<Entry*> next{nullptr};  // 链表指针，方便原子插入
    // ...
};

class Bucket {
    Entry* head_; // 哨兵头节点 (Dummy Head)
    // ...
};

• Dummy Head：每个桶都有一个虚拟头节点，这消除了“插入第一个节点”时的特殊判断逻辑，统一了链表操作。
• 有序链表：链表中的节点按 key 升序排列。这是一个很重要的优化：
  • 如果我们要找 key=5，当我们遍历到 key=7 时，就可以立即断定 5 不存在，无需遍历完整个链表。

三、并发冲突与解决 (结合代码)

无锁编程最难的地方在于处理竞争。在这个哈希表中，竞争主要发生在两个地方：

1. 更新 Value：多个线程同时修改同一个 Key。
2. 插入 Node：多个线程同时在其个位置插入新节点。

场景一：无锁插入 (Insert)

当我们需要插入一个新的 Key 时，首先要找到它的前驱节点 (prev) 和 后继节点 (target)。

// 伪代码逻辑
while (true) { // CAS 循环重试
    if (Find(key, &prev, &target)) {
        // key 已存在，进入更新逻辑...
    } else {
        // key 不存在，准备插入 new_entry
        new_entry->next.store(target, std::memory_order_release);
        
        // 【关键点】原子地将 prev->next 从 target 修改为 new_entry
        if (prev->next.compare_exchange_strong(target, new_entry, ...)) {
            return; // 插入成功
        }
        // CAS 失败？说明有别的线程在 prev 后面插入了东西，或者删除了 target。
        // 重新循环，再次 Find，重新定位 prev 和 target。
    }
}

这里利用了 compare_exchange_strong。只有当 prev->next 依然指向我们之前看到的 target 时，才将其修改为 new_entry。这一步保证了链表结构的完整性。

场景二：无锁更新 (Update)

如果 Find 发现 key 已经存在，我们则通过原子替换 value_ptr 来更新值。

auto old_val_ptr = target->value_ptr.load(std::memory_order_acquire);
// 【关键点】原子地将 value_ptr 从 old_val_ptr 替换为 new_value
if (target->value_ptr.compare_exchange_strong(old_val_ptr, new_value, ...)) {
    delete old_val_ptr; // 释放旧值（注：有坑，后文详述）
    return;
}

这实现了对 Value 的原子快照更新。

四、读写不对称性：为什么读永远也不卡？

读操作 (Wait-Free)

bool Get(K key, V **value) {
    Entry *prev = nullptr;
    Entry *target = nullptr;
    // Find 本质上就是遍历链表
    if (Find(key, &prev, &target)) {
        *value = target->value_ptr.load(std::memory_order_acquire);
        return true;
    }
    return false;
}

注意看，读操作中没有任何锁，也没有任何循环重试（Find 内部只是遍历，不会回退）。

• 即使写线程正在插入节点：读线程要么看到新节点（插入已完成），要么看不到（插入未完成，prev->next 还没变）。无论哪种，链表结构都是合法的，读线程都能安全遍历。
• 即使写线程正在更新 Value：读线程通过原子 load，要么拿到旧指针，要么拿到新指针，不会读到半个指针或乱码。

这就是 Wait-Free（无等待） 级别的读取性能：读线程的执行时间只取决于链表长度，完全不受写线程干扰。

隐患：内存安全 (The SMR Problem)

细心的读者可能注意到了代码中的一行注释：

delete old_val_ptr; // 注意：极高并发下若缺少 SMR，此处直接 delete 存在风险

这其实是该实现的一个妥协。在极度高并发的场景下，可能会发生这种情况：

1. 读线程 A 获取了 old_val_ptr，准备读取里面的数据。
2. 线程 A 被系统挂起（Context Switch）。
3. 写线程 B 进来了，执行 CAS 成功，把 value_ptr 换成了 new_value，并 delete old_val_ptr。
4. 读线程 A 醒来，试图访问 *old_val_ptr —— 崩溃 (Use-After-Free)。

在工业级通用的无锁容器（如 Java 的 ConcurrentHashMap 或 Folly 的 AtomicHashMap）中，会使用 SMR (Safe Memory Reclamation) 技术（如 Hazard Pointers 或 Epoch Based Reclamation）来解决这个问题：即“只有确认没有读线程在引用该内存时，才真正释放它”。

但在特定场景下（如 Cyber RT 的某些特定模块），如果能保证读取和删除之间的时序，或者能够容忍极低概率的这种 Race，为了追求极致的代码简洁和性能，这种“裸奔”的无锁实现也是存在的。

总结

AtomicHashMap 通过以下手段实现了极高的并发性能：

1. 分桶设计：减少热点冲突。
2. 原子链表操作：利用 CAS 管理链表结构，消除互斥锁。
3. 读写分离：读操作完全无锁且无等待（Wait-Free），写操作无锁但需重试（Lock-Free）。

这种数据结构非常适合 “读多写少” 且 “对延迟极度敏感” 的实时系统（如自动驾驶中间件）。