前言std::map/std::set是有序关联容器ordered associative container底层红黑树操作复杂度稳定在O(log n)。而std::unordered_map/std::unordered_set是 C11 引入的无序关联容器unordered associative container底层哈希表hash table平均复杂度O(1)。很多人会背哈希表快但真正用起来问题不断为什么自定义类型编译不过—— 缺少哈希函数或operator为什么unordered_map的迭代顺序每次运行都不一样为什么um[1000000]在循环里用会慢—— 哈希表扩容rehash为什么unordered_set里元素顺序和插入顺序不同本文把这两个容器的原理、接口、实战套路和常见坑一次讲清。一、底层原理为什么它是无序的1.1 桶bucket与哈希unordered_map内部维护一个桶数组bucket array每个桶挂一条链表或开放寻址。插入一个键k时计算h hash(k)用h % bucket_count()得到桶下标把节点挂到该桶里因为下标由哈希值决定桶内遍历顺序与插入顺序无关所以整个容器遍历出来是乱的。这正是无序的含义它不保证任何顺序也不承诺两次运行顺序一致。bucket[0] - (kapple, v1) bucket[1] - (kcat, v3) - (kbanana, v2) bucket[2] - nullptr bucket[3] - (kdog, v4)1.2 负载因子与扩容负载因子load factor 元素个数 / 桶个数。默认最大负载因子是1.0。当插入导致负载因子超过它容器会申请更大的桶数组通常是下一个质数或约 2 倍重新计算每个元素的桶位置rehash释放旧桶数组这一步是O(n)的且会让所有迭代器失效。这就是循环里反复插入会慢的根源。1.3 unordered_map 与 unordered_set 的关系对比项unordered_mapunordered_set存储内容键值对pairconst Key, T仅键Key元素类型value_typepairconst Key, Tvalue_typeKey典型用途字典、计数、缓存去重、存在性判断operator[]有键不存在则插入无底层结构完全相同完全相同unordered_set可以理解成unordered_map只保留键的特化版本。二、基本用法实战2.1 头文件与声明#include unordered_map #include unordered_set #include string #include iostream int main() { std::unordered_mapstd::string, int score; std::unordered_setint seen; return 0; }模板参数其实有 5 个只是后面几个有默认值template class Key, class T, class Hash std::hashKey, class KeyEqual std::equal_toKey, class Allocator std::allocatorstd::pairconst Key, T class unordered_map;理解这一点后面自定义类型的解法就自然出来了。2.2 插入与访问#include unordered_map #include string #include iostream int main() { std::unordered_mapstd::string, int age; // 方式 1operator[] —— 不存在则默认构造并插入 age[Tom] 18; // 方式 2insert —— 已存在则不覆盖 auto r age.insert({Jerry, 20}); std::cout 插入成功? r.second \n; // 1 r age.insert({Tom, 99}); std::cout 插入成功? r.second \n; // 0Tom 仍是 18 // 方式 3insert_or_assign (C17) —— 存在则覆盖 age.insert_or_assign(Tom, 99); std::cout Tom age[Tom] \n; // 99 // 方式 4emplace —— 原地构造避免临时对象 age.emplace(Spike, 5); // 方式 5try_emplace (C17) —— 只有键不存在才构造值 age.try_emplace(Spike, 100); // 不生效Spike 已存在 for (const auto [name, a] : age) std::cout name - a \n; }insert和emplace的区别值得说清楚emplace直接把参数转发给节点的构造函数理论上省掉一次临时pair的构造。但注意 ——即使插入失败emplace也可能已经构造了对象C17 起的try_emplace才彻底解决这个问题。2.3 查找#include unordered_map #include iostream int main() { std::unordered_mapint, std::string m{{1, one}, {2, two}}; // find —— 返回迭代器找不到返回 end() if (auto it m.find(1); it ! m.end()) std::cout it-first it-second \n; // count —— 返回 0 或 1unordered 容器不允许重复键 std::cout m.count(2) \n; // 1 // contains (C20) #if __cplusplus 202002L std::cout std::boolalpha m.contains(3) \n; // false #endif }重要规律unordered_map的键唯一所以count()只会返回 0 或 1。要判断存在性优先用find/contains不要用operator[]原因见常见坑点。2.4 unordered_set 去重#include unordered_set #include vector #include iostream int main() { std::vectorint v{1, 3, 3, 5, 5, 7, 1}; std::unordered_setint s(v.begin(), v.end()); std::cout 去重后个数: s.size() \n; // 4 for (int x : s) std::cout x ; std::cout \n; // 插入的返回值second 表示是否真的插进去了 auto [it, ok] s.insert(3); std::cout std::boolalpha ok \n; // false已存在 }三、进阶用法3.1 自定义类型作键这是最高频的编译错误来源。要作为unordered_map的键需要两样东西哈希函数能被std::hashKey或自定义Hash调用相等比较operator或自定义KeyEqual#include unordered_map #include iostream #include string struct Point { int x, y; bool operator(const Point o) const { return x o.x y o.y; } }; // 方式 A特化 std::hash namespace std { template struct hashPoint { size_t operator()(const Point p) const noexcept { // 组合两个整数的经典写法 size_t h1 std::hashint{}(p.x); size_t h2 std::hashint{}(p.y); return h1 ^ (h2 0x9e3779b9 (h1 6) (h1 2)); } }; } // namespace std int main() { std::unordered_mapPoint, std::string m; m[Point{1, 2}] A; m[Point{3, 4}] B; std::cout m[Point{1, 2}] \n; // A }方式 B 是传自定义仿函数不污染std命名空间更推荐struct PointHash { size_t operator()(const Point p) const noexcept { return std::hashint{}(p.x) * 31 std::hashint{}(p.y); } }; std::unordered_mapPoint, std::string, PointHash m;3.2 预留空间避免 rehash#include unordered_map #include vector int main() { std::unordered_mapint, int m; // 已知要存 100000 个元素提前预留 m.reserve(100000); // 直接保证能装下 n 个元素而不 rehash // m.rehash(200000); // rehash 是保证至少 n 个桶 std::vectorint data(100000, 1); for (int i 0; i 100000; i) m[i] data[i]; }reserve(n)是最省心的写法它内部会按n / max_load_factor()计算需要的桶数。3.3 遍历时删除#include unordered_map #include iostream int main() { std::unordered_mapint, int m{{1, 1}, {2, 2}, {3, 3}, {4, 4}}; // C11 起 erase 返回下一个迭代器 for (auto it m.begin(); it ! m.end(); ) { if (it-first % 2 0) it m.erase(it); // 正确接收返回值 else it; } for (const auto [k, v] : m) std::cout k ; // 1 3 }3.4 自定义桶迭代可选#include unordered_map #include iostream int main() { std::unordered_mapint, int m; for (int i 0; i 10; i) m[i] i * i; std::cout 桶数: m.bucket_count() \n; std::cout 负载因子: m.load_factor() \n; std::cout 最大负载因子: m.max_load_factor() \n; // 遍历 3 号桶里的元素 for (auto it m.begin(3); it ! m.end(3); it) std::cout it-first ; }四、unordered 与 ordered 容器选型维度unordered_map/unordered_setmap/set底层结构哈希表红黑树查找/插入/删除平均O(1)最坏O(n)稳定O(log n)元素顺序无序不保证按键升序迭代器失效rehash 时全部失效仅被删元素失效需要的能力hash严格弱序范围查询不支持支持lower_bound等内存开销桶数组 节点指针节点指针3 个抗哈希攻击可能退化不会选择建议只做键 → 值的单点查找且键可哈希 → 用unordered_*需要有序遍历、范围查询[a, b)→ 用map/set键类型没有天然哈希比如自定义结构体且不想写哈希函数 → 用map键是int/string且数据量小几十个→ 两者差别不大map反而更省内存常见坑点坑 1用operator[]做只读查找意外插入❌ 错误写法std::unordered_mapstd::string, int m; if (m[missing] 0) { // 偷偷插入了一个 {missing, 0} // ... } std::cout m.size(); // 1不是 0operator[]的语义是不存在就默认构造并插入它永远不是只读的。而且如果T没有默认构造函数直接编译报错。✅ 正确写法if (auto it m.find(missing); it ! m.end() it-second 0) { // ... } std::cout m.size(); // 0干净坑 2rehash 导致迭代器全部失效❌ 错误写法std::unordered_mapint, int m; auto it m.begin(); for (int i 0; i 1000000; i) { m[i] i; // 中途 rehashit 变成野指针 } std::cout it-first; // 未定义行为✅ 正确写法先reserve或者不保存迭代器或者用返回值重新获取。m.reserve(1000000);注意规则差异unordered_map的reserve/rehash会让所有迭代器失效而std::vector的reserve只在扩容时失效。两者别记混。坑 3保存operator[]返回的引用后又插入❌ 错误写法std::unordered_mapint, std::string m; m[1] a; std::string ref m[1]; for (int i 2; i 100; i) m[i] x; // 可能 rehash ref b; // ref 可能已悬空关键点unordered_map的rehash 只让迭代器失效不会让指向元素的引用/指针失效节点本身不移动只是桶指针重排。所以严格来说这个例子在标准下是安全的 —— 但删除元素会让该元素的引用失效std::string ref m[1]; m.erase(1); ref b; // 真的悬空了未定义行为结论引用只在不删除的前提下有效reserve之后更不能想当然。坑 4erase(key)与erase(iterator)混用❌ 错误写法for (auto it m.begin(); it ! m.end(); it) { if (it-second 0) m.erase(it-first); // 用 key 删it 立即失效再 it 是 UB }✅ 正确写法二选一// 写法 1用迭代器版本并接住返回值 for (auto it m.begin(); it ! m.end(); ) { if (it-second 0) it m.erase(it); else it; } // 写法 2先收集 key再统一删除 std::vectorint dead; for (const auto [k, v] : m) if (v 0) dead.push_back(k); for (int k : dead) m.erase(k);C20 还有std::erase_if(m, pred)一步到位std::erase_if(m, [](const auto kv) { return kv.second 0; });坑 5哈希函数写得差退化成链表❌ 错误写法struct BadHash { size_t operator()(const Point p) const { return p.x; } // 忽略 y };如果所有点的x都相同全部落进同一个桶查找复杂度退化为O(n)。✅ 正确写法让哈希值充分混合所有字段。struct GoodHash { size_t operator()(const Point p) const noexcept { size_t h1 std::hashint{}(p.x); size_t h2 std::hashint{}(p.y); return h1 ^ (h2 0x9e3779b9 (h1 6) (h1 2)); } };0x9e3779b9是黄金比例常数用于打散位模式这是boost::hash_combine的经典做法。坑 6哈希函数与operator不一致这是最隐蔽的 bug两个相等的对象哈希值不同或者哈希值相同但不相等。struct Key { int id; std::string name; // 只比较 id bool operator(const Key o) const { return id o.id; } }; struct KeyHash { // 却把 name 也混进哈希 —— 违反契约 size_t operator()(const Key k) const { return std::hashint{}(k.id) ^ std::hashstd::string{}(k.name); } };契约a b必须推出hash(a) hash(b)。反过来哈希相同但不等是允许的叫哈希冲突。上面代码Key{1,a}和Key{1,b}相等却哈希不同会导致插入进去了却查不到的诡异现象。✅ 正确写法哈希只使用参与operator的字段。struct KeyHash { size_t operator()(const Key k) const { return std::hashint{}(k.id); // 只哈希 id } };坑 7std::hash对pair/ 自定义类型没有特化std::unordered_mapstd::pairint,int, int m; // 编译错误标准库不为pair、vector、自定义结构体提供std::hash只有基本类型、string、智能指针等有。必须自己写struct PairHash { size_t operator()(const std::pairint,int p) const noexcept { size_t h1 std::hashint{}(p.first); size_t h2 std::hashint{}(p.second); return h1 ^ (h2 0x9e3779b9 (h1 6) (h1 2)); } }; std::unordered_mapstd::pairint,int, int, PairHash m; // OK坑 8认为迭代顺序等于插入顺序std::unordered_setint s; for (int i 0; i 5; i) s.insert(i); for (int x : s) std::cout x ; // 可能是 4 3 2 1 0也可能别的不要依赖任何顺序。更要命的是不同标准库实现libstdc / MSVC STL / libc结果不同同一实现在不同版本也可能变。需要有序输出就拷进vector排序。std::vectorint v(s.begin(), s.end()); std::sort(v.begin(), v.end());总结主题要点底层桶数组 链表hash % bucket_count定位复杂度平均O(1)最坏O(n)哈希退化顺序无序不可依赖需要顺序请用map/set插入只读查找用find/contains别用operator[]扩容已知规模先reserve否则会不断 rehash失效rehash 让迭代器全部失效引用仍有效除非删除删除it m.erase(it)或用 C20 的erase_if自定义键需hashoperator且两者必须一致一句话记住它unordered_*是用放弃顺序换平均 O(1)的容器。想清楚你是否真的不需要顺序再决定用哪一个。