CC++ & Algorithm

哈希冲突、负载因子与rehash——当两个物品要挤进同一个柜子时

极难3
语言版本：通用
概述：用教室座位比喻解释哈希冲突的必然性，讲解负载因子和rehash机制，以及它们对性能的影响，并给出C++和Python中观察这些现象的方法。

哈希冲突、负载因子与rehash——当两个物品要挤进同一个柜子时

从生活中的例子引入

想象你有一个储物柜，上面有100个小柜门（桶），每个柜门对应一个号码。当你要存放物品时，神奇的柜子会根据物品名字计算出一个1到100之间的号码，然后把这个物品放入对应号码的柜门里。但问题是，总共有100个柜门，却有无限多种物品名字，难免会出现两个不同的物品（比如“苹果”和“香蕉”）计算出的号码都是43号。这时就发生了冲突，两个物品想挤进同一个柜门。那怎么办？最简单的办法是：在43号柜门里面再放一个小的架子，把两个物品都放进去，用一条链子连起来。这样，当你找“苹果”时，先到43号柜门，然后沿着链子一个个找，直到找到名字匹配的“苹果”。这就是处理哈希冲突最常见的链地址法。

哈希表在存储过程中，随着放入的元素越来越多，每个桶里链接的物品也越来越多，查找效率就会下降（因为需要沿着链表遍历）。于是，我们需要一个指标来衡量“拥挤程度”——这就是负载因子。当负载因子超过某个阈值（比如1.0），哈希表就会自动rehash：扩充桶的数量，重新计算所有元素的位置，让它们分散得更均匀，从而恢复高效查找。

不过，这个“扩充”不是无限制的。如果你一开始就预计要放很多物品，可以提前告诉柜子：“我要放100个东西，请给我准备一个大柜子。”这样柜子就会一次性扩大，避免多次重新整理——这就是预留空间（reserve）。

理解哈希冲突、负载因子与rehash

哈希冲突的必然性

哈希函数把无限多的可能输入映射到有限个桶（比如N个桶），根据鸽巢原理：如果有N个鸽巢，却放进了N+1只鸽子，至少有一个巢里有两只鸽子。当元素数量大于桶数时，必然有冲突。即使元素数小于桶数，好的哈希函数应该让元素均匀分布，但冲突仍然可能发生（比如生日悖论：23个人中至少有两人同一天生日的概率超过50%）。所以，任何哈希表都必须有处理冲突的策略。

处理冲突的常见方法有两种：

  • 链地址法（separate chaining）：每个桶维护一个链表（或其他容器），所有映射到该桶的元素都放入这个链表。C++的unordered_set/map使用这种方法。
  • 开放地址法：当冲突发生时，通过探测（如线性探测、二次探测）在桶数组中寻找下一个空位。Python的字典和集合使用的就是开放地址法（结合伪随机探测）。

常见错误：认为好的哈希函数可以完全避免冲突。实际上，即使哈希函数完美均匀，只要元素数量超过桶数，冲突就不可避免。另外，不要以为哈希表查找总是O(1)——在冲突严重时，查找可能退化为O(n)（比如所有元素都映射到同一个桶里，变成一个链表）。

负载因子

负载因子（load factor）定义为：元素总数 / 桶的总数。它反映了哈希表的充满程度。

  • 负载因子小：桶多元素少，冲突少，查找快，但浪费空间（很多桶空着）。
  • 负载因子大：桶少元素多，冲突多，链表变长，查找变慢，但空间利用率高。

生活例子：一个班级有40个座位（桶），来了20个同学（元素），负载因子0.5。平均每两个位置坐一个人，很宽敞，找人也快。但如果来了80个同学，每个位置要挤两个人，负载因子2.0，找一个人就得在两个人里翻找，自然慢很多。

C++的unordered容器允许用户通过max_load_factor成员函数设置最大负载因子（默认一般为1.0）。当当前负载因子超过这个最大值时，容器会自动rehash。设置较小的max_load_factor（比如0.75）会让哈希表更早扩容，减少冲突，但会占用更多内存；设置较大的（比如2.0）则节省内存但可能变慢。大多数情况下默认值就够用。

常见错误：误以为负载因子越大越好（节省空间），但实际上负载因子过大会导致性能断崖式下降。另一个错误是修改了max_load_factor后忘记观察是否真的触发了rehash，导致程序效率异常。

rehash

rehash意味着：

  1. 分配一个新的、更大的桶数组（通常是原桶数的两倍左右）。
  2. 重新计算每个元素的哈希值，并放入新桶中（因为桶数变了，哈希模运算的结果也会变）。
  3. 释放旧的桶数组。

rehash是一个耗时的操作（O(n)），因为要遍历所有元素并重新插入。但因为它只发生在元素增长到一定阈值时，均摊下来每个插入操作的平均复杂度仍然是O(1)。你可以通过reserve预留足够的桶数来避免频繁rehash。

