std::unordered_map是哈希表查找平均 O(1)比std::map的 O(log n) 更快代价是元素没有顺序而且最坏情况会退化成 O(n)。这两个特点都不是玄学全部由它的结构决定一个桶数组bucket array加每个桶上挂的链外加一个装载因子load factor阈值控制何时扩容。这篇把结构、rehash、自定义哈希、遍历顺序这四件事一次讲清最后给一张与std::map的选型表。1. 引子map 已经 O(log n) 了为什么还要哈希表std::map的 O(log n) 听起来很快但它的「log n 次比较」每次都要跟着一个指针跳到堆上另一个地方100 万个元素的树高约 20也就是 20 次大概率缓存不命中cache miss的随机内存访问。哈希表的期望值是一次哈希计算 一次定位理想情况下访问的内存位置更集中常数因子明显更小。代价也很明确哈希表不保证顺序而且最坏情况是 O(n)。选择哪一个取决于你的场景是「要顺序和范围查询」还是「纯粹的点查」。官方文档std::unordered_map — cppreference 官方文档std::unordered_set — cppreference2. 结构桶数组 链以及三个关键数字unordered_map 的结构一个桶数组bucket array 每个桶挂一条链 具体用「链地址法」还是「开放寻址」标准不规定 —— 属于实现定义implementation-defined 桶数组bucket_count() 7 定位公式桶号 hash(key) % bucket_count ┌───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ └─┬─┴─┬─┴───┴─┬─┴─┬─┴───┴───┘ │ │ │ │ v v v v [a1] [b2][c3] │ v [d4] -- 冲突collision多个 key 落进同一个桶查找要沿这条链往下走 三个关键数字 size() 元素个数 bucket_count() 桶的个数 load_factor() size() / bucket_count() 「平均每个桶挂几个元素」 max_load_factor() 阈值默认 1.0超过就扩容rehash 查找一个 key 的三步 ① 算哈希 h hash(key) 与元素个数无关 ② 定位桶 i h % bucket_count() 一次取址 ③ 沿桶内的链找 key 相等的节点 期望 O(1)最坏 O(桶内节点数) O(n) 「期望 O(1)」成立的前提是哈希把 key 均匀撒进各桶每条链都短。 第 4 节会用实测演示所有 key 挤进同一个桶时会发生什么。// hash_basics.cpp — 编译: g -stdc17 -Wall -O2 hash_basics.cpp -o hash_basics #include iomanip #include iostream #include string #include unordered_map int main() { std::unordered_mapstd::string, int m; std::cout std::fixed std::setprecision(2); std::cout initial: buckets m.bucket_count() load m.load_factor() max_load m.max_load_factor() \n; for (int i 0; i 1000; i) { m.emplace(key std::to_string(i), i); // 注意这是「不存在才插入」 if (i 0 || i 10 || i 100 || i 999) { std::cout size m.size() buckets m.bucket_count() load m.load_factor() \n; } } std::cout bucket(key0) m.bucket(key0) \n; std::cout bucket(key999) m.bucket(key999) \n; return 0; }initial: buckets1 load0.00 max_load1.00 size1 buckets13 load0.08 size11 buckets13 load0.85 size101 buckets127 load0.80 size1000 buckets1109 load0.90 bucket(key0) 891 bucket(key999) 508输出里有几个值得记住的事实空表的bucket_count()是 1不是 0此时load_factor()定义为 0。libstdc 的默认构造函数只给一个桶第一次插入就立刻扩容到 13。桶数不会一个个长而是跳到质数序列上1 → 13 → 127 → 1109这是 libstdc 的实现选择用质数模运算让分布更均匀。标准只保证「够用」不保证任何具体数字所以永远不要把自己的逻辑绑在bucket_count()的数值上。load_factor始终控制在max_load_factor默认 1.0以内。size11时 11/13 ≈ 0.85下一个元素就会触发扩容。接口含义默认 / 典型值bucket_count()桶的个数空表为 1之后按质数增长1 → 13 → 127 → 1109…load_factor()size() / bucket_count()空表记为 0max_load_factor()允许的最大装载因子超过就 rehash1.0bucket(key)某个 key 落在哪个桶实现定义hash_function()取当前哈希函数对象std::hashKeykey_eq()取当前相等谓词std::equal_toKey官方文档std::unordered_map::load_factor — cppreference 官方文档std::unordered_map::max_load_factor — cppreference 官方文档std::unordered_map::bucket_count — cppreference3. rehash什么时候发生代价是什么rehash 的触发与代价 插入前检查 size() 1 max_load_factor() * bucket_count() ? │ ├── 否 ── 直接挂到对应的桶上均摊 O(1) │ └── 是 ── rehash申请一个更大的桶数组把「每一个」已有元素重新分桶 旧桶 0...6 ──┐ [a][b][c][d] │ 逐个取出、按新桶数重算 h % N、挂到新桶 │ 代价 O(size)这一次插入不是 O(1) 新桶 0...12 ─┘ → 所有迭代器失效 → 但引用和指针仍然有效节点本身没挪窝见第 6 节实测 实测往空表里塞 10000 个元素中途桶数组变了 10 次。 先 reserve(10000) 再塞则是 0 次。// hash_reserve.cpp — 编译: g -stdc17 -Wall -O2 hash_reserve.cpp -o hash_reserve #include cstddef #include iostream #include unordered_map constexpr int N 10000; int main() { { std::unordered_mapint, int m; std::size_t rehashes 0; std::size_t buckets m.bucket_count(); for (int i 0; i N; i) { m.emplace(i, i); if (m.bucket_count() ! buckets) { // 桶数组变了 发生了一次 rehash rehashes; buckets m.bucket_count(); } } std::cout no reserve : size m.size() buckets m.bucket_count() rehashes rehashes \n; } { std::unordered_mapint, int m; m.reserve(N); // 一次性把桶开够 std::size_t rehashes 0; std::size_t buckets m.bucket_count(); for (int i 0; i N; i) { m.emplace(i, i); if (m.bucket_count() ! buckets) { rehashes; buckets m.bucket_count(); } } std::cout with reserve: size m.size() buckets m.bucket_count() rehashes rehashes \n; } return 0; }no reserve : size10000 buckets10273 rehashes10 with reserve: size10000 buckets10273 rehashes0两种写法的最终桶数一样10273差别全在过程不reserve要经历 10 次「申请新桶数组 把当时所有元素重新分桶」每一次都是 O(当前元素数) 的突发耗时reserve之后是 0 次插入全程均摊 O(1)。这就是判断「要不要 reserve」的唯一标准你事先知不知道大概要装多少元素。两个细节reserve(n)保证的是「n个元素不会触发 rehash」而不是「桶数就是 n」。它按ceil(n / max_load_factor)选一个够用的桶数本例max_load_factor1.0选到的质数是 10273。如果先max_load_factor(0.5)再reserve(10000)桶会被开得更大约 2 万个换更短的链、更快的查找。rehash(n)是更底层的版本直接指定桶数下界。日常用reserve就够rehash少数场景比如你已经知道分布、想手工调桶数才用。官方文档std::unordered_map::reserve — cppreference 官方文档std::unordered_map::rehash — cppreference4. 最坏情况 O(n)为什么标准不敢保证 O(1)标准对unordered_map查找的措辞是「平均常数时间最坏线性时间」。这不是免责声明而是数学事实只要哈希把 n 个 key 全映射到同一个桶查找就退化成在一条长度为 n 的链上线性扫描。用一个计数相等谓词把这个过程量出来// hash_worst_case.cpp — 编译: g -stdc17 -Wall -O2 hash_worst_case.cpp -o hash_worst_case #include cstddef #include functional #include iostream #include unordered_map struct CountEq { inline static std::size_t comparisons 0; // 统计相等比较次数 bool operator()(int a, int b) const { comparisons; return a b; } }; struct GoodHash { std::size_t operator()(int v) const noexcept { return std::hashint{}(v); } }; // 只用于演示最坏情况常数哈希所有 key 都落进同一个桶 struct BadHash { std::size_t operator()(int) const noexcept { return 42; } }; constexpr int N 1000; int main() { { std::unordered_mapint, int, GoodHash, CountEq m; m.reserve(N); for (int i 0; i N; i) m.emplace(i, i); CountEq::comparisons 0; const bool found m.find(0) ! m.end(); // 0 是最早插入的在链尾 std::cout good hash: found found comparisons CountEq::comparisons \n; } { std::unordered_mapint, int, BadHash, CountEq m; m.reserve(N); for (int i 0; i N; i) m.emplace(i, i); CountEq::comparisons 0; const bool found m.find(0) ! m.end(); std::cout bad hash: found found comparisons CountEq::comparisons \n; std::cout bad hash: all m.size() keys in bucket m.bucket(999) (bucket_count m.bucket_count() )\n; } return 0; }good hash: found1 comparisons1 bad hash: found1 comparisons1000 bad hash: all 1000 keys in bucket 42 (bucket_count1031)同样查 1000 个元素里的一个好哈希比较 1 次坏哈希比较 1000 次。两者都是「合法的哈希表实现」因为BadHash满足标准对哈希函数的唯一硬性要求相等的 key 必须给出相等的哈希值常数哈希当然满足。它只是把性能毁掉了。实际拿到 O(n) 的路径有三条退化成 O(n) 的原因具体场景后果哈希函数质量差手写的混合算法有规律如hx hy对(1,2)和(2,1)同值大量冲突链变长输入分布有规律key 全是同余数、指针全部 8 字节对齐、字符串都同前缀桶分布倾斜逐位模运算被利用攻击者构造出全部落在同一桶的 keyhash flooding / DoS单次请求退化成 O(n²)这就是为什么std::hashstd::string之类不能是恒等映射也是为什么标准只敢承诺「平均」。想避免 hash flooding要么换一个带随机种子的哈希要么在不可信输入上用std::map它保证 O(log n) 上界。官方文档std::hash — cppreference列出了对哈希函数的硬性要求相等则同哈希以及标准为哪些类型提供了特化。 官方文档std::unordered_map::find — cppreference复杂度一栏写的就是「平均常数最坏与 size 成线性」。5. 自定义 keyoperator 加一个哈希函数用自定义类型当 key 需要两样东西一个相等谓词默认std::equal_toKey也就是operator和一个哈希函数默认std::hashKey标准只为基础类型和少数标准类型提供了特化。// hash_custom_key.cpp — 编译: g -stdc17 -Wall -O2 hash_custom_key.cpp -o hash_custom_key #include cstddef #include functional #include iostream #include string #include unordered_map #include unordered_set enum class Color { red, green, blue }; // 枚举做 key 不需要手写哈希特化 struct Point { int x 0; int y 0; bool operator(const Point other) const { // 相等谓词的依据 return x other.x y other.y; } }; struct PointHash { std::size_t operator()(const Point p) const noexcept { const std::size_t hx std::hashint{}(p.x); const std::size_t hy std::hashint{}(p.y); return hx ^ (hy 1); // 简单混合够用但不算均匀 } }; int main() { std::unordered_setColor seen{Color::red, Color::green, Color::red}; std::cout distinct colors seen.size() \n; std::cout has green? (seen.count(Color::green) ! 0) \n; std::cout hash(Color::red) std::hashColor{}(Color::red) (等于底层整数值的哈希)\n; std::unordered_mapPoint, std::string, PointHash labels; labels.emplace(Point{1, 2}, a); labels.emplace(Point{3, 4}, b); labels.emplace(Point{1, 2}, c); // 已存在不插入也不覆盖 std::cout point count labels.size() \n; std::cout labels[{1,2}] labels.at(Point{1, 2}) \n; return 0; }distinct colors 2 has green? 1 hash(Color::red) 0 (等于底层整数值的哈希) point count 2 labels[{1,2}] a两条实测结论枚举类型可以直接当 key不用手写哈希特化。在 gcc 13.2.0libstdc下std::unordered_setColor直接可用std::hashColor{}(Color::red)返回 0——哈希的就是底层整数值。所以真正需要手写哈希的场景是自定义 struct / class。labels.size() 2且[{1,2}] a第二次emplace同一个Point被正确识别为「已存在」而不插入说明operator和PointHash这条链路是通的。写自定义哈希必须守住两条相等的对象必须有相同的哈希值否则同一个 key 会被分到不同桶查找直接失效。PointHash只读x、y而operator也只比x、y两边一致是对的。分布要尽量均匀。上面用的是最简单的hx ^ (hy 1)它对Point{1,2}和Point{2,4}会算出同一个值1 ^ 4 2 ^ 8并不但这个式子的确容易产生规律性碰撞。生产代码里更稳妥的做法是依次混合h hx; h ^ hy 0x9e3779b9 (h 6) (h 2);。把两个分量真正搅在一起。官方文档std::hash — cppreference哈希函数的唯一硬性要求相等 ⇒ 同哈希与Hash具名要求。 官方文档std::equal_to — cppreferenceunordered_map的默认相等谓词逻辑就是operator。6. 与 map 一样的坑加上一个反直觉细节unordered_map::operator[]的副作用与map完全一致找不到 key 就插入一个值初始化的元素。这一条在unordered_map上同样容易踩因为「查一个计数器」看起来人畜无害。另外unordered_map的遍历顺序不确定不同实现不同同一实现下插入/删除也会改变它。把顺序写进测试断言就会得到时灵时不灵的 flaky 测试。// hash_order.cpp — 编译: g -stdc17 -Wall -O2 hash_order.cpp -o hash_order #include algorithm #include cstddef #include iostream #include memory #include string #include unordered_map #include vector int main() { std::unordered_mapstd::string, int m{{alice, 1}, {bob, 2}, {carol, 3}}; std::cout iteration order (implementation-defined):; for (const auto [key, value] : m) std::cout key; std::cout \n; // 要可复现的输出自己排序 std::vectorstd::string keys; keys.reserve(m.size()); for (const auto [key, value] : m) keys.push_back(key); std::sort(keys.begin(), keys.end()); std::cout sorted (stable for tests):; for (const std::string key : keys) std::cout key; std::cout \n; std::cout size before m.size() \n; const int missing m[dave]; // 反例不要这么写读一下就插进去了 std::cout m[\dave\] missing size after m.size() \n; // rehash 让全部迭代器失效但引用和指针仍然有效 std::unordered_mapstd::string, int t{{x, 1}}; int ref t.begin()-second; int* const address_before std::addressof(ref); const std::size_t buckets_before t.bucket_count(); t.reserve(10000); // 触发 rehash std::cout bucket_count changed? (t.bucket_count() ! buckets_before) \n; std::cout node kept its address? (address_before std::addressof(ref)) value ref \n; return 0; }iteration order (implementation-defined): ~~ sorted (stable for tests): alice bob carol size before 3 m[dave] 0 size after 4 bucket_count changed? 1 node kept its address? 1 value1实测输出里遍历顺序是carol bob alice这个顺序是 libstdc 当前实现的产物别依赖它所以这里用~~占位排序之后才是稳定的alice bob carol。三个结论现象实测证据正确做法遍历顺序不确定插入顺序是 alice/bob/carol遍历得到 carol/bob/alice要稳定输出就std::sort要语义上的有序就用std::mapoperator[]会插入size从 3 变成 4只读用find/at/containsC20rehash 使迭代器全部失效bucket_count变了rehash 之后重新取begin()rehash不使引用和指针失效节点地址node kept its address? 1值仍可读可以长期持有T/T*但别存迭代器最后一条是unordered_map上最反直觉、也最实用的细节标准明确保证「引用和指针只在该元素被 erase 时失效」。也就是说 rehash 只搬桶、不搬节点节点是独立分配的所以int ref一直有效但迭代器是「桶指针 节点指针」的组合桶一换迭代器就废了。需要长期记住「某个 value 在哪」时存指针或引用别存迭代器。官方文档std::unordered_map · 迭代器失效 — cppreference明确写了「rehash 使所有迭代器失效但引用和指针不受影响」。 官方文档std::unordered_map::operator[] — cppreference与 map 同款语义——不存在就插入。7. 完整示例词频统计加 Top-K词频统计是unordered_map的经典用法Top-K 则是它「顺序不确定」这个缺点的标准解法把结果倒进 vector自己排序输出就完全可复现。// word_count.cpp — 编译: g -stdc17 -Wall -O2 word_count.cpp -o word_count #include algorithm #include cctype #include cstddef #include iostream #include string #include unordered_map #include utility #include vector std::vectorstd::string split_words(const std::string text) { std::vectorstd::string words; std::string current; for (char ch : text) { const unsigned char uch static_castunsigned char(ch); // 避免对负值调用 ctype if (std::isalpha(uch) ! 0) { current.push_back(static_castchar(std::tolower(uch))); } else if (!current.empty()) { words.push_back(current); current.clear(); } } if (!current.empty()) words.push_back(current); return words; } int main() { const std::string text the quick brown fox jumps over the lazy dog, the dog barks and the fox runs; std::unordered_mapstd::string, int freq; freq.reserve(16); // 词表大小已知先开够桶 for (const std::string word : split_words(text)) freq[word]; // 这里 operator[] 正合适 std::vectorstd::pairstd::string, int items(freq.begin(), freq.end()); std::sort(items.begin(), items.end(), [](const auto a, const auto b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; // 同频次按字典序输出才可复现 }); std::cout distinct words freq.size() \n; std::cout top 3:; for (std::size_t i 0; i 3 i items.size(); i) { std::cout items[i].first items[i].second; } std::cout \n; return 0; }distinct words 11 top 3: the4 dog2 fox2这段代码把这篇的要点用了一遍词表不大不小、只做点查unordered_map正合适reserve(16)把 rehash 扼杀在开始前freq[word]是operator[]正当的用法要的就是「不存在则初始化」最后std::sort把不确定的遍历顺序收敛成确定输出dog和fox都是 2 次靠第二排序键字典序才保证每次运行结果一致。8. unordered_map 与 map 选型表维度std::map红黑树std::unordered_map哈希表元素顺序按 key 有序无序遍历顺序实现定义查找 / 插入 / 删除O(log n)保证平均 O(1)最坏 O(n)范围查询支持lower_bound/upper_bound/equal_range不支持顺序无意义中序遍历即排序是否每元素内存每个节点 3 个指针 颜色位约 3240 字节节点 12 个指针 桶数组桶数组有额外内存迭代器失效只有被删元素失效rehash 使全部迭代器失效引用/指针仍有效遍历的缓存表现树节点散落每次跳转大概率 miss桶数组连续、桶内链较短通常更好最坏情况可控性O(log n) 上界不可被输入击穿可被构造输入打到 O(n)hash flooding典型场景有序输出、范围查询、不可信输入、需要稳定顺序纯点查、词频统计、缓存索引、去重一句话的选型口径要顺序或范围 →map只要点查且追求常数因子 →unordered_map输入不可信又想保证上界 → 回到map。另外元素总量很小几十个以内时vector 线性查找往往比两者都快因为它的常数因子最低、且完全连续。官方文档容器库 — cppreference所有容器的复杂度与失效规则总表选型时对照一眼。 官方文档C Core Guidelines「SL: Containers」— isocpp.github.io容器选型的指导思想来源。9. 延伸阅读std::unordered_map — cppreference接口全貌重点看成员函数表里bucket_*系列和开头的复杂度说明。std::unordered_map::load_factor — cppreference 与 max_load_factor装载因子的定义与它如何控制 rehash 时机。std::unordered_map::reserve — cppreference注意它保证的是「不 rehash」而不是「桶数等于 n」。std::hash — cppreference标准为哪些类型提供了哈希、对自定义类型写特化要满足什么。std::unordered_set — cppreference去重场景的对应容器接口与unordered_map对称。本知识库内的相关篇目《C map 与 unordered_map 怎么选底层结构、复杂度与决策流程》 —— std::map 和 std::unordered_map 接口几乎一样底层却完全不同。《map / set 完全指南红黑树与有序容器》 —— 讲透 std::map / std::set 背后那棵红黑树——有序和 O(log n) 是同一套结构的《list 与 forward_list链表真的比 vector 快吗》 —— 用计数分配器和实测耗时把 std::list / std::forward_list 的真实开销算清楚10. 一句话总结std::unordered_map/unordered_set是「桶数组 链」的哈希表load_factor超过max_load_factor默认 1.0就触发rehash把全部元素重新分桶。所以预先知道规模就reserve实测塞 10000 个元素不 reserve 要 rehash 10 次reserve 之后 0 次查找「平均 O(1)、最坏 O(n)」不是免责声明坏哈希实测要比较 1000 次而好哈希只要 1 次自定义 struct 当 key 要同时给operator和哈希函数枚举类型在 libstdc 下可以直接当 key不必写特化operator[]依旧「找不到就插入默认值」遍历顺序依旧不能依赖但有一个反直觉的好消息rehash 会让所有迭代器失效却不会让引用和指针失效所以要长期记住某个 value存指针而不是迭代器。