第8章哈希表的扩容与缩容

课程目录第8章哈希表的扩容与缩容

哈希表的扩容与缩容：负载因子与动态调整

哈希表这东西，用起来确实爽——O(1)的查找速度，谁不爱？但你要是真把它当个无底洞往里塞数据，迟早要翻车。我早年做网络流量分析模块时就吃过这个亏：哈希表越用越慢，最后比链表还拉胯。问题出在哪？就是没管好扩容和缩容。

说白了，哈希表是个“空间换时间”的产物。它给你一块连续内存，你往里扔键值对。但内存是有限的，数据是无限的。怎么平衡？这就引出了我们今天的主角——负载因子。

负载因子：哈希表的“健康指标”

负载因子（Load Factor）的定义很简单：

负载因子 = 已存储元素个数 / 哈希表总桶数

举个例子。你有个哈希表，底层数组有16个桶。现在存了8个键值对。那负载因子就是 8/16 = 0.5。

这个值能告诉你什么？

负载因子太小：桶多数据少，内存浪费严重。你想想看，明明10个数据就能搞定的事，你非占100个位置，这不是败家吗？
负载因子太大：桶少数据多，哈希冲突急剧上升。链表的长度越来越长，查找效率从O(1)退化到O(n)。

我个人的习惯是，把负载因子控制在0.6到0.75之间。低于0.5就考虑缩容，高于0.75就触发扩容。当然，这个阈值不是死的——有些场景追求极致性能，可以设到0.5；有些场景内存紧张，0.8也能忍。

核心要点：负载因子是哈希表性能与内存消耗的平衡点。没有绝对正确的值，只有适合你场景的值。

何时扩容？何时缩容？

这个问题，我当年也纠结过。后来踩了几个坑，总结出两条铁律：

扩容时机

负载因子超过阈值（比如0.75）：这是最常见的触发条件。
链表/红黑树深度过大：即使负载因子没超标，但某个桶的冲突链特别长，也该扩容了。我在做日志分析系统时就遇到过——某些key被恶意构造，全挤到一个桶里，负载因子才0.3，但那个桶的链表已经100多个节点了。

缩容时机

负载因子低于下限（比如0.25）：数据删得差不多了，桶还占着，浪费内存。
大量删除操作后：你删了80%的数据，但哈希表的大小没变。这时候就该缩容，把内存还给系统。

注意：缩容不是必须的。如果你的应用场景是“只增不减”，那缩容逻辑完全可以砍掉。我曾经为了省事，在嵌入式设备上直接禁用了缩容——反正内存够用，少个功能少个bug。

rehash操作：搬家是个技术活

扩容或缩容，本质上就是一次rehash。什么意思？

假设原来哈希表有8个桶，现在要扩到16个。你不能直接把数组长度改成16就完事——因为哈希函数依赖桶的数量。原来 key % 8 算出来的位置，换成 key % 16 后全变了。所以你得重新计算每个元素的位置，然后搬过去。

rehash的步骤很简单：

分配新数组（大小是原来的2倍或0.5倍）。
遍历旧数组的每个桶。
对桶里的每个元素，用新哈希函数重新计算位置。
插入到新数组的对应桶中。
释放旧数组。

代码实现大概长这样：

// 哈希表扩容
void hash_table_resize(HashTable *ht, size_t new_capacity) {
    // 1. 分配新数组
    HashNode **new_buckets = calloc(new_capacity, sizeof(HashNode *));
    
    // 2. 遍历旧数组
    for (size_t i = 0; i < ht->capacity; i++) {
        HashNode *node = ht->buckets[i];
        while (node != NULL) {
            HashNode *next = node->next;
            
            // 3. 重新计算位置
            size_t new_index = node->hash % new_capacity;
            
            // 4. 头插法插入新桶
            node->next = new_buckets[new_index];
            new_buckets[new_index] = node;
            
            node = next;
        }
    }
    
    // 5. 释放旧数组，更新指针
    free(ht->buckets);
    ht->buckets = new_buckets;
    ht->capacity = new_capacity;
}

这段代码看着简单，但有个坑：rehash期间，哈希表是不可用的。如果你在rehash过程中插入或查询数据，要么数据丢失，要么查到旧数据。这就是为什么很多哈希表实现会在rehash时加一把大锁。

小技巧：rehash时用头插法插入新桶，效率高。但要注意，头插法会反转链表的顺序。如果你依赖插入顺序，记得改用尾插法。

