unordered_map / unordered_set 使用指南：哈希表的平均 O(1)

在正式开始之前，我想先问你一个问题：假设你有一百万条学生记录，每条记录都有一个唯一的学号，你需要频繁地「按学号快速找到某条记录」。如果前面你学的 set / map 足够快，那恭喜你，你已经解决了一大类问题。但今天这篇要讲的 unordered_set / unordered_map，在某些场景下会比 map 快得多——因为它们的平均查找时间复杂度是 O(1)。

你没看错，是 O(1)，也就是"不管数据有多少，查找一次的时间基本恒定"。我猜你已经忍不住好奇了：这怎么可能？我们前面讲红黑树，增删查都是 O(logN)，现在直接到 O(1)，是不是吹牛？别急，读完这篇你就明白其中的原理，也知道它的代价是什么。

这两个容器刚推出的时候，很多初学者会犯一个直觉错误：以为 unordered_map 就是"无序版的 map"。这句话没错，但它把最重要的东西——为什么无序、凭什么更快——给一笔带过了。这篇我会把这两点讲透。

而且我要提前预告，读完之后你应该始终带着这三个问题去理解它：

• 凭什么 unordered_* 能做到平均 O(1)？这个"平均"藏了什么前提，最坏能坏到什么程度？
• 为什么 unordered_* 对 key 的要求这么"苛刻"——既要能转成整数，又要能比较相等？
• 为什么它的遍历顺序既不是有序的、也不是插入顺序，甚至多次运行还不一样？

这三个问题，恰好对应这篇的三个承重墙：哈希表底层原理、模板参数设计、迭代器语义。你把这三点吃透，unordered_* 家族就再没有能难住你的地方了。

unordered 容器是怎么来的

我们先从需求说起。你之前学的 set 和 map，底层是一棵红黑树（Red-Black Tree）。红黑树是一棵平衡二叉搜索树，靠它"左小右大"的排布，任何时候查找某个键，都只需要比较树高那么多次，也就是 O(logN)。

O(logN) 已经很快了——即使有一百万个元素，log₂(10⁶) 大约只有 20，意味着查找最多比较 20 次就能命中。但注意，这 20 次比较里的每一次，都是一次"跟树节点里的值做比较"的运算。

这里我想让你真正体会到"比较"有多贵，因为它决定了为什么我们需要哈希。红黑树查找一个键，路径是这样的：从根节点开始，用你要找的键和当前节点的键做一次比较，小于就往左走、大于就往右走、等于就命中。每一次比较，都要"读出当前节点的值，再执行一次大小判断"。当数据量是十万、百万的时候，这 20 层比较放大的成本，就是你要为"有序"付出的每分钟都在发生的开销。

那能不能更快？当然可以。如果你能不靠比较，而是靠"直接算出这个键该放哪"，一次就定位到位置呢？

打个比方。红黑树像书店里按拼音字母排序的书架，你想找《三国演义》，你得从书架的某个位置开始，根据"三"字比"三"前还是后，一层层缩小范围。而哈希表像图书馆里的"按号码取书"系统：每本书按索书号直接是格子里，你只要知道索书号，直接走到那个格子把书拿出来——不用比对任何书名。

其实哈希的思想一点都不神秘，你自己就能写一个最简陋的版本。假设我们想快速判断一个 0 到 99 的整数有没有出现过，最朴素的做法就是开一个长度 100 的 bool 数组，把数字 i 直接放到下标 i 的位置上——"数字就是下标"，这就是哈希最简单的形态：一个从"键"到"位置"的映射函数。查找时连比较都不用，arr[key] 一次定位。

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // 最简陋的"哈希表"：一个数组，下标当作键，值标记有没有出现过
    vector<bool> seen(100, false);
 
    seen[7] = true;      // 记录"7 出现过"
    seen[42] = true;     // 记录"42 出现过"
 
    int q;
    cout << "输入一个 0~99 的整数: ";
    cin >> q;
    if (q >= 0 && q < 100 && seen[q])
        cout << q << " 出现过" << endl;
    else
        cout << q << " 没出现过" << endl;
    return 0;
}

看到没有，这个数组版的查找是真正的 O(1)，一次都没有比较。但它的局限也很明显：数组下标只能是整数，而且必须是"从 0 开始的连续整数"，否则 arr[key] 就直接越界了。如果我们想存 string、想存 double、想存一个结构体当键，怎么办？这就需要把"任意类型的键"统一换算成一个整数下标——这就是**哈希函数（hash function）**的职责，也是本篇真正的主角。

在这个"直接映射"的思想之上，标准库为你封装好了生产级、可复用的版本——它有很多称谓，比如"哈希表（hash table）""散列表""无序关联容器（unordered associative container）"。在 C++ 里，它们就是 unordered_set / unordered_map。

这里必须点明一个版本细节：unordered_* 系列是 C++11 标准正式引入的成员。在此之前，它们其实已经以 TR1（Technical Report 1，2005 年的标准技术报告）的形式存在，当时的命名空间是 std::tr1::unordered_map。如果你在支持 TR1 的老编译器（比如老版 GCC）上编译，可能要写 #include <tr1/unordered_map>；但到了 C++11，它们被扶正进标准库 std 命名空间，头文件也简化为 <unordered_map> / <unordered_set>。所以——如果你的代码要在纯 C++98 标准下编译，这些容器是用不了的，必须在支持 C++11 及以上的编译器环境下运行。

unordered 系列都有谁

map / set 有四种：map、set、multimap、multiset。unordered 系列也完全对应有四种：

• unordered_map：键值对，键唯一，对应 map。
• unordered_set：纯集合，键唯一，对应 set。
• unordered_multimap：键值对，键可以重复，对应 multimap。
• unordered_multiset：纯集合，键可以重复，对应 multiset。

其中 unordered_multimap / unordered_multiset 和前面的 multimap / multiset 功能完全类似，都是支持 Key 冗余（就是允许存储相同的键）。它们和各自"单值版"的区别，集中在 key 的要求、迭代器及遍历顺序、性能这三个方面——这也是整篇关于 unordered_set/map 与 set/map 差异的核心线索，我们先记住。

为了让你一眼看清这套家族谱系，我画一张表：

横向看是"同一种容器换了底层结构"，纵向看是"同一个哈希表支持去重还是支持冗余"。你掌握一套，另一套就自然通了。

它们分别属于两个头文件：unordered_set 和 unordered_multiset 需要 #include <unordered_set>，unordered_map 和 unordered_multimap 需要 #include <unordered_map>。这一点和 set/map 分别在 <set>、<map> 里的习惯完全对称，很好记。

这里先埋一个常常被忽略、但面试爱考的点：unordered_set / unordered_map 的键是去重的，而 unordered_multiset / unordered_multimap 允许同一个键出现多次。判断"去重版里某键是否已有"用 find / count；而"多重版"里，同一个键可能出现多次，它们的底层桶里会同时挂着多个相同的键。

unordered_set 的模板声明：四个参数

我们先看 unordered_set 的类声明，理解它的模板参数是理解"为什么自定义类型要用会麻烦"的第一步。

template <
    class Key,               // 第一个参数：关键字类型，也就是集合里存的元素类型
    class Hash = hash<Key>,  // 第二个参数：哈希函数对象，默认用 std::hash<Key>
    class Pred = equal_to<Key>,  // 第三个参数：等值比较函数对象，默认用 std::equal_to<Key>
    class Alloc = allocator<Key> // 第四个参数：空间配置器，用来申请内存
>
class unordered_set;

需要强调：这里的类声明确实是四个模板参数，但其中第二个、第三个参数在 C++ 标准里其实还有各自的"别名类型"，也就是容器对外暴露的嵌套类型名（type trait），课件里也标注了它们：

• 第一个 Key 对应容器的 key_type（对 set 而言 key_type 和 value_type 是同一个类型，都是 Key）；
• 第二个 Hash = hash<Key> 对应 hasher，意思是"负责计算哈希的那种类型"；
• 第三个 Pred = equal_to<Key> 对应 key_equal，意思是"负责判断键是否相等的那种类型"；
• 第四个 Alloc = allocator<Key> 对应 allocator_type，意思是"负责内存分配的那种类型"。

这些别名类型看起来很绕，但你只要体会一件事：标准库用"类型擦除"的方式，把"如何哈希、如何判等、如何分配内存"这三个可替换的策略，都做成了模板参数。你改变任何一个，容器的行为就跟着变。这正是 C++ 里"策略设计"的典型——约定一个接口（能调用、能返回正确类型），实现随你替换。

逐行拆开看：