什么时候rehash？ 在C++中，当load_factor() > max_load_factor()时触发。在Python中，当哈希表容量超过2/3（约67%）时会自动扩容（通常扩大到4倍左右，元素较少时）。

性能影响：频繁rehash会导致插入大量元素时出现“卡顿”。比如你要插入100万个元素，如果每插入10万个就rehash一次，就会多次浪费时间。如果你提前用reserve(1000000)告知容器，它就会一次性分配足够的桶，rehash次数降到最低（可能只有一次初始化扩容或零次）。

常见错误：忘记调用reserve就插入大量元素，导致多次rehash，性能下降。另一个错误是认为rehash后元素顺序不变——实际上rehash会打乱所有元素的存储顺序，因此不要依赖unordered容器中元素的遍历顺序。

C++完整代码实现（带详细注释）

下面的程序演示了哈希冲突的观察、负载因子的变化以及rehash的发生。代码中每个变量定义都附有中文注释。

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    // 定义一个存放整数的无序集合
    unordered_set<int> mySet;

    // 查看初始桶数和最大负载因子
    cout << "初始化后:" << endl;
    cout << "桶数: " << mySet.bucket_count() << endl;          // 桶的数量
    cout << "最大负载因子: " << mySet.max_load_factor() << endl; // 默认为1.0
    cout << "当前负载因子: " << mySet.load_factor() << endl;   // 当前元素数/桶数

    // 插入若干元素，观察桶数和负载因子的变化
    for (int i = 0; i < 20; ++i) {   // i 是循环变量，表示第几个元素
        mySet.insert(i * 10);         // 插入0,10,20,...,190
    }

    cout << "\n插入20个元素后:" << endl;
    cout << "桶数: " << mySet.bucket_count() << endl;     // 可能已自动扩容
    cout << "元素个数: " << mySet.size() << endl;         // 20
    cout << "负载因子: " << mySet.load_factor() << endl;  // 约0.95（如果桶数为21）

    // 检查每个桶中的元素数，看看冲突情况
    cout << "\n每个桶中的元素个数:" << endl;
    for (size_t i = 0; i < mySet.bucket_count(); ++i) { // i 是桶编号
        size_t sz = mySet.bucket_size(i);                // sz 表示该桶中的元素数量
        if (sz > 0) {
            cout << "桶" << i << ": " << sz << " 个元素" << endl;
        }
    }

    // 手动设置最大负载因子，然后插入更多元素触发rehash
    mySet.max_load_factor(0.75);  // 设置较小的最大负载因子，触发更早的rehash
    cout << "\n设置最大负载因子为0.75后继续插入..." << endl;
    for (int i = 20; i < 30; ++i) {   // i 从20到29
        mySet.insert(i * 10 + 5);      // 插入205,215,...,295
    }

    cout << "\n插入30个元素后:" << endl;
    cout << "桶数: " << mySet.bucket_count() << endl;     // 应该更大
    cout << "元素个数: " << mySet.size() << endl;         // 30
    cout << "负载因子: " << mySet.load_factor() << endl;  // 约0.69（小于0.75）

    // 查看某个元素的哈希桶编号
    int key = 50;                           // 要查询的元素
    size_t bucketIndex = mySet.bucket(key);  // 获取元素50所在的桶编号
    cout << "元素" << key << "在桶" << bucketIndex << "中" << endl;

    // 使用reserve预先分配足够桶数，避免多次rehash
    unordered_set<int> mySet2;    // 另一个集合
    mySet2.reserve(100);          // 告诉容器我准备放100个元素，请预留空间
    for (int i = 0; i < 100; ++i) {
        mySet2.insert(i);          // 插入0~99
    }
    // 此时由于提前预留了空间，rehash次数很少（可能只有一次初始分配）
    cout << "\n使用reserve(100)后插入100个元素:" << endl;
    cout << "桶数: " << mySet2.bucket_count() << endl;    // 可能大于100
    cout << "负载因子: " << mySet2.load_factor() << endl; // 接近0.99（因为预留了约101个桶）

    return 0;
}

运行结果示例（具体数值可能因编译器不同而略有差异）：

初始化后:
桶数: 1
最大负载因子: 1
当前负载因子: 0

插入20个元素后:
桶数: 21
元素个数: 20
负载因子: 0.952381

每个桶中的元素个数:
桶0: 1 个元素
桶1: 1 个元素
...（可能所有桶各1个）
桶20: 1 个元素

设置最大负载因子为0.75后继续插入...

插入30个元素后:
桶数: 43
元素个数: 30
负载因子: 0.697674

元素50在桶29中

使用reserve(100)后插入100个元素:
桶数: 101
负载因子: 0.990099

