16、unordered系列容器（下）：unordered_multiset与unordered_multimap、性能对比（与set/map）、负载因子与rehash
好，咱们接着聊unordered系列。上一章我把unordered_set和unordered_map的基本用法讲透了。这一章咱们把剩下的两个兄弟——unordered_multiset和unordered_multimap搞定，然后深入聊聊性能、负载因子这些底层的东西。
说实话，这两个容器平时用得没前两个那么频繁，但一旦遇到需要存储重复键的场景，它们就是最优解。我自己在做一个日志分析系统时就踩过这个坑——一开始用unordered_map存IP访问次数，结果发现同一个IP有多条日志，直接覆盖了……后来换成unordered_multimap才搞定。
16.1 unordered_multiset：允许重复的无序集合
unordered_multiset和unordered_set最大的区别就一句话：允许键值重复。底层实现完全一样——哈希表，所有操作的平均时间复杂度依然是O(1)。
你想想看，什么时候需要它？比如统计一篇文章里每个单词出现的所有位置，或者记录一个班级里所有学生的年龄分布。这些场景下，同一个值会出现多次，用multiset就对了。
核心区别速览：
- unordered_set：每个键唯一，插入重复键会被忽略
- unordered_multiset：允许重复键，插入重复键会成功
- 查找操作：find()返回第一个匹配元素的迭代器
- 计数操作：count()返回匹配元素的数量
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_multiset<int> nums;
// 插入重复值
nums.insert(10);
nums.insert(20);
nums.insert(10); // 允许！不会报错
nums.insert(30);
nums.insert(10); // 再来一个10
std::cout << "容器大小: " << nums.size() << "\n"; // 输出5
std::cout << "10出现的次数: " << nums.count(10) << "\n"; // 输出3
// 遍历所有元素
for (const auto& val : nums) {
std::cout << val << " ";
}
std::cout << "\n";
// 删除所有值为10的元素
nums.erase(10);
std::cout << "删除后大小: " << nums.size() << "\n"; // 输出2
return 0;
}嗯，这里要注意一点：erase(key)会删除所有匹配的元素。如果你只想删一个，得用迭代器版本的erase。我曾经在代码里没注意这个细节，结果把一批数据全删了……还好有版本控制。
16.2 unordered_multimap：一对多的映射关系
unordered_multimap就更实用了。它允许同一个键对应多个值。典型的场景是什么？比如一个部门有多个员工，一个学生选了多门课，一个IP地址对应多个访问记录。
我个人习惯用unordered_multimap来处理这种一对多的关系，而不是自己手动维护一个unordered_map<Key, vector<Value>>。为什么？因为前者更简洁，而且查找、插入都是O(1)。
注意：unordered_multimap没有operator[]！因为一个键可能对应多个值，用下标访问没有意义。想取值？用find()、equal_range()或者遍历。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_multimap<std::string, int> scores;
// 插入数据：一个学生可能有多个成绩
scores.insert({"张三", 85});
scores.insert({"李四", 92});
scores.insert({"张三", 90}); // 张三又考了一次
scores.insert({"王五", 78});
scores.insert({"张三", 88}); // 张三第三次考试
// 查找张三的所有成绩
auto range = scores.equal_range("张三");
std::cout << "张三的成绩: ";
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->second << " ";
}
std::cout << "\n";
// 统计某个键的数量
std::cout << "张三共有 " << scores.count("张三") << " 条记录\n";
return 0;
}equal_range()这个函数特别有用。它返回一个pair，first指向第一个匹配元素，second指向最后一个匹配元素的下一个位置。说白了，就是给你一个区间，里面全是同一个键对应的值。
16.3 性能对比：unordered系列 vs 有序系列
好，接下来咱们聊聊性能。这是面试高频题，也是实际开发中必须考虑的问题。
我直接说结论：大多数情况下，unordered系列比有序系列快。但这不是绝对的，得看具体场景。
| 操作 | unordered_set/map | set/map |
|---|---|---|
| 插入 | 平均O(1)，最坏O(n) | O(log n) |
| 查找 | 平均O(1)，最坏O(n) | O(log n) |
| 删除 | 平均O(1)，最坏O(n) | O(log n) |
| 遍历 | 无序（按桶顺序） | 有序（升序） |
| 内存占用 | 较高（哈希表+桶） | 较低（红黑树节点） |
| 自定义类型 | 需要提供hash函数 | 需要提供比较函数 |
为什么会这样？unordered系列用哈希表，理想情况下直接算出位置，一步到位。但哈希冲突严重时，性能会退化到O(n)。有序系列用红黑树，稳定O(log n)，不会突然变慢。
我的建议：
- 数据量大（百万级以上）且不需要排序 → 用unordered系列
- 需要有序遍历 → 用set/map
- 对实时性要求极高，不能接受偶尔的慢查询 → 用set/map
- 自定义类型作为键，懒得写hash函数 → 用set/map
我曾经在一个实时交易系统里用过unordered_map，结果某次哈希冲突严重，导致一笔订单处理延迟了十几毫秒……虽然概率很低，但在金融系统里这就是事故。后来我换成了map，虽然慢一点但稳定。
16.4 负载因子与rehash：哈希表的灵魂
聊unordered系列，绕不开负载因子和rehash。这两个概念直接决定了哈希表的性能。
负载因子 = 元素个数 / 桶数
说白了，就是每个桶平均装了多少元素。负载因子越大，哈希冲突的概率越高，查找效率越低。负载因子越小，内存浪费越多。
C++标准库默认的负载因子是1.0。什么意思？就是当元素个数等于桶数时，就会触发rehash。
rehash是什么？就是重新分配桶的数量，然后把所有元素重新哈希到新桶里。这个过程很耗时——O(n)的复杂度。
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> s;
std::cout << "初始桶数: " << s.bucket_count() << "\n";
std::cout << "最大负载因子: " << s.max_load_factor() << "\n";
// 插入元素，观察桶数变化
for (int i = 0; i < 20; ++i) {
s.insert(i);
std::cout << "插入 " << i+1 << " 个元素后，桶数: "
<< s.bucket_count() << "，负载因子: "
<< s.load_factor() << "\n";
}
// 手动调整负载因子
s.max_load_factor(0.75); // 设置最大负载因子为0.75
s.rehash(50); // 手动触发rehash，设置桶数为50
std::cout << "调整后桶数: " << s.bucket_count() << "\n";
std::cout << "调整后负载因子: " << s.load_factor() << "\n";
return 0;
}关键API总结：
load_factor()：获取当前负载因子max_load_factor()：获取/设置最大负载因子rehash(n)：设置桶数至少为n，并重新哈希reserve(n)：预留空间，相当于rehash，但更直观——预留n个元素的空间
我个人习惯在知道数据量的大致范围时，提前调用reserve()。比如我知道要插入100万个元素，就先reserve(1000000)。这样能避免多次rehash带来的性能开销。我在处理一个千万级的数据集时，用了reserve后，插入时间从8秒降到了3秒——效果立竿见影。
16.5 知识体系总览
下面这张图把本章的核心知识点串起来了。你可以看到unordered_multiset/multimap在整个家族中的位置，以及负载因子和rehash如何影响性能。
这张图把整个知识脉络理清楚了。从上到下：先区分两类容器，再理解它们的核心特性，最后落到性能调优的关键——负载因子和rehash。你把这个图记在脑子里，面试时随便问都不怕。
避坑指南：
- 我曾经在循环中插入大量元素，没注意rehash会导致迭代器失效——结果程序崩溃了。记住：rehash会使所有迭代器、指针、引用失效。
- 自定义类型作为键时，一定要提供hash函数和相等比较函数。我见过有人只写了hash函数忘了相等比较，编译过了但运行结果全错。
- 不要频繁修改max_load_factor。默认1.0是经过权衡的，除非你有明确的性能测试数据，否则别动它。
好了，unordered系列容器到这里就讲完了。从基本用法到性能调优，该覆盖的点都覆盖了。实际开发中多用用，慢慢就能找到感觉。记住：没有银弹，选对容器比优化代码更重要。
公众号:蓝海资料掘金营，微信deep3321