• 第一个模板参数 Key，就是集合里存的元素类型。比如 unordered_set<int> 里存 int，unordered_set<string> 里存 std::string。
• 第二个参数是哈希函数（Hash），类型是 hash<Key>。它的作用是把一个 Key 换算成一个整数（具体是 size_t，后面原理节会细讲这个类型）。默认情况下，标准库给内置类型（int、double、指针）以及 std::string 等都事先写好了 hash<Key> 的特化版本，所以你直接用它们不需要操心。但如果 Key 是你自己定义的结构体，那 hash<Key> 标准库可不知道该怎么算——这时就得你自己搞定（后面专门讲）。
• 第三个参数是等值比较函数（Pred），类型是 equal_to<Key>。它是用来判断"两个键是否相等"的。默认的 equal_to<Key> 会去调用 Key 的 operator==。所以如果你的自定义类型没有提供 operator==，这里也要自己处理。
• 第四个参数 Alloc 是空间配置器（allocator），负责底层内存的申请和释放。做工程的人偶尔会用它对内存做池化管理（提前申请一大块内存、之后反复复用，避免反复向操作系统要内存），但对绝大多数人来说，这个参数一辈子都用不上。

unordered_map 的声明和 unordered_set 几乎一样，只是在 Key 后面多了一个 T（映射的值类型）参数。对 map 来说，它的 key_type 是 Key，而 value_type 变成了 pair<const Key, T>——这是 map/set 家族的一个经典差异：set 里只存一个键，map 里存的是"键值对"。后面遍历环节你会看到，对于 map，迭代器解引用的对象是一个 pair，需要用 first（键）和 second（值）来分别访问。

绝大多数情况下，我们只需要传第一个参数——也就是像 unordered_set<int>、unordered_map<string, int> 这样写就完了。要知道，"为什么标准库要设计成总是要求哈希+等值比较"这个问题，绝非一时兴起，这背后正是哈希表的两个底层要求，我们先记住这两个要求，后面讲原理会彻底讲透：

• 要求一：Key 要能转成一个整数（便于算出存储位置）。容器要用这个整数来决定"这个键放到哪个桶"。
• 要求二：Key 要能做相等比较（用于处理冲突时确认命中）。因为哈希有可能撞车，撞车后要在同一个桶里精确判断"是不是同一个键"。

顺便补一句版本细节：从 C++17 开始，unordered_set 也支持类模板参数推导（CTAD，Class Template Argument Deduction）。也就是说，某些情况下你可以直接写 unordered_set s{1, 2, 3}; 让编译器帮你推导出 Key = int。不过 CTAD 只能推导第一个参数，后面三个策略参数依然得默认模板参数来兜底。这只是语法糖，不影响你理解底层四个参数的本质。

unordered_set 和 set 的三个差异

你可能会说："反正功能一样，那我直接用 unordered_set 不就完了？" 没那么简单。虽然 set 和 unordered_set 高层 API 几乎一模一样——都支持 insert、erase、find，用起来一样的顺手——但它们底层和背后有三处本质差异，正是这些差异决定了你该选谁。

差异一：对 Key 的要求不同

• set 要求 Key 支持小于比较（operator<），因为它基于红黑树，靠"谁比谁小"来排列节点。
• unordered_set 要求 Key 能转成整数（供哈希函数用）且支持等于比较（供去重判断用）。

换句话说，同样是放自定义类型，红黑树只要有"小于",而无序容器必须同时有"哈希"和"等于"。这正是我们上面说的哈希表的两个要求。

这里有个很多初学者都没意识到的哲学翻转：红黑树把"比较"当成了万能的排序依据，而哈希表把"比较"降级成了只用于"命中确认"的辅助手段。 在红黑树里，比较既要用来排序（所以需要 <），又要用来查重；在哈希表里，定位已经交给哈希函数了，== 只负责在极少数"撞到同一个桶"的时候，确认是不是同一个键。这也是为什么 unordered 对 == 的要求，反而是一种更"纯粹"的等值判断。

差异二：迭代器类型和遍历顺序不同

• set 的迭代器是双向迭代器（bidirectional iterator），可以前移和后移。它的底层是红黑树，中序遍历天然有序，所以遍历 set 得到的结果是有序且去重的。
• unordered_set 的迭代器是单向迭代器（forward iterator），只能向后走。它的底层是哈希表，元素的存储位置由哈希函数算出，和元素本身的大小没有关系，所以遍历结果无序且去重。

这里我想让你把"单向"和"双向"这个差异彻底消化掉，因为它不是文字游戏。双向迭代器支持 it--（往后退）和 it++（往前进），所以你可以从尾往头扫，也可以"两头夹击"取最近邻；而单向迭代器只有 it++，你只能一路往前，永远回不去。为什么哈希表的迭代器只能是单向的？因为哈希表的元素分散在一个一个的桶里，节点之间没有天然的"前驱/后继"逻辑——你要从某个元素"往后退一步"，根本不知道退到哪个桶、哪个节点，所以单向是它的既有限制。

这是可以写代码验证的，标准库头文件 <iterator> 里给你提供了迭代器类别的标记类型。我们可以在编译期用 static_assert（静态断言，编译时检查）来确认它们的类别：

#include <iostream>
#include <set>
#include <unordered_set>
#include <iterator>
#include <type_traits>
using namespace std;
 
int main()
{
    // iterator_traits 能"问出"迭代器的类别标签，利用它做编译期断言。
    // is_same<A,B>::value 在 A 和 B 是同一类型时为 true。
    static_assert(is_same<
        iterator_traits<set<int>::iterator>::iterator_category,
        bidirectional_iterator_tag>::value,
        "set 的迭代器应当是双向迭代器");
 
    static_assert(is_same<
        iterator_traits<unordered_set<int>::iterator>::iterator_category,
        forward_iterator_tag>::value,
        "unordered_set 的迭代器应当是单向迭代器");
    cout << "编译期已经确认了两种迭代器的类别" << endl;
    return 0;
}

这段代码如果编译通过，就说明上面的说法系统认证过了。forward_iterator_tag 和 bidirectional_iterator_tag 是标准库给迭代器贴的"身份标签"，你不需要记，只要直觉上理解"能退的（双向）比只能进的（单向）功能更强"即可。

这里就有了本文第一个"坑"：不要指望遍历 unordered_set 得到有序结果，也不要假设遍历顺序等于插入顺序。它既不保证有序，也不保证是插入顺序——顺序取决于哈希结果和当前桶的数量，而这些在运行时会变（后面讲 rehash 时你就有数了）。

差异三：性能不同

• 红黑树增删查的平均效率是 O(logN)。
• 哈希表增删查的平均效率是 O(1)。

这是最核心的卖点：大多数场景下，unordered_set / unordered_map 的增删查改都比 set / map 快，尤其是查找和批量插入。因为 O(1) 意味着无论容器里有一万条还是一百万条，一次查找的时间几乎不变，而红黑树会随数据量增长而变慢。

不过"平均 O(1)"这句话背后的条件很关键，它有个最坏情况会退化到 O(n)——这个我们专门放到"桶与平均 O(1) 的原理"那一节深挖，那是全文最重要的一段。

这里额外提醒一句关于"凭什么 unordered 更快但实际没那么玄"的认知：O(logN) 和 O(1) 的差距在大数据量下才真正拉开。数据量只有几十上百时，常量开销（哈希函数的计算、内存布局）反而可能让 unordered 并不占优，甚至更慢。所以"unordered 一定更快"是片面的——它在"海量精确查找"这个特定战场上才是王。这个道理到"性能实测"和"选型"两节你会看得更清楚。

基本使用：insert / erase / find / count / operator[]

聊完差异，直接上手。unordered_set 提供的这些接口用法和 set 一模一样，你完全可以无缝迁移：

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us;
 
    // insert：插入元素
    // 返回值是 pair<iterator, bool>，bool 表示这次是否真的插入了新元素
    auto p = us.insert(5);   // 插入 5，成功，p.second == true
    cout << "插入5: " << (p.second ? "成功" : "失败") << endl;
 
    us.insert(3);            // 插入 3
    us.insert(1);            // 插入 1
    us.insert(3);            // 再次插入 3，因为键唯一，这次不会真的插入
 
    // size：元素个数（因为去重，插入 4 个实际只有 3 个）
    cout << "size = " << us.size() << endl;  // 输出 3
 
    // find：查找某个键，找不到返回 end()
    if (us.find(3) != us.end())
        cout << "找到了 3" << endl;   // 会打印
    if (us.find(100) == us.end())
        cout << "没找到 100" << endl; // 会打印
 
    // count：统计键出现的次数（单值版要么 0 要么 1）
    cout << "3 出现了 " << us.count(3) << " 次" << endl; // 输出 1
 
    // erase：按键删除，返回删除的个数
    cout << "删除 3，删除了 " << us.erase(3) << " 个" << endl; // 输出 1
    cout << "size = " << us.size() << endl;  // 输出 2
 
    return 0;
}

这里我要把几个接口掰得更碎一些，因为它们各有值得注意的细节：

关于 insert 的三个常见细节：