从结果可以看出，随着插入元素增多，桶数增加了（rehash），负载因子保持在最大值附近。注意：第一次插入20个后桶数为21（因默认max_load_factor=1，所以桶数刚好比元素数多1），负载因子0.95；设置max_load_factor=0.75后，继续插入迫使rehash到43个桶，负载因子降到0.69；而使用reserve时直接分配了101个桶，负载因子0.99。

Python中等价功能的说明

Python的字典和集合也是基于哈希表的，但Python不提供直接的接口来观察桶数和负载因子。不过，Python的哈希表也有类似机制：当哈希表容量超过一定阈值（通常2/3满）时，会自动扩容（rehash）。你可以通过sys.getsizeof查看对象占用的内存大小，间接感受扩容。

Python的hash()函数可以查看对象的哈希值，但注意整数在Python中的哈希值通常是其本身（除了-1之类的特殊情况）。我们无法直接操作桶。

下面示例演示如何通过hash函数和字典的__sizeof__观察扩容：

import sys

d = {}                     # 空字典
print("空字典大小:", sys.getsizeof(d))  # 初始内存大小（72字节左右）

# 逐步添加元素，观察内存变化，指示rehash发生
for i in range(100):       # i 是键值
    d[i] = i                # 添加键值对
    if i % 20 == 19:        # 每20个打印一次（i=19,39,59,79,99）
        size = sys.getsizeof(d)
        print(f"添加{i+1}个元素后字典大小: {size} bytes")

运行结果示例（Python 3.11）：

空字典大小: 72
添加20个元素后字典大小: 312
添加40个元素后字典大小: 312
添加60个元素后字典大小: 728
添加80个元素后字典大小: 728
添加100个元素后字典大小: 1064

可以看到在20个时大小为312，到60个时跳到了728，这就是发生了rehash（扩容）。注意：Python的rehash不是每次添加都触发，而是当容量达到约2/3时一次性扩容（通常增长4倍左右）。内存大小变化可以让你直观感受到rehash的时机。

常见错误：在Python中，不要以为字典的插入总是O(1)且没有额外开销。当你一次性插入大量元素时，底层会经历多次rehash，导致插入的总时间不是线性的。不过Python的rehash策略已经优化得比较均衡，一般开发者无需手动干预。如果你需要提前预留空间，可以使用dict.fromkeys一次性创建大量键值对（但这只是创建，内部rehash仍然会发生）。

总结要点和注意事项

  1. 哈希冲突不可避免，但通过好的哈希函数和链地址法（或开放地址法）可以优雅处理。
  2. 负载因子是衡量哈希表“拥挤程度”的指标。C++中可以设置max_load_factor控制自动rehash的阈值。
  3. rehash是扩容操作，会影响所有已有元素的位置，开销大，但均摊成本可以接受。预先使用reserve可以预测元素个数，减少rehash次数。
  4. C++中的观察函数：bucket_count, load_factor, max_load_factor, bucket等可以帮助调试性能。
  5. Python中无直接观察接口，但可以通过内存变化感知rehash。Python默认负载因子大约2/3。
  6. 性能调优建议：如果知道将要放入大量元素，在C++中使用reserve(n)；在Python中无法预留，但可以预估后使用dict.fromkeys等方式一次性创建大量键值对（不过Python内部会自己处理，你很难控制）。
  7. 不要依赖元素的存储顺序，rehash会打乱原有顺序。unordered容器不保证顺序，即使在同一次运行中插入顺序不同，遍历结果也可能不同。
  8. 常见错误汇总：
    • 误以为哈希表查找总是O(1)，实际上冲突严重时会退化。
    • 忘记reserve导致多次rehash，插入大量元素时性能下降。
    • 修改max_load_factor后忽略了它对内存和性能的平衡。
    • 依赖unordered容器的元素顺序，写出错误代码。

理解了哈希冲突和rehash，你就能理解为什么哈希表有时快有时慢，也能在需要性能时做出合理选择。下一个知识点我们将学习如何为自定义类型编写哈希函数和等价比较，让它们也能放入unordered容器中。

例题精讲

1单选题

哈希表的负载因子（load factor）定义是？

A元素个数 / 桶的个数
B桶的个数 / 元素个数
C冲突元素个数 / 总元素个数
D桶的个数 / 表的总容量
2判断题

哈希表中负载因子越小，发生哈希冲突的可能性越大。

3单选题

在哈希表进行rehash操作时，以下关于时间复杂度描述正确的是？

AO(1)
BO(n)
CO(log n)
DO(n²)
4填空题
给定C++ unordered_map初始桶数为8，负载因子的最大值设置为0.5。在插入元素的过程中，当size() > ___时，会触发rehash操作。
5判断题

在哈希表的rehash过程中，所有已存在的元素都会重新计算哈希值并重新分配到新的桶中。