19、哈希表的线程安全：线程安全问题分析、互斥锁实现、读写锁优化、无锁哈希表简介

多线程环境下操作哈希表，说白了就是一场「谁先改、谁后读」的博弈。我早年做服务器中间件时，就吃过线程安全的亏——一个全局哈希表被多个工作线程同时读写，线上偶发崩溃，查了两天才定位到是并发插入导致链表成环。嗯，从那以后，我对哈希表的线程安全就格外上心。

19.1 线程安全问题分析

哈希表的线程安全问题，核心就三个字：竞态条件。多个线程同时读写同一块内存，结果不可预测。

具体来说，常见的问题场景有：

• 插入冲突：两个线程同时往同一个桶里插节点，可能导致链表断裂或节点丢失。
• 扩容重哈希：一个线程在扩容搬数据，另一个线程在读旧表，读到一半表结构变了，直接崩溃。
• 删除与遍历：一个线程删节点，另一个线程正在遍历链表，访问了已被释放的内存。
• 读-写交织：读线程看到的数据是「半写」状态，比如 key 已经更新但 value 还没写完。

你可能会问：「我读多写少，不加锁行不行？」我的建议是——别赌。我在项目中见过太多「理论上不会并发」但实际就撞上了的案例。线程安全不是概率问题，是确定性问题。

19.2 互斥锁实现

最简单的方案，就是给整个哈希表加一把大锁。C 语言里常用 pthread_mutex_t。

实现思路：

• 每个操作（插入、查找、删除）前后加锁解锁。
• 锁的粒度是「整个哈希表」。

#include <pthread.h>

typedef struct {
    HashTable *table;
    pthread_mutex_t lock;
} ThreadSafeHashTable;

void ts_insert(ThreadSafeHashTable *ht, int key, int value) {
    pthread_mutex_lock(&ht->lock);
    insert(ht->table, key, value);
    pthread_mutex_unlock(&ht->lock);
}

int ts_lookup(ThreadSafeHashTable *ht, int key) {
    pthread_mutex_lock(&ht->lock);
    int val = lookup(ht->table, key);
    pthread_mutex_unlock(&ht->lock);
    return val;
}

但缺点也很明显：性能瓶颈。读操作也要等锁，读多写少时浪费严重。

方案	优点	缺点
全局互斥锁	实现简单，正确性容易保证	并发性能差，读操作互相阻塞
读写锁	读读不互斥，性能更好	实现稍复杂，写锁仍可能饿死
无锁哈希表	极高并发，无锁竞争	实现极复杂，调试困难

19.3 读写锁优化

读操作不修改数据，多个线程同时读是安全的。互斥锁把读也堵死了，太浪费。读写锁（pthread_rwlock_t）就是来解决这个问题的。

核心规则：

• 多个线程可以同时获取读锁。
• 写锁是独占的，获取写锁时，所有读锁必须释放。
• 读锁和写锁互斥。

typedef struct {
    HashTable *table;
    pthread_rwlock_t rwlock;
} RWSafeHashTable;

void rw_insert(RWSafeHashTable *ht, int key, int value) {
    pthread_rwlock_wrlock(&ht->rwlock);
    insert(ht->table, key, value);
    pthread_rwlock_unlock(&ht->rwlock);
}

int rw_lookup(RWSafeHashTable *ht, int key) {
    pthread_rwlock_rdlock(&ht->rwlock);
    int val = lookup(ht->table, key);
    pthread_rwlock_unlock(&ht->rwlock);
    return val;
}

读写锁适合「读远多于写」的场景。比如缓存系统、配置中心、路由表等。

19.4 无锁哈希表简介

锁再好，也有开销。上下文切换、缓存失效、锁竞争……在高并发场景下，锁可能成为瓶颈。于是有了无锁（Lock-Free）哈希表。

无锁哈希表的核心思想：

• 使用 CAS（Compare-And-Swap）原子操作来更新数据。
• 不依赖操作系统锁，全靠 CPU 指令保证原子性。
• 通常配合分离链表或桶级锁来降低冲突。

一个简单的无锁插入伪代码：

// 假设每个桶是单向链表，头指针用原子变量
void lockfree_insert(AtomicPtr *head, Node *new_node) {
    do {
        new_node->next = atomic_load(head);
    } while (!atomic_compare_exchange_weak(head, &new_node->next, new_node));
}

这里用 CAS 循环把新节点插入链表头部。如果其他线程同时插入，CAS 会失败，重试即可。

无锁哈希表的难点：

• 内存管理：删除节点时，不能立即释放内存，因为可能有其他线程还在读它。需要引用计数或 RCU（Read-Copy-Update）。
• ABA 问题：CAS 操作中，指针值从 A 变成 B 又变回 A，CAS 会误判为没变化。需要额外标记位解决。
• 调试困难：并发 bug 难以复现，死循环或数据损坏很难定位。

19.5 知识体系总览

下面这张图总结了哈希表线程安全的三种方案及其适用场景：

从互斥锁到读写锁，再到无锁哈希表，每一步都是在「正确性」和「性能」之间做权衡。我个人习惯是：先保证正确，再考虑优化。不要一开始就追求无锁，除非你真的很清楚自己在做什么。

---

公众号:蓝海资料掘金营，微信deep3321