第一，insert 的返回值是 pair<iterator, bool>。bool 反映的是"这次操作到底有没有插入一个新元素"——键已存在时，容器保持原样不动，second 为 false，此时 first（迭代器）指向那个已经存在的旧元素。所以如果你想知道"元素是否首次出现"，检查 p.second 是最直接的手段，它甚至比 count 更省一次查找。

第二，unordered_set 的 insert 也支持 insert(begin, end) 批量插入一段迭代器范围，以及 C++11 起的 insert({a, b, c}) 用初始化列表一次插入多个值。这点和 set 一致，但有一个和 vector 不一样的要点：哈希表批量插入有扩容开销，能提前预估数据量时用 reserve 会显著更省（原理节会讲）。

第三，自 C++11 起还新增了 emplace（在容器内部直接构造元素，省一次拷贝/移动）和 insert 的"带位置提示"版本。emplace 对 unordered_set<string> 这类"构造昂贵"的键尤其有用。下面这段演示一下 init-list、范围插入和 emplace：

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
 
int main()
{
    unordered_set<string> us;
 
    // 初始化列表方式批量插入
    us.insert({"apple", "banana", "cherry"});
 
    // 范围插入：把 vector 里的元素整体搬进来
    vector<string> more = {"dog", "elephant"};
    us.insert(more.begin(), more.end());
 
    // emplace：在容器内部直接构造 string，通常比 insert 少一次拷贝
    us.emplace("fig");
 
    cout << "size = " << us.size() << endl;   // 5
    for (const auto& w : us)
        cout << w << " ";
    cout << endl;
    return 0;
}

关于 erase 的三种常见形态，这几乎是每个容器的标配，但值得点名：按键值删、按迭代器删、按范围删。按迭代器删比较隐蔽，误用会导致迭代器失效（后面单独讲"迭代器失效"这个坑）。

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us = {10, 20, 30, 40, 50};
 
    // 形态1：按键值删除，返回删除的元素个数（去重版要么 0 要么 1）
    cout << us.erase(20) << endl;   // 1，删掉了 20
 
    // 形态2：按迭代器删除，返回下一个元素的迭代器
    auto it = us.find(30);
    if (it != us.end()) {
        it = us.erase(it);          // 删掉 it 指向的元素，it 指向下一个
        cout << "删掉30后,下一个元素是 " << (it != us.end() ? to_string(*it) : string("(尾)")) << endl;
    }
 
    // 形态3：按范围删除 [first, last)
    auto f = us.begin();
    auto e = ++us.begin();          // 第二个元素的位置
    us.erase(f, e);                 // 删除从 begin 到第一个元素
 
    cout << "size = " << us.size() << endl;
    return 0;
}

注意形态2里我把返回值赋给了新的迭代器 it——这是删除元素时迭代器失效的第一个法门：对哈希表，erase(it) 之后那个迭代器本身指向的结点已经被销毁，不能再碰；但标准保证哈希容器删除操作不会让"其他"迭代器失效（只让受影响的失效）。这是哈希表和 vector 的一个关键区别：vector 删除中间元素会让后面所有迭代器失效，而哈希表只可能让那个别删除的元素失效。下面"隐藏的坑"小节我会再补一条最经典的：边遍历边删除，必须像形态2那样用返回值接住下一个迭代器，而不能直接 ++it 跳过。

关于 find 和 count 的分工： find 返回迭代器，找不到返回 end()，适合"我还要拿到那个元素/对应的值"的场景；count 返回个数，适合"我只想知道存不存在、有几个"的场景。对去重版的 unordered_set / unordered_map，count 恒定返回 0 或 1，所以"判断在不在这"用 count(key) != 0 是最直白的写法——而且 C++20 还新增了更清晰的 contains 成员函数（下面 map 小节会补代码）。

同样，unordered_map 的接口和 map 几乎一致，并且因为它是"键值对"容器，额外多了一个主角接口 operator[]（下标访问），用起来非常顺手：

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
int main()
{
    unordered_map<string, int> m;
 
    // insert：插入一对键值，用 {} 或者 make_pair
    m.insert({"apple", 3});
    m.insert(make_pair("banana", 5));
 
    // operator[]：如果键存在就返回其引用；如果不存在，就"插入一个默认值"并返回引用。
    // 这一步非常常用，但也最容易踩坑——> 见下方说明。
    m["cherry"] = 7;   // "cherry" 不存在，先插入默认值0，再把0改成7，等价于 {cherry,7}
    m["apple"] += 1;   // "apple" 存在，直接取值，加1，变成4
 
    // find：查找
    auto it = m.find("apple");
    if (it != m.end())
        cout << it->first << " -> " << it->second << endl; // apple -> 4
 
    // erase：按键删除
    m.erase("banana");
 
    // 遍历：键值对，it->first 是键，it->second 是值
    for (const auto& kv : m)
        cout << kv.first << " -> " << kv.second << endl;
 
    return 0;
}

关于 map 家族，我再帮你把三件容易混淆的事理清楚：

第一，operator[] 和 find 是两码事。 operator[] 会隐式插入，find 不会。这是 C++ 里让无数人掉坑的经典设计（下面有专门的一节）。

第二，map / unordered_map 还有一个安全的取读成员函数 at(key)。它是 C++11 引入的：键存在就返回对应值的引用，键不存在就抛出 std::out_of_range 异常。它和 operator[] 最大的不同就是不改容器。所以当你"只想读、又不想为不存在的情况额外判空"时，at 是比 operator[] 更安全的选择：

#include <iostream>
#include <unordered_map>
#include <stdexcept>
#include <string>
using namespace std;
 
int main()
{
    unordered_map<string, int> m;
    m["apple"] = 3;
 
    try {
        cout << m.at("apple") << endl;      // 3，键存在，正常
        cout << m.at("nope") << endl;       // 键不存在，这里抛异常
    } catch (const out_of_range& e) {
        cout << "捕获异常: " << e.what() << endl;
    }
    cout << "size = " << m.size() << endl;  // 仍是 1，at 不会插入任何东西
    return 0;
}

注意上面 m.at("nope") 抛出异常后，size 依然是 1——这正好反衬出 operator[] 的"副作用"有多坑：它那一次访问就会让 size 变成 2。

第三，C++17 给你带来了两个"终于不再纠结 operator[] 副作用"的新接口：insert_or_assign 和 try_emplace。 这是在 map/unordered_map 上专门为"有就更新、无才插入"这类需求而生的：

• insert_or_assign(k, v)：键存在就更新它对应的值，键不存在就插入；返回 pair<iterator, bool>，且不会像 operator[] 那样要求值类型可默认构造。适合"统计/写入的最新值保持一致"。
• try_emplace(k, args...)：类似 emplace，但如果键已经存在就什么都不做（不构造值、不覆盖），返回 pair<iterator, bool>。适合"只在首次插入，不想重复构造值"的高效场景。

看个对比例子：

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
int main()
{
    unordered_map<string, int> m;
 
    // insert_or_assign：键存在就覆盖，键不存在就插入
    m.insert_or_assign("score", 90);
    m.insert_or_assign("score", 95);   // 键已存在，覆盖为 95
    cout << m["score"] << endl;        // 95
 
    // try_emplace：键已存在就返回旧元素，不做任何改动
    auto [it, ok] = m.try_emplace("score", 100); // 键已存在，ok == false
    cout << "try_emplace 返回 ok = " << ok << endl;   // 0 (false)
    cout << m["score"] << endl;                     // 仍是 95
 
    // 键不存在时 try_emplace 才会真正插入
    m.try_emplace("name", 1);
    cout << "size = " << m.size() << endl;          // 2
    return 0;
}

auto [it, ok] 是 C++17 的结构化绑定（structured binding），一次性把一个 pair 解包成两个变量，非常常用。这三个接口（insert_or_assign/try_emplace）都属于比较新的 C++ 特性，如果你的编译环境是 C++98/11，那只有 operator[] 可用了——这也是版本差异里最重要的一个提醒。

再补一个 C++20 的语法糖：contains。 它比 count 语义更直白，是"判断键在不在"的最清晰写法：

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
 
int main()
{
    unordered_set<string> us = {"cpp", "python"};
    if (us.contains("cpp"))
        cout << "存在 cpp" << endl;   // 会打印
    if (!us.contains("java"))
        cout << "不存在 java" << endl; // 会打印
    return 0;
}

contains 是 C++20 才有的，老编译器用 count(x) != 0 或 find(x) != end() 代替即可。

这里有个关于 operator[] 的、非常经典且隐蔽的坑：operator[] 会有"插入副作用"。只要你去访问一个不存在的键（哪怕只是读它），它都会先把这个键以默认值插入进去。比如说，下面这段代码本来只想"看看在不在"，结果反而把数据塞进去了：

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main()
{
    unordered_map<string, int> m;
    // 我们只是"读"一个不存在的键
    int v = m["hello"];   // 糟糕！这里不仅读了，还把 {"hello",0} 插进去了
    cout << "size = " << m.size() << endl; // 输出 1，而不是 0
    cout << "v = " << v << endl;           // 输出 0
    return 0;
}

