第13章并发哈希表设计

课程目录第13章并发哈希表设计

并发哈希表设计：分段锁、无锁思路与扩容实战

哈希表这东西，咱们做系统编程的几乎天天用。单线程下它就是个数组加链表，简单得很。但一旦上了多线程，问题就来了——你读我写，你写我读，数据乱成一锅粥。

今天咱们聊聊并发哈希表的设计。我这些年踩过的坑不少，从最早粗暴地给整个表加一把大锁，到后来用分段锁、甚至无锁结构，每一步都有血泪教训。你想想看，一个高并发的服务，哈希表要是成了瓶颈，那整个系统都得跟着遭殃。

一、分段锁设计：把大锁拆成小锁

最早我接手过一个缓存系统，整个哈希表就一把读写锁。刚开始还行，后来并发上来了，性能直线下降。为什么？因为所有线程都在抢同一把锁，哪怕它们操作的是不同的桶。

分段锁的思路很简单：把哈希表分成多个段（Segment），每个段独立加锁。这样线程A操作段0，线程B操作段1，互不干扰。

核心思想：锁的粒度越细，并发度越高。但也不是越细越好，锁太多会带来额外的内存开销和管理复杂度。

我一般这样设计分段锁哈希表：

#define SEGMENT_COUNT 16  // 分段数，通常是2的幂

typedef struct {
    pthread_mutex_t lock;
    int capacity;
    int size;
    struct Entry** buckets;
} Segment;

typedef struct {
    Segment segments[SEGMENT_COUNT];
    int (*hash_func)(void* key);
} ConcurrentHashMap;

// 根据key定位到哪个段
int get_segment_index(void* key, int (*hash)(void*)) {
    int h = hash(key);
    return h & (SEGMENT_COUNT - 1);  // 位运算取模，效率高
}

这里有个细节：分段数最好设成2的幂。这样取模可以用位运算代替除法，性能提升明显。我在一个高吞吐项目里测过，光这一项改动，整体吞吐就提升了15%。

我的习惯：分段数一般取16或32。太少锁竞争还是严重，太多管理成本上升。你可以根据CPU核心数来调，通常分段数 ≥ 核心数 × 2 就差不多了。

二、无锁哈希表的实现思路

分段锁虽然好，但终究还是有锁。有锁就有上下文切换，就有等待。在一些极端场景下——比如延迟敏感的交易系统——我们希望完全避免锁。

无锁哈希表，说白了就是用原子操作代替锁。CAS（Compare-And-Swap）是咱们最常用的武器。

我简单说两种常见思路：

基于CAS的链式哈希：插入时用CAS把新节点挂到链表头部。如果CAS失败，说明有其他线程抢先了，重试就行。
开放地址法 + 原子操作：用数组存数据，插入时用CAS原子地写入空槽位。删除时用标记位，不真正删除。

// 无锁插入示例（链式哈希）
void lockfree_insert(AtomicBucket* bucket, void* key, void* value) {
    Node* new_node = create_node(key, value);
    while (1) {
        Node* old_head = atomic_load(&bucket->head);
        new_node->next = old_head;
        // CAS：如果head还是old_head，就把new_node写进去
        if (atomic_compare_exchange_weak(&bucket->head, &old_head, new_node)) {
            break;  // 成功，退出
        }
        // 失败则重试，说明有其他线程改了head
    }
}

我曾经踩过的坑：无锁编程最怕ABA问题。线程A读到head是X，准备CAS时线程B把head改成Y又改回X。线程A的CAS成功了，但它以为链表没变过，实际上结构已经变了。解决办法是加版本号，或者用带标记的指针。

说实话，无锁哈希表实现起来非常考验功底。我建议你如果不是特别必要，先用分段锁。等对并发控制有了深刻理解，再碰无锁。我自己也是写了三年多线程代码后，才敢在生产环境用无锁结构。

三、哈希表的并发扩容

哈希表用着用着，数据多了就得扩容。单线程下扩容很简单：新建一个大数组，把旧数据重新哈希一遍搬过去。但并发环境下，这事就麻烦了——你搬数据的时候，别的线程还在读写。

我常用的方案有两种：

方案	原理	优缺点
全局锁扩容	扩容时锁住整个表，搬完再释放	实现简单，但扩容期间所有操作阻塞
渐进式扩容	每次操作搬一部分数据，逐步完成	无长时间阻塞，但实现复杂

我个人更倾向于渐进式扩容。虽然代码写起来麻烦点，但用户体验好。你想想看，一个线上服务突然卡顿几百毫秒，用户肯定骂娘。

渐进式扩容的核心思路：

维护新旧两张表，一个迁移指针记录搬到了哪里
每次插入、查询、删除操作时，顺便搬一小批数据
所有操作先查旧表，再查新表
等数据全部搬完，释放旧表

typedef struct {
    Segment* old_table;   // 旧表
    Segment* new_table;   // 新表（容量翻倍）
    int migrate_index;    // 已迁移到的位置
    pthread_mutex_t resize_lock;
} ResizableHashMap;

// 每次操作时调用，搬一个桶的数据
void migrate_one_bucket(ResizableHashMap* map) {
    int idx = atomic_fetch_add(&map->migrate_index, 1);
    if (idx >= map->old_table->capacity) return;
    
    // 把old_table[idx]的数据重新哈希到new_table
    // ... 搬数据逻辑 ...
}

我的经验：每次搬一个桶就够了，别贪多。搬多了反而影响正常操作的延迟。另外，迁移指针要用原子操作，防止多个线程重复搬同一个桶。

四、性能测试与调优

设计完了，到底好不好用？得测。我一般从三个维度来评估：

吞吐量：每秒能处理多少操作（插入/查询/删除）
延迟分布：P50、P99、P999延迟，特别是尾部延迟
扩展性：随着线程数增加，性能是否线性增长

下面是我之前做的一个对比测试结果（8核机器，50%读50%写）：

方案	1线程	4线程	8线程	16线程
全局锁	100万 ops/s	110万	105万	100万
分段锁(16段)	98万	350万	620万	680万
无锁	95万	380万	700万	750万

看到没？全局锁在4线程后就瓶颈了，因为锁竞争太激烈。分段锁和无锁则能充分利用多核。

调优时我一般关注这几个点：

锁的粒度：分段数是不是合理？可以试试8、16、32、64
哈希函数：分布均匀吗？不均匀会导致某些段特别热
扩容阈值：负载因子设多少？0.75是经典值，但你可以根据读写比例调
内存分配：频繁分配释放节点？考虑用内存池

一句话总结：分段锁是工程实践中最稳妥的选择。无锁适合极致性能场景，但实现难度大。扩容一定要用渐进式，别让服务卡顿。

好了，关于并发哈希表的设计，咱们就聊到这儿。这些内容是我多年实战的积累，希望能帮你少走弯路。

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

📚 课程目录

并发哈希表设计：分段锁、无锁思路与扩容实战

一、分段锁设计：把大锁拆成小锁

二、无锁哈希表的实现思路

三、哈希表的并发扩容

四、性能测试与调优