10. std::unordered_set / std::unordered_multiset 详解

哈希表，说白了就是「用空间换时间」的典型代表。我刚开始学STL时，总觉得它跟set差不多，直到有一次在项目中处理百万级数据去重，set跑了三秒多，换成unordered_set瞬间搞定——嗯，从那以后我再也不敢小看哈希了。

10.1 哈希表实现原理

先说说底层逻辑。unordered_set和unordered_multiset底层都是哈希表（hash table）。你可以把它想象成一个数组，每个位置叫「桶」（bucket）。

插入元素时，哈希函数把键值映射成一个整数，这个整数对桶数量取模，就得到了该元素应该存放的桶位置。理想情况下，每个桶里只有一个元素，查找就是O(1)。

但现实没那么完美。不同的键可能映射到同一个桶，这就叫「哈希冲突」。STL处理冲突的方式是「链地址法」——每个桶其实是一个链表（或更高效的数据结构），冲突的元素都挂在这个链表上。

核心要点：哈希表的性能取决于三个因素——哈希函数的质量、桶的数量、冲突解决策略。

哈希表核心结构图 桶数组（Bucket Array） 桶0 桶1 桶2（冲突） 桶3 ... 桶n 键A 键B 键C 哈希函数流程 输入键值 哈希函数计算 取模定位桶 插入/查找 无冲突 有冲突（链地址法） 链表节点

10.2 负载因子与rehash

负载因子（load factor）是个关键指标。它等于「元素总数 / 桶总数」。比如有100个元素，50个桶，负载因子就是2.0。

负载因子越大，冲突概率越高，性能越差。STL默认的负载因子是1.0。当实际负载因子超过这个阈值时，哈希表会自动扩容——也就是rehash。

我的经验：如果你能预估数据量，可以在构造时指定初始桶数量，避免频繁rehash。rehash是O(n)操作，数据量大时很伤性能。

rehash的过程是这样的：

  1. 分配一个更大的桶数组（通常是当前大小的两倍）
  2. 重新计算每个元素的哈希值，放到新桶中
  3. 释放旧桶数组

你可以通过以下接口控制负载因子：

std::unordered_set<int> us;
us.max_load_factor(0.75f);  // 设置最大负载因子
float lf = us.load_factor(); // 获取当前负载因子
us.reserve(1000);            // 预留空间，避免多次rehash

注意：不要频繁调用reserve或rehash。我曾经在一个循环里每插入一个元素就调用一次reserve，结果性能比set还差——因为每次都要重新分配内存。

10.3 冲突解决：链地址法

前面说了，STL用的是链地址法。每个桶维护一个链表，冲突的元素都挂在这个链表上。

查找时，先定位到桶，再遍历链表。如果链表很长，查找就退化成O(n)。所以控制负载因子很重要。

C++11之后，STL对链表做了优化——当链表长度超过某个阈值时，会转换成红黑树（类似map的底层结构）。这个优化在数据分布不均匀时特别有用。

冲突解决方式 优点 缺点
链地址法（STL采用） 实现简单，删除方便 链表过长时性能下降
开放地址法 缓存友好，空间利用率高 删除复杂，容易产生聚集
再哈希法 冲突时换哈希函数 实现复杂，不常用

10.4 自定义哈希函数

STL为基本类型（int、string等）提供了默认的哈希函数。但如果你用自定义类型做键，就得自己写哈希函数了。

举个例子，假设我们有一个Person结构体：

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        // 组合哈希：把多个字段的哈希值混合
        return std::hash<std::string>()(p.name) ^ 
               (std::hash<int>()(p.age) << 1);
    }
};

std::unordered_set<Person, PersonHash> people;

关键点：自定义哈希函数必须满足两个条件：

  • 相同的键必须产生相同的哈希值
  • 不同的键尽量产生不同的哈希值（均匀分布）

写哈希函数时，我有个小技巧：用boost::hash_combine的思路，把多个字段的哈希值混合。上面代码里的^ (hash << 1)就是一种简单混合。

另外，别忘了提供operator==。哈希表用哈希函数定位桶，但真正判断两个元素是否相等，靠的是operator==。

避坑指南：我曾经写过一个自定义哈希函数，把所有字段的哈希值直接异或。结果发现不同字段组合产生了相同的哈希值（比如("a",1)和("b",0)）。后来改用移位混合，冲突就少多了。

10.5 unordered_multiset 的特殊性

unordered_multiset和unordered_set的区别只有一个：允许重复元素。

插入重复元素时，它们会被放在同一个桶里。查找时，find返回第一个匹配的元素，equal_range返回所有匹配的范围。

std::unordered_multiset<int> ums;
ums.insert(1);
ums.insert(1);
ums.insert(2);

// 统计某个值的出现次数
size_t count = ums.count(1);  // 返回2

// 获取所有匹配元素的范围
auto range = ums.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";  // 输出 1 1
}

删除时要注意：erase(key)会删除所有匹配的元素。如果只想删一个，得用迭代器。

注意：unordered_multiset的erase(key)返回被删除的元素个数。如果你不确定容器里有多少个重复值，最好先调用count确认一下。

10.6 性能对比与选型建议

什么时候用unordered_set，什么时候用set？我个人的经验是：

  • 需要有序遍历 → 用set（红黑树，中序遍历有序）
  • 只关心查找速度 → 用unordered_set（平均O(1)，最坏O(n)）
  • 数据量小（几十个） → 两者差别不大，选哪个都行
  • 数据量大（百万级） → 优先考虑unordered_set

另外，unordered_set的内存占用通常比set大一些，因为要维护桶数组。如果你的内存很紧张，可以考虑set。

好了，关于unordered_set和unordered_multiset的核心内容就这些。记住一句话：哈希表是「用空间换时间」的典型，用好负载因子和自定义哈希函数，你就能发挥它的最大威力。

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

← 上一章 📖 返回目录 下一章 →