所以，判断键存不存在，应该用 find 或 count，而不是 operator[]——除非你本来就打算在值不存在时给它一个默认值（比如做词频统计，这正是 operator[] 最好用的场景）。看下面这个经典应用，用它做"统计一段文字里每个单词出现几次"：

#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
using namespace std;
 
int main()
{
    string text = "apple banana apple cherry banana apple";
    stringstream ss(text);        // 把字符串当作输入流来读，方便按空白切词
    unordered_map<string, int> freq;
    string word;
    while (ss >> word)            // 逐个读取单词
        freq[word]++;            // 第一次出现时插入默认0再变1，后续直接自增
    for (const auto& kv : freq)
        cout << kv.first << " 出现 " << kv.second << " 次" << endl;
    return 0;
}

这段代码里 freq[word]++ 就是 operator[] 精髓的浓缩：存在就在原值上加一，不存在就先是 0 再加到 1，一行完成"初始化+计数"。如果换成 insert 去写，你得先 find 判断在不在、再决定是 insert 还是更新，繁琐得多。

在收尾这节之前，我把 unordered_* 最容易踩的几个"隐藏坑" 集中在这里讲掉，因为它们都藏在"基本使用"这个看似平淡的外表之下：

坑一：边遍历边删除，必须用返回值接住下一个迭代器。 哈希表删除一个元素会让指向它的迭代器失效。如果你在循环里 for(auto it = us.begin(); it != us.end(); ++it) { if(...) us.erase(it); }，那么 erase(it) 之后又去 ++it，此时 it 已经指向被销毁的结点，是未定义行为（很可能崩溃）。正确写法是形态2那样的：it = us.erase(it); 让返回值接手下一个迭代器，else ++it; 手动前进。C++20 之后其实有了更优雅的 erase_if 自由函数，但那是后话。

坑二：operator[] 要求值类型可默认构造。 如果值是 unique_ptr、某个没有默认构造函数的类，那么 m[key] 这种写法会编译报错——因为它默认要"插入一个默认构造的值"。这时候就该用 insert / emplace / insert_or_assign 了。

坑三：在 const 容器上不能用 operator[]。 operator[] 只有非 const 版本（因为它可能修改容器），所以 const unordered_map<string,int>& cm; cm["x"] 编译不过，必须用 at 或 find。

坑四：别拿 unordered_map/unordered_set 的迭代器去做"有序算法"的输入。 比如 std::lower_bound / std::binary_search 需要随机访问或有序序列，哈希容器的迭代器是单向的且内容无序，这些算法要么编译不过、要么结果没有意义。有序相关的活交给 map/set 或手动排序过的 vector 就好。

遍历：迭代顺序不保证

前面强调过，unordered 容器的遍历顺序既不保证有序，也不保证等于插入顺序。我用一段直观的代码证明给你看：

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us;
    // 按 10,20,30,40,50,60,70,80 的顺序插入
    for (int i = 1; i <= 8; ++i)
        us.insert(i * 10);
 
    // 打印遍历结果
    for (int x : us)
        cout << x << " ";
    cout << endl;
    return 0;
}

你运行这个程序（在不同编译器、不同版本、不同桶数下），大概率会看到输出不是 10 20 30 ... 80 这种顺序，而是类似 80 10 60 20 ... 这样乱序的结果。为什么？因为元素存放的位置不是语义顺序，而是由 hash(元素) % 桶数 算出来的桶下标决定的。哪个键能被算到几号桶，跟键之间谁大谁小毫无关系。

更"玄学"的是，这个顺序还不是固定不变的：当元素数量变多、触发扩容（rehash）时，桶的数量会变，所有元素的桶下标难免跟着变，遍历顺序就可能整个打乱。所以你可能在调试时发现"咦，我啥都没改，怎么遍历顺序变了"——别慌，多半是触发了 rehash。结论就一句话：凡是依赖迭代顺序的逻辑，都不要用 unordered 容器来做。你要是需要按序输出，要么改用 map/set，要么自己排序。

既然"顺序不保证"是这么重要的一条铁律，我把它再往深挖几层，帮你建立更牢固的直觉：

为什么连"插入顺序"都不保证？ 你想，哈希表里每个元素住在"由哈希值定下来的桶"里，一个新元素来了，它的桶号由它自己的键决定，跟"它是第几个来的"毫无关系。所以天然就没有"谁先来谁排前面"这回事。相比 vector 用"物理上挨着的下标"决定顺序、红黑树用"大小关系"决定顺序，哈希表是根本没有顺序这个概念的。它不是"顺序被打乱了"，而是"顺序从未被定义过"。

为什么连"同一个程序跑两遍"顺序还可能不一样？ 因为 std::hash 对某些类型（尤其 std::string）的标准实现，标准库并没有规定具体算法——不同的标准库实现（libstdc++、libc++、MSVC）各不相同；甚至有些实现会对字符串哈希使用每次进程带有随机扰动（hash seed randomization）的策略，用来抵御"故意构造全部撞桶的恶意输入"（这属于哈希洪水防护）。在这种扰动下，同一个程序、同一个输入，每次运行的哈希值可能都不同，遍历顺序自然也就不同。所以你千万不要把 unordered 的遍历顺序当成"可靠的中间结果"跨进程使用。

那我就是想要按序输出怎么办？ 有两条路：一是改用 map/set，让红黑树帮你把序遍历；二是先把 unordered 的结果拷到 vector，再 sort。第二条路的典型场景是"先用哈希表去重统计，再按某种规则排序输出"，下面这段就演示了"去重后按升序输出"：

#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    vector<int> raw = {50, 10, 30, 10, 20, 30, 40, 50};
    unordered_set<int> uniq;
    for (int x : raw)
        uniq.insert(x);          // 用哈希表去重，顺序无所谓
 
    vector<int> sorted(uniq.begin(), uniq.end()); // 拷出来
    sort(sorted.begin(), sorted.end());           // 再排序
 
    for (int x : sorted)
        cout << x << " ";        // 10 20 30 40 50
    cout << endl;
    return 0;
}

这套"哈希去重 + 排序"的组合，在海量数据处理里非常常见，因为它把"去重的快"和"排序的有序"分给了两个各自最强的容器。

桶与平均 O(1) 的原理

现在，到了全文最重要的一段——把哈希表的工作原理彻底讲明白，你才能真正理解"平均 O(1) 但最坏 O(n)"这句话的分量。

哈希表（hash table）的内部，可以想象成这样一个结构：

• 一个数组，数组里的每个格子叫一个桶（bucket），桶用编号 0、1、2…表示。
• 当你往哈希表里插入一个键 key 时，先调用哈希函数 hash(key)，得到一个大而杂的整数（可以理解为这个键的"指纹"），再对这个整数做一次"取模"，算出它该进几号桶。
• 因为不同的键算出的桶下标可能一样（哈希冲突），所以每个桶其实不是直接存一个元素，而往往挂着一条链表（专业点叫"拉链法"或"链地址法"，开散列）。桶里那条链表上，挂着所有"算进这个桶"的键。

于是，一次查找 key 的流程是：算哈希 → 取模 → 定位到桶 → 在桶的链表里，用"等于比较"从左到右找匹配的键。

我把这两步到底"在你插入那一刻发生了什么"再用大白话过一遍，因为这里藏着 unordered_* 对 key 一大堆要求的根源：

第一步，哈希。hash(key) 返回一个 size_t（无符号整数，通常 64 位或 32 位，取决于平台）。这一步要求 key 能算成整数——这就是模板第二个参数 Hash 存在的意义。对 string、int 这些，标准库帮你写好了；对自定义类型，得你自己写（后面那节专门讲，这里是伏笔）。

第二步，取模定位。把哈希值对"当前桶的个数"取模，bucket_index = hash(key) % bucket_count。这一步决定了 key 去哪一号桶。因为取模的结果只落在 [0, bucket_count)，所以桶数组的下标不会越界。

第三步，冲突处理。哈希值的空间通常极大（比如 2⁶⁴ 种可能），而桶的数量有限（比如几百或几千），所以一定会发生"不同的 key 算进同一个桶"——这就是哈希冲突。比如两个 key 的哈希值取模后都得到 3，那 key1 和 key2 都进 3 号桶。桶里那条链就把它们按插入顺序挨个串起来。到这里，你该明白为什么 unordered 一定还需要一个"等值比较"了——当桶里有一串键时，必须用 == 一个一个比对，才能确认到底哪一个才是你要找的。 这就是模板第三个参数 Pred 存在的意义。哈希负责"粗定位"，等值负责"精确命中"，两者缺一不可。

为什么平均是 O(1)？ 因为只要桶的数量足够多、哈希函数散列得够均匀，绝大多数桶里就只有一个（或很少几个）元素。这时候查找基本就是"算哈希 + 直接进桶"两步,链表的遍历往往一趟就结束了，跟总数据量 N 无关——这就是 O(1) 的来源。你可以理解为：大部分时候我们一次就抓到目标，根本不需要像红黑树那样一路比较下来。

