C++ unordered_map 与 unordered_set：哈希桶和 rehash
06 unordered_map 和 unordered_set 用哈希桶换平均效率
你有一个用户 ID 到用户信息的映射，用户 ID 是 uint64_t。查找频率极高，每次请求都要根据 ID 找到对应的用户对象。你对输出顺序完全不关心，谁先谁后没关系，只要能按键快速找到就行。这种场景下 std::map<uint64_t, UserInfo> 的对数查找就显得不够干脆：既然键是整数，能不能一步就算出位置？这就是 std::unordered_map 的入口。
无序关联容器的核心策略是退一步换效率：放弃有序，换取平均常数时间的查找。键的位置不再由大小关系决定，而是由一个哈希函数（hash function）计算出一个整数值，哈希值，然后根据这个值决定元素放在哪个桶（bucket）里。理想情况下，键均匀分散在各桶，每个桶里只有极少的元素（甚至只有一个），查找一个键就等于：计算哈希值（常数时间）→ 定位到桶（常数时间）→ 在桶内扫描可能的几个元素（平均常数时间）。总成本平均 O(1)。
但这个"平均"背后有一整套不可忽略的条件。
桶、哈希和相等判断
unordered_map 底层维护一个桶数组，桶的本质上是一个位置（或链表的头指针），每个桶负责收纳一部分哈希值范围内的元素。键插入时，容器计算 hash(key) 得到一个 size_t 类型的哈希值，然后用 hash(key) % bucket_count() 确定它归哪个桶管。通常一个桶内有一个单向链表（或等价的结构）把冲突到同一个桶的多个元素串在一起。
当你要查找一个键时，同样走这条路径：哈希→ 定位桶→ 在桶内逐个比较键的值。桶内比较用的是相等判断（equality predicate），默认就是 operator==。这意味着两个键要被认定为"相同"，必须同时满足：哈希值相同（撞到同一个桶），且 operator== 返回 true。如果哈希值相同但键不相等，这就是哈希冲突（collision），它们会在同一个桶的链表中共存，查找时需要依次比较，效率开始下降。
哈希函数的质量直接决定了 unordered_map 的表现。一个好的哈希函数会把键均匀地分散到所有桶中，使得每个桶负载大致相当。标准库为内置类型（整数、浮点、指针）和 std::string 等常见类型提供了 std::hash 的特化版本，一般来说够用。但如果你用自定义类型作为键，必须提供 std::hash 的特化或自定义哈希函数对象，同时在同一个桶中还需要 operator== 来判断冲突键是否真的相等，哈希值相同不代表键相同。
一个常见的自定义键模式：
struct Point { int x, y; };
bool operator==(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}
// std::hash 特化
template<> struct std::hash<Point> {
size_t operator()(const Point& p) const {
return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
}
};
std::unordered_set<Point> points;
points.insert({3, 5}); // 现在合法了
哈希函数保证同一个键多次哈希得到相同值，但不同键哈希到不同桶并不是保证，那是哈希函数质量的体现，不是正确性前提。标准允许所有键都哈希到同一个桶（退化成一个链表），此时查找就是 O(n)。你的代码不能依赖"反正哈希表很快"，必须配合合适的哈希函数和负载因子来维持平均效率。
负载因子与 rehash
负载因子（load factor）定义为元素总数除以桶数量：load_factor() = size() / bucket_count()。它是衡量"桶的拥挤程度"的指标，负载因子越高，每个桶里的平均元素数越多，碰撞越频繁，查找效率越差。
unordered_map 会尝试把负载因子控制在 max_load_factor() 以下。默认的 max_load_factor() 通常是 1.0。当一次插入导致 load_factor() 超过这个阈值时，容器会触发 rehash，扩大桶的数量（至少为 size() / max_load_factor()），然后把已有元素重新哈希分布到新桶结构中。
rehash 的代价很大：每个元素都需要重新计算归属桶并移动到新位置。更关键的是，rehash 会让所有迭代器、指向元素的指针和引用失效，虽然元素数据本身没有被移动（如果桶实现用的是链表节点），但它们对应的迭代器状态和桶链表结构被完全重排了。这个失效行为经常被忽略：你以为只是在插入一个元素，实际上容器在后台悄悄重建了整个桶阵列，所有之前保存的迭代器都变成了悬空状态。
reserve(n) 是预留给未来插入的：它确保桶数量足以容纳至少 n 个元素而不超出 max_load_factor()，从而在此次调用时就完成必要的 rehash，而不是在后续插入过程中零星触发。如果你预先知道大概要放多少元素，reserve 可以消除反复 rehash 的延迟峰值，付出的代价是在一开始就支付一次较大的重排。
rehash(n) 更直接：把桶数量设为至少 n，然后重排所有元素。reserve 内部本质上就是在调用 rehash(ceil(n / max_load_factor()))。
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> m;
std::cout << "初始 bucket_count: " << m.bucket_count() << '\n';
std::cout << "max_load_factor: " << m.max_load_factor() << '\n';
// 预估要放 100 个元素，提前 prepare
m.reserve(100);
for (int i = 0; i < 100; ++i)
m[i] = "value" + std::to_string(i);
std::cout << "插入 100 个后:\n";
std::cout << " size: " << m.size() << '\n';
std::cout << " bucket_count: " << m.bucket_count() << '\n';
std::cout << " load_factor: " << m.load_factor() << '\n';
// 再插入更多，观察 rehash
for (int i = 100; i < 200; ++i)
m[i] = "value" + std::to_string(i);
std::cout << "插入 200 个后:\n";
std::cout << " size: " << m.size() << '\n';
std::cout << " bucket_count: " << m.bucket_count() << '\n';
std::cout << " load_factor: " << m.load_factor() << '\n';
}
这段代码的输出会随实现而异，但结构是确定的：reserve(100) 之后，前 100 个元素的插入不会触发额外的 rehash。当插入到第 101 个时，负载因子超过阈值，rehash 发生，bucket_count 变大，所有元素被重新分布。
遍历顺序没有任何承诺
unordered_map 的遍历顺序没有业务语义。它可以和插入顺序不同，可以和你心理预期不同，可以在两次运行同一个程序时不同（取决于哈希种子，很多实现默认启用随机哈希种子以求安全）。在同一个容器实例内，只要不发生 rehash、没有任何插入和删除，遍历顺序在短时间内是稳定的，但这只是一个实现偶然，不构成可以依赖的保证。
"需要稳定排序输出"是 map 的硬需求信号。如果你在 unordered_map 中存好数据，然后每次输出前先拷贝到 vector 再 sort，效率先不说，这个工作流本身就说明你选错了容器，有序关联容器原生提供了按键的稳定遍历。
这并不是否定 unordered_map 的价值，而是在明确它的适用区间：你需要高效的按键查找、不关心输出顺序、键类型有良好的哈希实现、负载因子可控。在这些条件下，unordered_map 的查找和插入通常比 map 快一个数量级（从 O(log n) 降到平均 O(1)），但遇到不满足这些条件的情况（糟糕的哈希函数、过高的负载因子、需要范围查询或有序输出），unordered_map 的优势迅速消失甚至反转。
map 与 unordered_map 的对决
把 map 和 unordered_map 放在一张表里对比，差异就非常清楚了：
- 顺序：
map按键有序遍历，unordered_map遍历顺序无保证。 - 查找：
map的find是 O(log n)，unordered_map是平均 O(1)、最坏 O(n)。 - 插入：
map的插入总是 O(log n)（平衡树结构调整），unordered_map是平均 O(1)（哈希→桶→挂载），但 rehash 时触发 O(n) 重排。 - 范围查询：
map原生支持lower_bound/upper_bound，锁定键的范围。unordered_map做不到有效的范围查询，只能遍历全部再过滤。 - 内存：
map每个节点存储至少三个指针（左子、右子、父节点）加颜色标记。unordered_map每个元素至少一个后继指针（桶链表），外加桶数组本身。内存差异取决于实现和元素数量，没有绝对的一方更省。 - 迭代器稳定性：
map的迭代器在删除某个元素后，只有被删的那个失效，其他稳定。unordered_map同理，除非 rehash 发生，一旦 rehash 所有迭代器失效。 - 键要求：
map需要严格弱序的比较函数（默认operator<）。unordered_map需要哈希函数（默认std::hash）和相等判断（默认operator==）。
从这张表出发，决策规则反而是简单的：需要有序遍历或范围查询→map；只需要按键快速查找且不在意顺序→unordered_map。如果两者都满足（比如键是整数，既支持哈希又支持小于比较），那就看你更在意有序输出还是平均更快的查找，大多数场景中，查找频次远高于有序输出频次，所以unordered_map更常见。但如果你做的是一个需要频繁输出有序报告的系统（比如报表、日志分析），map的顺序原生性就价值连城了。
一个容易被忽视的边界：unordered_map 中的"常数时间"是平均的，不是保证的。如果攻击者有意识地构造大量哈希到同一个桶的键（哈希碰撞攻击），unordered_map 的单次查找可以从 O(1) 退化为 O(n)，足以让服务挂掉。生产环境中，如果键的来源不受信任，应该使用带有随机种子的哈希函数（现代实现默认已包含），或者在有安全需求的场景中换用有序关联容器，map 的 O(log n) 虽然在平均情况下不如 O(1)，但它在最坏情况下仍然是 O(log n)，不存在被攻击放大的风险。
unordered_multimap 和 unordered_multiset
和有序关联容器一样，无序容器也有允许重复键的 "multi" 变体：std::unordered_multimap 和 std::unordered_multiset。它们和普通版本的关系与 multimap 之于 map 一样，允许等值键重复出现，没有 operator[]，find 返回其中一个匹配而非全部。对于 unordered_multimap，equal_range(key) 返回的迭代器范围包含了所有键等于 key 的元素，但这个范围内元素的相对顺序没有任何保证。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::unordered_map<std::string, int> word_count;
word_count["hello"] = 5;
word_count["world"] = 3;
word_count["cpp"] = 10;
word_count["hello"] += 2; // 更新已存在的键
// find 查找
auto it = word_count.find("cpp");
if (it != word_count.end())
std::cout << "'cpp' 出现了 " << it->second << " 次\n";
// 遍历，顺序无保证
std::cout << "所有词频:\n";
for (const auto& [word, count] : word_count)
std::cout << " " << word << ": " << count << '\n';
// bucket 信息
std::cout << "bucket_count: " << word_count.bucket_count() << '\n';
std::cout << "load_factor: " << word_count.load_factor() << '\n';
// 查看 "hello" 在哪个桶
std::cout << "\"hello\" 在桶 " << word_count.bucket("hello") << '\n';
}
在多次运行中，遍历输出的顺序很可能不同。这是正常的，不是 bug。如果你依赖这个顺序来做业务判断，就会在不同环境、不同编译版本或不同哈希种子上出现不一致的行为。有序性需求出现时，请直接换到 map。
哈希结构的下一站
unordered_map 的哈希桶结构决定了它的核心能力和边界：它用空间（桶数组 + 链表指针的额外内存）换取了平均常数时间的查找，同时完全放弃了有序性。这个取舍在工程上是划算的，大多数查找密集型场景中，顺序确实不是需求，常数时间的收益是实打实的。但理解这个取舍的前提是接受它的全部条件：哈希质量、负载因子管理、rehash 风险、遍历不确定性。
哈希容器的第一条工程规则是提前估算规模。你知道大概要插入多少元素时，调用 reserve(n) 可以让容器一次性准备足够桶数量，减少中途 rehash。这个动作的意义不只是性能更平滑，也让迭代器失效时机更可控。没有 reserve 时，某次普通插入可能刚好触发 rehash，之前保存的迭代器全部失效；有了合理预留，批量插入期间结构更稳定。对高频服务来说，这种可预测性经常比单次操作快一点更重要。
第二条规则是认真对待自定义 key。内置整数、指针、std::string 通常有标准库提供的 std::hash，但结构体、组合 key、业务 ID 对象需要你自己定义哈希和相等判断。二者必须一致：如果 a == b 为真，那么 hash(a) 必须等于 hash(b)。反过来，哈希值相等不要求对象相等，因为冲突是允许存在的。如果这个一致性被破坏，容器可能把等价键放到不同桶里，查找结果就会变得不可靠。
组合哈希也不能太随意。很多人把两个字段的哈希值简单异或，这在字段分布有规律时容易产生大量碰撞。更稳妥的做法是使用成熟的组合方法，或者让 key 先归一化成一个稳定的字符串、整数元组，再用合适的哈希策略。哈希函数不需要加密级安全，但必须让真实数据分布尽量均匀。你可以通过观察 bucket_count()、load_factor()、单个桶大小分布来判断哈希质量，而不是凭感觉相信平均 O(1)。
第三条规则是不要依赖遍历顺序。无序容器的遍历顺序可能随着桶数量、插入顺序、哈希实现、编译器版本变化。即使某次运行看起来稳定，也只能说明当时的内部布局恰好如此。如果业务需要稳定输出，请把键拷贝出来排序，或者直接选择 map。把 unordered_map 的当前遍历结果写进快照、日志、测试 golden file，是非常容易制造脆弱测试的做法。
安全场景还要考虑哈希碰撞攻击。如果外部用户可以控制 key，并且能够构造大量落入同一桶的输入，平均常数时间会退化成线性扫描。某些运行库或框架会使用随机化哈希缓解问题，但标准 unordered_map 本身不给你最坏 O(1) 的保证。面对不可信输入、服务端公开接口、攻击者可反复试探的系统，稳定的 O(log n) 有时比平均 O(1) 更可靠。这不是说哈希表不能用于服务端，而是说 key 的来源和哈希策略要纳入设计。
最后，unordered_set 与 unordered_map 的区别只是值模型不同：前者只关心一个 key 是否存在，后者把 key 映射到一个 value。去重、成员判断、访问控制集合适合 unordered_set；计数、索引、缓存、对象表适合 unordered_map。如果你发现自己在 unordered_set 之外又维护一张平行数组保存数据，通常说明你真正需要的是 unordered_map；如果你在 unordered_map 里只把 value 设成 true，通常说明 unordered_set 更直接。
使用哈希容器时，接口设计也要避开遍历顺序泄露。比如一个函数返回 const std::unordered_map<K, V>&，调用方很容易顺手遍历它并把当前顺序当成输出顺序；更好的做法是提供明确的查询接口，或者在需要输出时返回一个已经排序好的 vector。哈希表的优势在内部查找，不在外部展示。把无序结构直接暴露给展示层，后面很容易出现"为什么线上顺序和本地不一样"这类问题。
哈希表也不适合所有小数据场景。几十个元素以内，vector 线性扫描经常足够快，代码更简单，内存更紧凑；哈希表需要桶数组、节点、哈希计算和相等比较，常数项并不小。只有当按键查找频率足够高、元素数量足够大、顺序无意义时，unordered_map 的平均 O(1) 才开始真正兑现价值。容器选择不能只看复杂度阶数，规模和访问频率同样重要。
在调试哈希表性能时，不要只看总耗时。先打印 bucket_count()、load_factor()，再抽样看最大桶长度，很多问题会直接暴露出来。一个负载因子看起来不高的表，也可能因为哈希函数糟糕而把大量 key 塞进少数桶；一个频繁 rehash 的表，平均耗时看起来还行，尾延迟却会出现尖刺。对于服务端程序，尾延迟经常比平均值更重要，因为一次 rehash 发生在请求路径上，就会让某个请求突然变慢。
自定义 key 还有一个维护成本：哈希和相等判断要随着字段语义一起更新。业务结构体新增字段后，如果 operator== 用了新字段，hash 没有同步更新，等价对象可能仍然满足 hash 一致性，也可能因为旧字段碰撞变多而性能下降；如果 hash 用了新字段，operator== 没用，等价规则就更混乱。最好把 key 的等价语义写成独立测试，明确哪些字段决定身份，哪些字段只是附带数据。
unordered_map 的 operator[] 也要谨慎使用。它在键不存在时会插入默认值，适合计数、累加、聚合这类"缺省值有意义"的场景；只读查询应该使用 find、contains 或 at。很多服务端 bug 来自一次看似无害的读取：查询一个不存在的 key，结果把空对象插进了索引，后续逻辑又把这个空对象当成真实数据处理。哈希表查找很快，但查询语义仍然要分清读和写。
批量删除时也不要边遍历边随意改结构。对无序容器来说，删除当前元素可以用 it = table.erase(it) 安全推进；插入新元素则可能触发 rehash，让所有迭代器失效。最稳妥的做法是把待删除 key 先收集到临时数组，再统一删除；或者只在循环中做删除，不做插入。哈希表的节点稳定性很好，rehash 这条全局风险线必须单独对待。
哈希容器的测试也要覆盖顺序无关性。不要把遍历输出直接作为 golden file；要么把结果按 key 排序后比较，要么逐个 key 检查值。还要测试缺失 key、重复插入、负载因子变化和自定义 key 的等价样例。只测"能查到一个存在的 key"太薄，哈希表真正容易出问题的地方在桶分布、默认插入和无序输出这些边界上。
理解了这些边界，unordered_map 就不再是一个更快的 map，它是一种完全不同的组织方式。它把顺序让出去，把范围查询让出去，把最坏情况稳定性让出去，换来按键查找和更新的平均效率。只要需求接受这些交换，哈希表就是非常锋利的工具；需求不接受时，树结构和排序数组会更可靠。
在真实项目里，哈希表经常承担索引层角色：对象本体可能在 vector、对象池或数据库结果集中，unordered_map 保存 key 到位置、ID 或摘要的映射。这样可以把快速定位和数据存储分开，避免把所有职责都塞进哈希表本身。哈希表负责"找到谁"，别的结构负责"如何保存和输出"。这个分工会在后面的综合小程序里再次出现。
如果你发现哈希表里存了很重的对象，也要检查移动、复制和 rehash 成本。节点式实现通常不会像 vector 那样批量搬动对象本体，但插入时仍然会构造节点，rehash 时仍然会重组桶链。对大对象来说，用稳定 ID、智能指针或对象池配合哈希索引，往往比把所有状态直接塞进 unordered_map 更清楚。
哈希表还有一个很实用的判断标准：输出顺序一旦进入需求，就要重新评估。偶尔输出一次，可以临时把键拷贝到 vector 排序；频繁输出、范围输出、分页输出都说明有序结构可能更合适。不要让无序容器长期承担有序展示任务，这会让每次输出都变成补偿性工作。
把哈希表用好，本质上是在管理三个变量：哈希质量、桶数量、业务是否接受无序。哈希质量决定元素能否均匀分布，桶数量决定负载因子和 rehash 频率，业务无序性决定你能不能享受哈希结构的主要优势。三个变量都清楚时，unordered_map 是非常直接的选择；任意一个变量含糊，都应该谨慎。
从数据结构的角度看，vector 的连续内存、list 的节点、map 的树、unordered_map 的哈希桶，它们各自在物理内存中是对数据的不同摆放方式。但标准库的算法不直接面对这些差异。算法只通过迭代器来接触元素，迭代器屏蔽了下层容器的结构，把这些不同的物理形态统一成一致的逻辑接口。接下来我们把视角从容器的"内部"抽出来，聚焦在迭代器这个通用游标上。
阅读导航
