第二十五天：关联式容器——红黑树与哈希表的实战心法
说实话，C++ 标准库里的关联式容器，是我工作中用得最频繁的工具之一。今天咱们就把 set、map 和它们的哈希版本彻底聊透。
一、红黑树家族：set / multiset / map / multimap
这四个容器底层都是红黑树。红黑树是什么？说白了就是一种自平衡的二叉搜索树。它保证插入、删除、查找的时间复杂度都是 O(log n)。
我个人习惯把红黑树想象成一个「有纪律的二叉树」——每个节点要么红要么黑，路径上的黑色节点数必须相等。嗯，细节不用死记，你只要知道它很稳就行。
1. set 和 multiset
set 存储唯一键，multiset 允许重复键。两者都自动排序。
#include <set>
#include <iostream>
int main() {
std::set<int> s = {3, 1, 4, 1, 5, 9};
// 输出: 1 3 4 5 9 （自动去重+排序）
for (int x : s) std::cout << x << " ";
std::multiset<int> ms = {3, 1, 4, 1, 5, 9};
// 输出: 1 1 3 4 5 9 （保留重复，排序）
for (int x : ms) std::cout << x << " ";
return 0;
}
我的经验： 需要快速判断元素是否存在时，用
set 比 vector 快得多。我在做日志去重时，就用 set 存已处理的日志 ID，几百万条数据查起来毫秒级。
2. map 和 multimap
map 存键值对，键唯一；multimap 允许键重复。底层也是红黑树。
#include <map>
#include <iostream>
int main() {
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages["Alice"] = 31; // 覆盖旧值
// 遍历
for (const auto& [name, age] : ages) {
std::cout << name << ": " << age << "\n";
}
// multimap 示例
std::multimap<std::string, int> scores;
scores.insert({"Math", 95});
scores.insert({"Math", 88}); // 允许重复键
return 0;
}
注意：
map 的 operator[] 如果键不存在，会自动插入一个默认值。我曾经因为这个特性踩过坑——查配置时不小心写了个不存在的键，结果插入了大量空数据。建议用 find() 或 at() 来避免。
二、红黑树原理速览
红黑树的规则其实就五条：
- 节点是红色或黑色
- 根节点是黑色
- 叶子节点（NIL）是黑色
- 红色节点的子节点必须是黑色
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
你想想看，这五条规则保证了什么？保证了树的高度最多是 2log(n+1)。所以查找效率非常稳定。
核心思想： 红黑树不是追求绝对平衡（像 AVL 树那样），而是追求「近似平衡」。插入和删除时的旋转操作更少，实际性能往往更好。
三、哈希表家族：unordered_set / unordered_map
这两个容器底层是哈希表。平均时间复杂度 O(1)，最坏 O(n)。
哈希表的核心就是哈希函数 + 冲突处理。C++ 标准库用的是链地址法——每个桶里挂一个链表。
#include <unordered_map>
#include <iostream>
int main() {
std::unordered_map<std::string, int> freq;
freq["apple"] = 3;
freq["banana"] = 5;
freq["apple"]++; // 变成 4
// 查找
auto it = freq.find("apple");
if (it != freq.end()) {
std::cout << it->first << ": " << it->second << "\n";
}
// 遍历（无序）
for (const auto& [key, val] : freq) {
std::cout << key << ": " << val << "\n";
}
return 0;
}
选型建议： 需要有序遍历时用
map，只关心查找速度时用 unordered_map。我在做高频交易系统时，订单簿用 map（需要按价格排序），而用户信息用 unordered_map（只查不排序）。
四、哈希表原理深入
哈希表的关键参数有两个：
| 参数 | 说明 | 默认值 |
|---|---|---|
| 桶数量 (bucket_count) | 哈希表底层数组大小 | 实现定义 |
| 负载因子 (load_factor) | 元素数 / 桶数 | 1.0 |
当负载因子超过阈值时，哈希表会 rehash——重新分配桶数组，重新计算所有元素的哈希值。这个操作很耗时，所以如果你知道数据量，最好提前 reserve()。
std::unordered_map<int, int> m;
m.reserve(10000); // 提前分配空间，避免多次 rehash
我曾经踩过的坑： 自定义类型作为 unordered_map 的键时，必须提供哈希函数。有一次我忘了重载
std::hash，编译报错找了半小时。后来我习惯写个简单的 lambda 做哈希。
五、红黑树 vs 哈希表：怎么选？
| 场景 | 推荐容器 | 原因 |
|---|---|---|
| 需要有序遍历 | map / set | 红黑树天然有序 |
| 查找为主，不关心顺序 | unordered_map / unordered_set | O(1) 平均查找 |
| 范围查询（如找 20~30 之间的元素） | map / set | 支持 lower_bound / upper_bound |
| 数据量极大，内存敏感 | unordered_* | 哈希表内存更紧凑 |
一句话总结： 红黑树稳，哈希表快。但哈希表的最坏情况（所有元素哈希冲突）会导致退化成链表，性能暴跌。所以如果你的数据有规律，或者哈希函数可能被攻击，用红黑树更安全。
六、知识体系总览
下面这张图帮你理清今天讲的所有内容：
七、实战避坑指南
最后分享几个我实际工作中遇到的坑：
- 迭代器失效： 红黑树的插入不会使已有迭代器失效，但哈希表的 rehash 会使所有迭代器失效。如果你在遍历时插入元素，小心！
- 自定义比较器：
map和set默认用std::less，如果你存自定义类型，必须重载operator<或提供比较函数。 - 性能陷阱： 哈希表的
reserve()只预留桶空间，不预留元素空间。如果你知道元素数量，先reserve()能避免多次 rehash。
我的习惯： 写代码前先问自己三个问题——需要排序吗？需要范围查询吗？数据量多大？答案清楚了，容器自然就选好了。
好了，今天的内容就到这里。红黑树和哈希表是 C++ 标准库的基石，理解它们能让你写出更高效、更健壮的代码。下次遇到性能问题，不妨想想是不是容器选错了。
公众号:蓝海资料掘金营，微信deep3321