我想再帮你把这个"平均"二字说得更精确一点，因为它决定你后面怎么解读性能。「平均 O(1)」指的是：在哈希函数散列得够好、负载因子受控的前提下，平均下来，一次查找要探索的"桶内链表元素个数"是一个常数（期望值），与 N 无关。注意，这是一个概率意义上的平均，而不是"每次都是 O(1)"。它不保证任何单次查找最坏只需要常数时间——恰恰相反，最坏情况可以差到难以想象（下面就说）。

为什么又说是"最坏 O(n)"？ 因为如果哈希函数写得糟糕（比如所有键都算到同一个桶），或者故意构造一堆会哈希到同一个桶的键，那么数据会全部堆在一条链表里，查找就变成"遍历一条 N 长的链表"，复杂度退化成 O(n)。这就是哈希冲突的代价。

那怎么办？哈希表靠两个手段对抗冲突：一是让桶多一点、散列均匀一点；二是监测一个叫负载因子（load factor）的量。负载因子 = 元素总数 ÷ 桶的数量。当它超过某个阈值（unordered_* 默认约 1.0）时，容器会自动扩容并 rehash——申请更大的桶数组，再把老元素重新计算桶下标搬过去，让桶重新"空"起来。这也是为什么上面说元素变多时遍历顺序会变。

rehash 这个词值得单独强调，因为它是理解哈希表动态行为的关键。rehash 中的 re 是英文前缀"重新"，hash 是"哈希定位"，合起来就是"重新计算哈希、重新分桶"。当元素数量超过"当前桶数 × 负载因子阈值"时，容器就会触发一次 rehash：申请一个新的大数组作为桶，然后遍历所有旧元素，用新桶数重新算一遍 %，把每个元素搬家到新桶里。这次搬家的开销是 O(n)，但它不常发生，均摊到每次插入上，平均代价依然接近 O(1)——这就是所谓的摊还分析（amortized），像 vector 扩容那样，"平时快、偶尔大动干戈，平均下来还是快"。

再补一层更"底层"的直觉：哈希表的桶往往不止是一片数组，而是一片数组 + 每个桶挂着一条链表（或者一棵更小的平衡树）。标准库里不同的实现做法不一样：libstdc++（GCC）经典实现是"桶是单链表头指针的数组"；MSVC 用"桶内再套一个链表（甚至自 C++17 起某些版本用红黑树节点）"来做冲突元素再组织。这些实现细节你不必背，你真正要吸收的是那个不变的抽象：哈希负责散步、数组负责定位、桶解决冲突、负载因子驱动 rehash。四件事就构成了哈希表这一切。

所以请把这句结论刻在脑子里（这是全文最重要的考点）：

unordered 容器的查找是"平均 O(1)、最坏 O(n)"。正是因为存在哈希冲突和退化的可能，它才需要在哈希之外额外要求一个"等于比较"来精确匹配，也才需要"合理设计哈希函数"来尽量摊平冲突。 换句话说，优雅的平均 O(1) 是有前提的：一个好的哈希函数加一个容量合理的桶数组。

我们来用代码实测一下"负载因子"和"桶数"这些底层指标是什么用的。这几个接口平时不太用，但拿来观察哈希表内部非常直观：

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us;
    us.reserve(100);   // 提前开好 100 个桶的容量，避免反复 rehash（属于 Hash Policy 接口）
 
    for (int i = 0; i < 50; ++i)
        us.insert(i);
 
    cout << "元素个数 size      = " << us.size()   << endl;  // 50
    cout << "桶的个数 bucket_count = " << us.bucket_count() << endl; // 至少100
    cout << "负载因子 load_factor = " << us.load_factor() << endl;  // 50/100 = 0.5
    cout << "最大负载因子 max_load_factor = " << us.max_load_factor() << endl; // 默认1.0
    return 0;
}

bucket_count() 返回桶数、load_factor() 返回当前实际负载因子，reserve(n) 则是"预留至少这么多桶"——当我们能预估数据量时先 reserve，能显著减少扩容时的搬运开销，这是 unordered 容器在大量插入时的一条性能建议。

这节我还想补一个亲手观察 rehash 全过程的实验，它能帮你把"遍历顺序为什么变"和"负载因子为什么是 1.0"这两件事瞬间钉死在记忆里。思路很简单：每插入一个元素，就打印当前的桶数和负载因子，你会亲眼看到"桶数突然翻倍、负载因子被拉回 0.5 附近"的那一刻：

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us;
    cout << "初始: 桶数=" << us.bucket_count()
         << "  max_load= " << us.max_load_factor() << endl;
 
    for (int i = 0; i < 20; ++i) {
        us.insert(i);
        // 只在桶数变化时打印，让你只看"扩容触发点"
        static size_t last = 0;
        if (us.bucket_count() != last) {
            last = us.bucket_count();
            cout << "插入" << i + 1 << "个后: 桶数=" << last
                 << "  load=" << us.load_factor() << endl;
        }
    }
    return 0;
}

你运行它会发现：桶数不是一步到位，而是随着元素增多、在某次插入时陡然翻倍，同时 load_factor 被压回低值。这正是"负载因子突破阈值 → rehash 扩容 → 负载因子回落"的活教材。你也顺带明白了为什么 reserve 值得用——它让你一次性在数据还很小时就把桶开够，避开中途那几次 O(n) 的搬家。

最后，关于桶，还有一个容易被忽略但面试爱考的接口：bucket(key) 和 bucket_size(i)。前者告诉你"某个键当前待在几号桶"，后者告诉你"某号桶里挂着几个元素"。它们让你能直观看到"哪些键撞在了一起"：

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main()
{
    unordered_set<int> us;
    for (int i = 0; i < 10; ++i)
        us.insert(i * 7);    // 刻意用一堆数验证分桶
 
    for (int i = 0; i < 10; ++i) {
        int key = i * 7;
        cout << "键 " << key << " 落在 " << us.bucket(key) << " 号桶" << endl;
    }
    cout << "桶总数: " << us.bucket_count() << endl;
    return 0;
}

bucket(key) 返回的正是 hash(key) % bucket_count 的结果，你在输出里会看到不同的键被打散到不同桶（也可能偶尔撞桶）。这个接口就是"哈希表原理"的直接观测窗口。

性能对比：set 和 unordered_set 实测

光说不练假把式。前面的原理，我们用一段真实的性能对比程序来验证——这就是课件里那个经典实验的完整可运行版本。它对一百万个数，分别用 set 和 unordered_set 做批量插入、查找、删除，用 clock() 计时看谁快：

#include <iostream>
#include <unordered_set>
#include <set>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
 
int main()
{
    const size_t N = 1000000;         // 数据规模：100万
    set<int> s;
    unordered_set<int> us;
    vector<int> v;
    v.reserve(N);
 
    srand((unsigned)time(0));
    for (size_t i = 0; i < N; ++i)
        v.push_back(rand() + (int)i); // rand()+i 让重复相对少一些
 
    // 统计 set 的插入耗时
    size_t b1 = clock();
    for (auto e : v) s.insert(e);
    size_t e1 = clock();
    cout << "set insert: " << e1 - b1 << "ms" << endl;
 
    // 统计 unordered_set 的插入耗时（先 reserve 避免扩容）
    us.reserve(N);
    size_t b2 = clock();
    for (auto e : v) us.insert(e);
    size_t e2 = clock();
    cout << "unordered_set insert: " << e2 - b2 << "ms" << endl;
 
    // 统计查找命中数，同时各计时
    int m1 = 0, m2 = 0;
    size_t b3 = clock();
    for (auto e : v) if (s.find(e) != s.end()) ++m1;
    size_t e3 = clock();
    cout << "set find: " << e3 - b3 << "ms, 命中 " << m1 << endl;
 
    size_t b4 = clock();
    for (auto e : v) if (us.find(e) != us.end()) ++m2;
    size_t e4 = clock();
    cout << "unordered_set find: " << e4 - b4 << "ms, 命中 " << m2 << endl;
 
    // 各删除耗时
    size_t b5 = clock();
    for (auto e : v) s.erase(e);
    size_t e5 = clock();
    cout << "set erase: " << e5 - b5 << "ms" << endl;
 
    size_t b6 = clock();
    for (auto e : v) us.erase(e);
    size_t e6 = clock();
    cout << "unordered_set erase: " << e6 - b6 << "ms" << endl;
 
    cout << "set/size=" << s.size() << " unordered/size=" << us.size() << endl;
    return 0;
}

在你自己的机器上跑一下，通常的结果是：unordered_set 的插入、查找、删除明显比 set 快，尤其查找，差距可能是数倍。这就很直观地验证了 O(1) 与 O(logN) 在百万级数据上的差别。当然这个差距会受编译器、哈希函数质量、以及数据是否"命中哈希冲突区"影响，但方向是一致的。