渐进式rehash：别让一次搬家卡死你

上面那种一次性rehash，有个致命问题：耗时不可控。

你想想看，如果你的哈希表里有1000万个元素，rehash一次要搬多久？我实测过，在普通服务器上，光遍历和重新插入就要几百毫秒。这期间整个哈希表都锁着，所有请求都得排队等。对于高并发系统来说，这就是灾难。

怎么解决？渐进式rehash。

核心思想很简单：不一次搬完，分多次搬。

具体做法：

同时维护两个哈希表：旧表和新表。
每次插入、删除、查找操作时，顺便搬一部分数据（比如搬一个桶）。
搬完一个桶，就把旧表的那个桶置空。
直到所有桶都搬完，释放旧表。

这样，rehash的耗时被分摊到每次操作中。单次操作只多花一点点时间，但系统整体不会出现“卡死”现象。

Redis的哈希表就是这么干的。我当年看Redis源码时，看到这设计直呼内行——把大任务拆成小任务，用时间换平滑。

渐进式rehash的伪代码：

// 渐进式rehash：每次搬一个桶
void incremental_rehash(HashTable *ht) {
    if (ht->rehash_idx == -1) {
        return; // 没有rehash在进行
    }
    
    // 从rehash_idx开始，搬一个非空桶
    while (ht->rehash_idx < ht->old_capacity) {
        if (ht->old_buckets[ht->rehash_idx] != NULL) {
            // 搬这个桶的所有元素到新表
            HashNode *node = ht->old_buckets[ht->rehash_idx];
            while (node != NULL) {
                HashNode *next = node->next;
                size_t new_idx = node->hash % ht->new_capacity;
                node->next = ht->new_buckets[new_idx];
                ht->new_buckets[new_idx] = node;
                node = next;
            }
            ht->old_buckets[ht->rehash_idx] = NULL;
            break;
        }
        ht->rehash_idx++;
    }
    
    // 检查是否搬完
    if (ht->rehash_idx >= ht->old_capacity) {
        // 全部搬完，释放旧表
        free(ht->old_buckets);
        ht->old_buckets = NULL;
        ht->buckets = ht->new_buckets;
        ht->capacity = ht->new_capacity;
        ht->rehash_idx = -1;
    }
}

这段代码里，rehash_idx记录当前搬到了哪个桶。每次操作前调用一次incremental_rehash，搬一个桶。如果那个桶是空的，就继续找下一个非空桶。直到所有桶搬完，收工。

关键设计：渐进式rehash期间，查找操作需要查两个表——先查新表，没找到再查旧表。插入操作只插新表。删除操作两个表都要删。这些细节，一个都不能漏。

一张图看懂哈希表动态调整

说了这么多，不如一张图来得直观。下面这个SVG图，把扩容缩容的整个流程串起来了：

这张图把扩容流程走了一遍：从初始状态开始，插入数据导致负载因子超标，触发扩容，然后选择rehash方式，最后完成扩容。缩容的流程类似，只是方向相反——负载因子低于下限时触发，新容量减半。

避坑指南

最后，分享几个我踩过的坑：

rehash期间别做全表遍历：如果你在渐进式rehash期间遍历整个哈希表，得同时遍历旧表和新表，而且要注意跳过已经搬过的桶。我当年没处理好这个，导致遍历结果重复——查了半天才发现是rehash的锅。
缩容阈值别设太高：有些人把缩容阈值设成0.5，结果频繁触发缩容和扩容，系统在“扩-缩-扩-缩”之间反复横跳。我建议缩容阈值设成扩容阈值的一半以下，比如扩容0.75，缩容0.25。
多线程环境要加锁：rehash期间，哈希表的结构在变。如果多个线程同时操作，轻则数据错乱，重则程序崩溃。我见过最惨的一次，rehash到一半，另一个线程插入数据，直接把新表的内存踩坏了——排查了三天才找到原因。

好了，哈希表的扩容与缩容就聊到这。记住一句话：负载因子是标尺，rehash是手段，渐进式是智慧。下次你设计哈希表时，希望这些经验能帮你少走弯路。

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

📚 课程目录

哈希表的扩容与缩容：负载因子与动态调整

负载因子：哈希表的“健康指标”

何时扩容？何时缩容？

扩容时机

缩容时机

rehash操作：搬家是个技术活

渐进式rehash：别让一次搬家卡死你

一张图看懂哈希表动态调整

避坑指南