1. 无序容器的定位C11 引入了四个基于哈希表的无序容器std::unordered_set —— 不重复元素的集合无序std::unordered_multiset —— 允许重复元素的集合无序std::unordered_map —— 键值对键不重复无序std::unordered_multimap —— 键值对键可重复无序今天介绍最常用的 unordered_set 和 unordered_map。2. 头文件和声明#include unordered_set // unordered_set, unordered_multiset #include unordered_map // unordered_map, unordered_multimap声明对象std::unordered_setint uset; // 存放 int 的无序集合 std::unordered_mapstd::string, int umap; // string → int 的无序映射与 set/map 不同的是不需要指定比较器因为没有排序但可以指定哈希函数和键相等判定。3. unordered_set 的基本操作3.1 插入元素std::unordered_setint uset; uset.insert(10); uset.insert(20); uset.insert(10); // 重复不会插入 uset.emplace(30); // 原地构造insert 也返回 pairiterator, boolsecond 表示是否成功插入。3.2 查找元素if (uset.find(20) ! uset.end()) { std::cout 找到了 20\n; } if (uset.count(10)) { std::cout 10 存在\n; }count 要么返回 0 要么 1。3.3 删除元素uset.erase(20); // 按键值删除 auto it uset.find(30); if (it ! uset.end()) uset.erase(it); // 按迭代器删除 uset.clear();3.4 遍历for (const auto x : uset) { std::cout x ; } // 或用迭代器 for (auto it uset.begin(); it ! uset.end(); it) { std::cout *it ; }注意 遍历顺序是无规律的与插入顺序无关也绝不是排序顺序。千万不要依赖遍历顺序。4. unordered_map 的基本操作unordered_map 存储的是 std::pairconst Key, T 的键值对用法与 map 非常相似只是内部无序。4.1 插入和修改std::unordered_mapstd::string, double price; price.insert({apple, 3.5}); price.insert(std::make_pair(banana, 2.0)); price.emplace(orange, 4.2); // 使用 []若键不存在则插入默认值然后赋值 price[grape] 5.5; price[apple] 3.8; // 修改已存在键的值[] 的隐藏风险如果访问一个不存在的键umap[unknown] 会插入一个 {unknown, 0} 的默认值对。若只想查询而不插入务必使用 find 或 at。std::cout price.at(apple) \n; // 存在输出 3.8 // price.at(pear); // 不存在抛出 std::out_of_range 异常 auto it price.find(banana); if (it ! price.end()) { std::cout it-second \n; }4.2 遍历for (const auto p : price) { std::cout p.first : p.second \n; } // C17 结构化绑定 for (const auto [name, price] : price) { std::cout name costs price \n; }同样遍历顺序是无序的。5. 哈希表性能的关键哈希函数与负载因子5.1 什么是哈希函数哈希表将键通过哈希函数映射到一个整数值然后根据这个值决定元素存放在哪个“桶”里。理想情况下每个桶中的元素很少查找就是 O(1)。C 标准库为内置类型int, std::string, 指针等提供了默认的哈希函数。但如果你的键是自定义类型就需要自己提供哈希函数并可能提供相等比较函数。5.2 自定义类型作为键假设我们有一个 Point 结构体struct Point { int x, y; bool operator(const Point other) const { return x other.x y other.y; } };我们需要为它写一个哈希函数struct PointHash { size_t operator()(const Point p) const { // 一种简单的组合哈希方法 return std::hashint()(p.x) ^ (std::hashint()(p.y) 1); } };然后声明容器std::unordered_setPoint, PointHash points; points.insert({1, 2});对于 unordered_map需要指定键的哈希和相等比较值不需要std::unordered_mapPoint, std::string, PointHash pointNames; pointNames[{0, 0}] 原点;若等号运算符有特殊逻辑也可以自定义相等仿函数作为第二个模板参数在哈希之后。5.3 桶与接口哈希表由一系列“桶”组成每个桶是一个链表或后继结构。标准库提供了一些探查哈希表状态的接口std::unordered_mapstd::string, int umap; // ... 插入数据 std::cout 桶的个数: umap.bucket_count() \n; std::cout 负载因子: umap.load_factor() ( umap.size() / umap.bucket_count() )\n; std::cout 最大负载因子: umap.max_load_factor() \n; // 遍历所有桶 for (size_t i 0; i umap.bucket_count(); i) { std::cout 桶 i 有 umap.bucket_size(i) 个元素:; for (auto it umap.begin(i); it ! umap.end(i); it) { std::cout it-first; } std::cout \n; }5.4 重哈希与性能负载因子 元素个数 / 桶的数量。当 load_factor() max_load_factor() 时容器会自动进行重哈希rehash分配更多的桶并重新分配所有元素。这是一个较重的操作O(n)。你可以在插入大量元素前使用 reserve(n) 预留桶的数量避免反复重哈希。umap.reserve(1000); // 为至少 1000 个元素预留足够的桶也可以直接调用 rehash(n) 手动设置桶的最小数量。最佳实践已知要插入 N 个元素时调用 reserve(N)或在插入前预估数量避免多次重哈希。6. unordered_map / unordered_set vs map / set特性 set / map unordered_set / unordered_map底层数据结构 红黑树平衡 BST 哈希表顺序性 元素始终有序 无序查找复杂度 O(log n) 平均 O(1)最坏 O(n)插入/删除复杂度 O(log n) 平均 O(1)最坏 O(n)遍历顺序 按键升序或自定义 无序可能随插入而变内存占用 较小每个节点两个指针颜色 较大桶数组 链表节点迭代器失效 插入永不失效删除仅当前失效 重哈希时所有迭代器失效删除仅当前失效适用场景 需要顺序遍历、范围查询 单纯快速查找、无需排序选用建议如果需要字典序输出或范围查找比如找出所有大于某值的键用 map/set。如果只需要“键是否存在”或“快速获取值”且不关心顺序用 unordered_map/unordered_set。7. 常见陷阱和注意事项遍历顺序不可靠不要写出依赖遍历顺序的代码。即使在你的编译器和平台下看起来有序换一个环境就可能完全不同。[] 的无意插入umap[key] 如果键不存在会直接插入一个默认值。若只是读取用 at() 或 find()。重哈希使迭代器失效在执行插入操作后可能导致重哈希所有之前的迭代器都会失效。如果需要在遍历过程中插入最好先插入到临时容器再合并或者先 reserve 足够空间防止重哈希。自定义类型的哈希函数必须高效且均匀差的哈希函数会导致大量碰撞退化成链表性能从 O(1) 掉到 O(n)。应尽量保证哈希值分布均匀。unordered_multiset/unordered_multimap 没有 []因为键不唯一无法确定修改哪个值。它们支持 equal_range 获取同一键的范围。不要依赖 bucket 的顺序桶的迭代顺序同样是未定义的不要假设元素会按某种特定规律存放在桶中。8. 性能优化小贴士提前 reserve如果已知大致元素数量使用 reserve() 可以有效避免多次重哈希大幅提升插入性能。选择合适的 max_load_factor默认通常为 1.0。如果内存充裕且希望减少碰撞可以调低 max_load_factor(0.75)。用 emplace 代替 insert减少临时对象的构造与拷贝。对于小规模数据map/set 有时可能比 unordered_map/unordered_set 更快因为哈希表的内存分配和哈希计算本身也有开销。具体可实测。9. 小结unordered_set 和 unordered_map 是基于哈希表的无序关联容器提供平均 O(1) 的查找/插入/删除。使用 #include unordered_set 和 #include unordered_map。不保证元素顺序遍历顺序无意义且可能变化。可以通过自定义哈希函数和相等比较来支持自定义键类型。掌握 find、at、[]、insert、erase、reserve、load_factor 等关键接口。注意 [] 的自动插入行为和重哈希导致的迭代器失效问题。