注意我用它来和 set 对比的是同样一套增删查，接口和语义完全一致——唯一的区别就是底层结构，这正是"set 和 unordered_set 高度相似、只差这三处"的最好例证。

不过，为了让这篇足够"彻底正确"，我必须诚实地把这段实测背后的四个隐藏条件也讲清楚，不然你换个环境就可能得出完全相反的结论，然后回来骂这篇文章。这四个条件是：

第一，测量方法有噪声。 clock() 测的是 CPU 时间，但在 Debug（不优化）模式下，两个容器都慢到失真；而 Release（开 -O2 / /O2 优化）模式下，差距才真正拉开。实际工程里你遇到的是优化后的结果。而且 clock() 的精度有限，数据量到百万级才有意义。

第二，unordered_set 我特意 reserve(N) 了。 如果不 reserve，插入过程中的 rehash 会带来额外开销，差距会缩小；当然即便如此，它在大多数实现下通常仍不慢于 set。这点我想强调的是：给 unordered 预留容量，是把它的优势兑现出来的前提之一（对应原理节的摊还分析）。

第三，"有序数据"这个场景会让 set 更没负担、让 unordered 更吃亏。 当数据本身是有序的（比如 i 从 0 到 N 递增），红黑树插入会频繁触发旋转但仍保持 O(logN)；哈希表的 hash(int) 对递增的 int 可能算得很"聚拢"（取决于实现），桶分布未必均匀。所以如果你把数据换成 v.push_back(i)（完全有序），你看到的差距可能缩小甚至不一致——这时候更要回归到"平均"和"具体实现"来理解，别指望一个数字放之四海皆准。

第四，内存和缓存的隐形代价。 哈希表里元素真正被 index 到数组的位置是随机的，访问时 cache（CPU 高速缓存）命中率通常比红黑树更低；红黑树在树高只有 20 层时，节点在内存里分布也未必连续。说到底，常数因子（cache locality、分配次数、指针跳转）在真实世界里会和"理论复杂度"打架。这就是为什么我反复说"平均 O(1)"——它描述的是渐进复杂度，而不是每次跑都必然更快的绝对值。

所以这段实测的正确打开方式是：它验证了『在海量、随机、已 reserve 的典型用例如词频统计、按 ID 查表』下，unordered 明显快于 set』，而不要把它读成『unordered 在任何情况下都快』。 完整、诚实的结论放到最后一节选型里统一给你。

自定义类型：哈希函数与等值比较

内置类型和 std::string 用起来很省心，因为标准库给它们写好了 hash<Key> 的特化和 operator==。但你自己定一个结构体时，麻烦就来了：std::hash<MyType> 默认没有实现，MyType 默认也没有 operator==。

先看一个"什么都不做、直接编译报错"的例子，你体会一下缺了啥：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
 
struct Person {   // 自定义类型
    string name;
    int    age;
    // 注意：这里既没有 operator==，也没有给 hash<Person> 特化
};
 
int main()
{
    unordered_set<Person> s;  // 编译报错：无法使用 hash<Person>，且 Person 没有 operator==
    s.insert({"张三", 25});
    return 0;
}

这段代码是编译不过的。报错会指向"找不到 hash<Person> 的定义"和"Person 不支持等于比较"。而这，就对应我们前面反复强调的哈希表两大要求：要能哈希、要能相等比较。这也再次印证：unordered 容器对 key 的要求，本质就是哈希表的要求。

在给出两条解决路径之前，我想先回答一个从这节开头就该回答的问题：为什么标准库不给我的结构体自动生成哈希和等值？ 原因有二：第一，标准库根本"看不见"你的结构体，hash<Person> 这种模板特化只有在你显式告诉它"Person 该怎么算哈希"时才知道；第二，更关键的是，"Person 怎么算相等、怎么算哈希"在工程上并没有唯一的正确答案——你是按"name+age"判等，还是只按"身份证号 id"判等？不同业务含义不同，标准库不可能替你拿主意。这正是 C++"把决策权留给用户"的一贯风格。

怎么解决？有两条路，任选其一。

方案一：给 std::hash 写特化，并定义 operator==

给 std::hash<Person> 做模板特化（template specialization），同时在 Person 里定义 operator==。这样 unordered_set<Person> 的默认参数 hash<Key> 和 equal_to<Key> 就能直接用了。

"模板特化"这个词听起来吓人，其实意思很简单：std::hash<X> 是一个"按 X 的类型算哈希"的类模板，你只对它其中的一种（X=Person）给出专门的实现，其余类型照旧走默认/其他特化。写法就是 namespace std { template<> struct hash<Person> {...}; }，template<> 表示"这里不是再定义一个通用模板，而是给某个具体类型定制一份"。

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
 
struct Person {
    string name;
    int    age;
 
    // 提供等值比较：名字相同且年龄相同，视为同一个 Person
    bool operator==(const Person& other) const
    {
        return name == other.name && age == other.age;
    }
};
 
// 定义在自己的命名空间里，对哈希做特化
namespace std {
template <>
struct hash<Person> {           // std::hash 的 Person 特化
    size_t operator()(const Person& p) const
    {
        // 把 name 的哈希和 age 做一次组合，得到一个整数作为 Person 的哈希
        size_t h = hash<string>()(p.name);
        return h ^ (size_t)p.age;   // 用异或把 age 掺进来
    }
};
}
 
int main()
{
    unordered_set<Person> s;
    s.insert({"张三", 25});
    if (s.find({"张三", 25}) != s.end())
        cout << "找到了张三年纪25" << endl;  // 会打印
    if (s.find({"张三", 30}) == s.end())
        cout << "没找到张三年纪30" << endl;  // 会打印
    cout << "size = " << s.size() << endl;  // 1
    return 0;
}

说明两点。其一，特化 std::hash<Person> 的语法是 template<> struct hash<Person> { size_t operator()(...) const { ... } };，返回值类型 size_t（无符号整数）是最标准的，因为它就是哈希值。其二，h ^ p.age 这种"拼接"只是示意，工程上更好的做法是用成熟的组合公式（比如 h = h * 31 + age）以减少冲突，你只要理解"把各字段的信息汇总成一个整数"即可。

既然提到了"更成熟的组合公式"，我在这里把工程上最主流、最稳妥的哈希组合技巧给你，因为它是把"示意代码"升级为"可上生产代码"的关键一步。

最经典的组合器是 Boost 库的 boost::hash_combine，其核心公式是（借助 WebSearch 核实过的 Boost 公开实现）：

seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);

这里的 0x9e3779b9 不是随便挑的数字——它是黄金分割比 φ≈1.618… 的小数部分转换为 32 位二进制的一个近似值。之所以选它，是因为这个常数的位模式能起到"搅拌器"的作用：当你把一个新的哈希值 value 掺进累积的 seed 时，这个常数配合"左移 6 位 + 右移 2 位的位打散"，能把不同字段的哈希尽量均匀地混合，避免两个字段算出来刚好抵消、或者换来换去得到相同的总哈希。^（异或）保证输入的每一位都对结果有影响，+（加法）的进位则进一步打散位模式。整套操作叫"哈希组合（hash combine）"。这个公式很长一段时间也是 Boost 的实际实现，你在网上几乎任何讲"自定义哈希"的专业资料里都能看到它。

我们在不依赖 Boost 的前提下，可以自己写一个同样思路的 hash_combine 工具函数，然后让 Person 的哈希去用它，这样比 h ^ age 这种简陋方案抗冲突性好得多：

#include <iostream>
#include <string>
#include <cstddef>
#include <unordered_set>
using namespace std;
 
// 自己实现一个 boost 风格的哈希组合器：
// seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
inline void hash_combine(size_t& seed, size_t value)
{
    seed ^= value + 0x9e3779b9u + (seed << 6) + (seed >> 2);
}
 
struct Point {
    int x, y, z;
    bool operator==(const Point& o) const { return x==o.x && y==o.y && z==o.z; }
};
 
namespace std {
template <>
struct hash<Point> {
    size_t operator()(const Point& p) const
    {
        size_t seed = 0;
        hash_combine(seed, hash<int>()(p.x));
        hash_combine(seed, hash<int>()(p.y));
        hash_combine(seed, hash<int>()(p.z));
        return seed;
    }
};
}
 
int main()
{
    unordered_set<Point> pts;
    pts.insert({1, 2, 3});
    if (pts.find({1, 2, 3}) != pts.end())
        cout << "找到点 (1,2,3)" << endl;   // 会打印
    cout << "size = " << pts.size() << endl; // 1
    return 0;
}

注意这个 hash_combine 有一个你不到千分之一的概率会踩、但踩到就崩溃的坑：(seed << 6) 在有符号类型的负数左移上是未定义行为，所以我们这里用了 size_t（无符号）并传入 size_t 类型的值，安全得多。这也是为什么行业标准实现总是让 seed 走无符号路径。

这里还顺带引出一个重要事实，值得明确标注为"实现相关"而非标准保证：标准库并没有为 std::pair / std::tuple 保证提供 std::hash 特化（C++11 标准不要求；直到 C++ 的后续演进也没有把 pair/tuple 的 hash 纳入标准要求）。所以像 unordered_map<std::pair<int,int>, int> 这种写法，在很多编译器上能编过、在另一些上用惯常方式却编不过，行为不一致。如果你想以 pair/tuple 为键但又不想踩这个坑，最稳妥的做法是：定义一个自定义结构体（里面放两个字段），像 Point 那样自己提供 operator== 和 hash 特化；如果非得用 pair，就用下面方案二的方式显式传入自定义的哈希和等值仿函数。

方案二：不去动 std::hash，自己传一个哈希仿函数

如果你不喜欢污染 std 命名空间（特化 std::hash 需要在 std 里写，很多人不太喜欢），更解耦的写法是：自定义一个"哈希函数对象"，作为第二个模板参数传进去，第三个参数再传自定义的"等于比较函数对象"。

这里先解释一下"仿函数（functor）"这个词，它是理解方案二的关键。仿函数就是一个重载了 operator() 的类对象——它长得像个类，但用起来像函数：PersonHash h; h(p);。标准库的哈希要求就是"给我一个 operator()(const Key&) const 返回 size_t 的对象"，std::hash<Key> 本身就是这样一类仿函数。你传自己的仿函数进去，只是换了一个实现，接口约定完全一样。所以方案二和方案一的本质区别只有一个：一个去修改 std::hash<Key> 这个"默认实现"，一个在旁边另起炉灶。

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
 
struct Person {
    string name;
    int    age;
};
 
// 自定义哈希仿函数：只要能这样调用并返回一个 size_t 即可
struct PersonHash {
    size_t operator()(const Person& p) const
    {
        return std::hash<string>()(p.name) ^ (size_t)p.age;
    }
};
 
// 自定义等值比较仿函数：返回 bool，判断两个 Person 是否相等
struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const
    {
        return a.name == b.name && a.age == b.age;
    }
};
 
int main()
{
    // 把两个仿函数作为类型传入模板的第二、第三个参数
    unordered_set<Person, PersonHash, PersonEqual> s;
    s.insert({"李四", 30});
    if (s.find({"李四", 30}) != s.end())
        cout << "找到了" << endl;   // 会打印
    cout << "size = " << s.size() << endl; // 1
    return 0;
}

在给出最终建议之前，我还想补一个方案二独有的"现代写法"——它正好把"可传任意可调用对象"这个特性发挥到极致。自 C++14 起，如果只是想临时用一次、又不想写两个具名结构体，可以借助泛型 lambda（generic lambda，即参数写 auto 的 lambda）配合 decltype 把仿函数写得更内联，并在声明容器时把闭包实例作为构造参数传进去：

#include <iostream>
#include <string>
#include <functional>
#include <unordered_set>
using namespace std;
 
struct Item {
    string id;
    int    code;
};
 
// 自定义哈希仿函数（经典具名写法，最清晰易读）
struct ItemHash {
    size_t operator()(const Item& v) const {
        return std::hash<string>()(v.id) ^ (size_t)v.code;
    }
};
 
// 自定义等值仿函数
struct ItemEqual {
    bool operator()(const Item& a, const Item& b) const {
        return a.id == b.id && a.code == b.code;
    }
};
 
int main()
{
    unordered_set<Item, ItemHash, ItemEqual> s1; // 具名仿函数版
    s1.insert({"A1", 1});
 
    // —— C++14 泛型 lambda 版 ——
    // 不写具名 struct，直接内联两个可调用对象当作类型
    auto h  = [](const auto& v) -> size_t {
        return std::hash<string>()(v.id) ^ (size_t)v.code;
    };
    auto eq = [](const auto& a, const auto& b) {
        return a.id == b.id && a.code == b.code;
    };
    // 构造时必须把仿函数闭包实例也传进去，0 表示用默认初始桶数
    unordered_set<Item, decltype(h), decltype(eq)> s2(0, h, eq);
    s2.insert({"A2", 2});
 
    if (s2.find({"A2", 2}) != s2.end())
        cout << "找到了 A2" << endl;                 // 会打印
    cout << "s1.size = " << s1.size()
         << ", s2.size = " << s2.size() << endl;     // 1, 1
    return 0;
}

不过我要提醒：泛型 lambda 写法里 decltype(h) / decltype(eq) 这类类型名很难读，报错信息也晦涩得多，而且必须记得在构造容器时把 h、eq 传进去。所以大多数工程场景，两个具名 struct 仿函数依然是更好读、更好维护的选择。

两条路都能跑通，怎么选？我的建议是：如果这个自定义类型确实经常被当 Key 用，用方案一（给 std::hash 特化）最省心，以后写 unordered_set<Person> 就是一行。方案二更灵活（同一个 Person 可以按不同的字段定义不同哈希/相等的组合），但每次声明容器都要带上一长串模板参数，稍有啰嗦。两个方案都值得掌握。

再补充一点方案二的实际价值：当你需要对同一个自定义类型、按不同字段定义不同的哈希与等值组合时，方案二让"每个容器各带一套独立的仿函数"成为可能——这是方案一做不到的，也是具名仿函数方案二最重要的优势所在。

这里再强调一个容易被忽略的"坑中之坑"：哈希相等和逻辑相等必须一致。上面例子里，Person 的逻辑相等是"名字和年龄都相同"，哈希也必须做到"相等的两个人，哈希值一定相同"——比如你按 name 和 age 组合哈希，那两个 {"张三",25} 算出同样的值，没问题。但如果你搞反了（比如哈希只算 name，相等却要求连 age 一样），就会出现"明明相等的键哈希到了不同的桶，然后 find 死活找不到"这种极其隐蔽的 bug。准则就一条：逻辑上相等的 key，哈希函数必须给它们算出一模一样的哈希值。

我想用一个完整的错误演示，让你彻底看清这条"一致性"准则为什么是生死线。下面这个例子，哈希函数和等值比较"打架"了：

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
 
struct Person {
    string name;
    int    age;
};
 
// 故意的错误：这里只把 name 拿去算哈希，完全忽略 age
struct BadHash {
    size_t operator()(const Person& p) const
    {
        return std::hash<string>()(p.name);   // 只算 name
    }
};
 
// 但等值判断又要求 name 和 age 都得相同
struct GoodEqual {
    bool operator()(const Person& a, const Person& b) const
    {
        return a.name == b.name && a.age == b.age;
    }
};
 
int main()
{
    unordered_set<Person, BadHash, GoodEqual> s;
    s.insert({"张三", 25});
    s.insert({"张三", 30});   // 和上面的张三 name 一样，但 age 不同
 
    // 两个不同的 Person（age 不同）因哈希只看 name，会撞进同一个桶。
    // 但等值又判断它们不相等，所以它们都能被插进去。
    cout << "size = " << s.size() << endl; // 2
 
    // 但更糟的问题在这：因为 BadHash 只看 name，而 GoodEqual 要求 age 也相等，
    // "张三,30" 这种本应存在的人也永远搜不到匹配————这其实是等值判定更严的情形。
    // 反过来的错误更致命：哈希忽略了一个字段，而相等也用同样的子集判断，
    // 会让"s.size() 变小"（不同的键被误判相等）。
    return 0;
}

上面这个例子的价值不在于"它能不能跑"，而在于它把两种典型的"一致性错误"都曝光在你眼前：一种是哈希比等值更"宽"（哈希忽略的字段、等值却比）——导致 key 大量撞桶，性能退化；另一种是哈希和等值用的字段子集不一致，可能导致本该区分的键被合并（容器 size 不符合预期）或者查找漏配。无论哪种，都是极难定位的隐蔽 bug。标准里关于这条准则有一个正式的称呼叫 相等性自反性 + 一致的哈希约定，你要记住的只有一句话：当作相等的两个键，哈希必须相同；绝不要在一个坐标里用 name、在另一个坐标里把 age 也算进去。

unordered 的哈希相关接口

课件在收尾部分专门列出了 unordered_* 的"Buckets 和 Hash policy"两类接口，并提醒"日常使用不需要太关注，等学了哈希表底层再回看，就一目了然"。现在我们已经把底层讲透了，正好回来看这两套接口，你会发现它们每一个都在前面原理节里露过脸，再无悬念。

第一套是 Buckets（桶）相关接口，直接对应"哈希表内部那一片桶数组"。它们让你能窥探容器的内部布局：

• bucket_count()：当前桶的个数，即数组长度。
• bucket_size(size_t n)：第 n 号桶里挂的元素个数。
• bucket(const key_type& k)：键 k 当前算到了哪一号桶。
• begin(n) / end(n)：访问第 n 号桶内部元素范围的起始/结束迭代器。

第二套是 Hash Policy（哈希策略）相关接口，对应"负载因子"和"扩容"这套动态管理机制：

• load_factor()：当前负载因子（元素数 / 桶数）。
• max_load_factor() / max_load_factor(float z)：读/写"触发扩容的负载因子阈值"。默认大约是 1.0，你可以手动调低或调高。调低让容器更"稀"（桶多，更快但更耗内存）；调高让容器更"挤"（省内存，但更长链、更慢）。
• rehash(n)：手动触发一次重散列，把桶数调整到"至少 n 个桶且满足负载因子约束"。适合在你知道数据量大、且想主动避开扩容高峰时使用。
• reserve(n)：预留至少能装下 n 个元素、且不超出 max_load_factor 的桶数。它本质上就是 rehash(ceil(n / max_load_factor)) 的便捷封装，是"大量插入前提前开桶"的最常用接口。

连同前面原理节和实测节，这两套接口的真实场景是：平时你基本用不到；但当你要做"海量插入前的性能优化"（reserve）或"排查为什么那么慢"（看 load_factor、bucket_size 是否偏高）时，它们是你唯一的观察与干预手段。 一旦看懂底层，这些接口就像阿拉伯数字一样自然，不需要死记。

再给你一个能一次性把两套接口都串起来的综合实验，用 unordered_map<string,int> 展示"预分配、读负载、看分桶、手动 rehash"的完整流程：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main()
{
    unordered_map<string, int> m;
 
    // reserve：提前预估要存 64 个键，让它把桶开够，避免中途 rehash
    m.reserve(64);
 
    cout << "预分配后 桶数=" << m.bucket_count()
         << " 最大负载=" << m.max_load_factor() << endl;
 
    // 插入 20 个键
    for (int i = 0; i < 20; ++i)
        m["key" + to_string(i)] = i * 10;
 
    cout << "size=" << m.size()
         << " 当前负载=" << m.load_factor() << endl;
 
    // 看某个特定键分到的桶
    cout << "\"key15\" 落在 桶 " << m.bucket("key15") << endl;
 
    // 手动 rehash 到至少 128 个桶
    m.rehash(128);
    cout << "rehash 后 桶数=" << m.bucket_count()
         << " 负载=" << m.load_factor() << endl;
 
    // 手动调高最大负载因子（更省内存，但一次查找的链变长）
    m.max_load_factor(2.0f);
    cout << "调高后 max_load_factor=" << m.max_load_factor() << endl;
    return 0;
}

你会发现：reserve(64) 后桶数跟着翻到能容纳 64 个元素的最小 2 的幂（具体数值和实现有关，你只需理解"桶数≥64/负载上限"）；插入 20 个后因为没超过阈值，不会触发 rehash，负载维持在较低水平；rehash(128) 会把桶数加大；改 max_load_factor 则只是改了约束，并不会立刻重排（只有下一次需要扩容时才会生效，这是它的语义）。这一套下来，Buckets 和 Hash policy 两组接口在你眼里就彻底透明了。

何时选 unordered_map，何时选 map

学到这里，问题自然浮上来：那到底该用哪个？我给你几条决策依据。

• 需要频繁查找、并且键≈数据量巨大、又不需要有序遍历：优先 unordered_map / unordered_set。查得快、插入快，这是它的主场。典型如缓存、去重、词频统计、按 ID 精确查找。这是最常见的场景。
• 需要按顺序遍历、范围查询（比如"找所有在 [a, b] 之间的键"）、取最小/最大：只能用 map / set。红黑树天然有序，支持这类操作；unordered 根本做不到。
• 自定义类型的 Key 没有现成的哈希和等值：如果你懒得为它写哈希+等值，又需要有序，那用 map / set（只需 operator<）反而更省事。
• 担心最坏情况退化、对性能稳定性要求极高：红黑树稳定 O(logN)，无论数据多刁钻都不会崩；而哈希表在最坏（糟糕的哈希或恶意构造的冲突数据）下可能退化到 O(n)。实时性要求苛刻的场景，map 更稳。
• 键本身保证唯一（比如已经去重过的 ID 列表）：也仍要选，因为 unordered 照样承担"去重复检查"，只是你心理上把它当哈希查找用就对了。反过来说，如果同一个键可能反复出现、你又想全保留，那就上 unordered_multiset / unordered_multimap。但注意——和 multimap 一样，operator[] 在 unordered_multimap 上是不能用的（因为一个键对应多个值，无意义），要取全部值得用 equal_range。

关于 operator[] 在 multi 版上不可用、以及 equal_range 怎么取全部，值得补一段直观的代码，因为这是选型时很容易撞上的点：

#include <iostream>
#include <unordered_multimap>
#include <string>
using namespace std;
 
int main()
{
    unordered_multimap<string, int> m;
    m.insert({"score", 90});
    m.insert({"score", 80});
    m.insert({"score", 95});
    m.insert({"name", 1});
 
    // 一个键对应多个值：取出 score 的全部值
    auto [lo, hi] = m.equal_range("score");   // 返回 pair<iterator,iterator>
    cout << "score 有多少个值: " << m.count("score") << endl;
    for (auto it = lo; it != hi; ++it)
        cout << it->second << " ";            // 90 80 95
    cout << endl;
 
    // 注释掉的这行是理解不了的写法，跑不了：
    // m["score"];   // 错误：unordered_multimap 没有 operator[]，一个键对应多个值无法取引用
    return 0;
}

equal_range(k) 返回一个 pair，first 指向 k 的第一个匹配，second 指向最后一个匹配的"下一个位置"，中间的迭代区间正好包住 k 的所有值。这是多值容器取全部的标准姿势。

做个简单总结，方便你按需决策：

顺便说一句取舍的哲学：map 用一点 O(logN) 的成本，换来了有序和稳定；unordered_map 用"平均 O(1)"的高性能，换走了有序、丢掉了最坏情况的保证。天下没有免费的午餐——所谓快，往往是拿别的特性换来的。想清楚你真正在意什么，选择自然就出来了。

最后，我再把选型这条线往外推一步，回答几个"看起来都是 unordered 也不太对"的进阶问题，避免你从一个极端走到另一个极端：

当数据量很小（比如几百上千）时，别急着上 unordered。 这时 O(1) 和 O(logN) 的实际差距几乎可以忽略，而哈希函数的常数开销、unordered_* 背后那个数组加链表的更复杂的布局，可能让它反而比 vector 加 map 更慢。很多公司内部的代码规范会规定"小集合用 vector 遍历 / 用 map"，原因正在于此。

当你"必须要稳定、可预测的延迟"时，unordered 的 rehash 是需要警惕的。 因为 rehash 是 O(n) 的突发操作，在某些实时系统（游戏引擎的某些热路径、金融高频、音频处理）里，这种偶发的"性能尖刺"是不可接受的。这类系统往往要么在一开始就用 reserve 把桶开够、彻底禁掉运行期 rehash，要么干脆上红黑树。

关于"哈希洪灾（hash flooding）"这个安全话题，值得被你知晓。 因为如果服务端用 unordered_map<string,...> 存用户可控的字符串，而该标准库实现对 string 的哈希没有随机化种子，那么恶意用户就能精心构造一组"哈希全部相同"的字符串，把所有键塞进同一个桶，让每次操作退化成 O(n)，从而发起拒绝服务攻击。这是哈希表最坏情况在现代安全语境下的真实投影。对策通常有两个：标准库的随机化种子（很多实现默认已开启），以及在代码层面避免用未加盐的哈希处理不可信输入。这个话题比较深入，但你至少要知道"最坏 O(n)"在现实里是可以被人为引爆的。

顺带一提，如果本篇之后你对"到底谁是哈希表的稳妥替身"感兴趣，C++ 社区还有一个方向叫 开放寻址法（open addressing）哈希表（元素直接存在桶数组里、冲突时线性/平方探测），很多高性能库（如 absl::flat_hash_map、robin_hood）用此法换取更好的缓存局部性。标准库的 unordered_* 在不同实现对冲突通常用链地址法或其变体。这属于更内核的话题，本篇点到为止——你只需理解，"平均 O(1)"对上位实现细节并非唯一答案，但抽象不变量（哈希、桶、冲突、负载因子、rehash、一致性准则）放之四海而皆准。

回到开头的那个问题。这套 unordered 容器，是靠哈希函数加一张"分桶"的表格，把查找从"一路比较"缩短成"定位即得"，换来了平均 O(1) 的惊人速度。但这速度有两个前提：一个散列均匀的哈希函数，和一组容量合理的桶，否则冲突会把 O(1) 拖回 O(n)。它给我们三点启发：绝不要依赖迭代顺序；自定义类型上 unordered_* 要自备哈希和等值；而在海量精确查询的场景里，它几乎总是比红黑树更快。现在，你可以放心地把那些"只查不改、又海量、又不在乎顺序"的数据，交给 unordered_map 了。