std::map和std::unordered_map都属于关联容器associative containeroperator[]、find、insert、erase、size这些接口几乎一模一样很多时候把类型名换掉程序照样跑。正因为「换一下就能编译」选型才容易被忽略直到某个热点函数慢了十倍才回头查。这篇不重复 API 细节只回答一个工程问题给定一个具体需求红黑树和哈希表我该挑哪个为什么。1. 引子换了个容器热路径快了十倍一个统计日志里错误码出现次数的环节原本用std::mapint, int撑着每来一条日志做一次counts[code]。数据量上去之后这条路径成了瓶颈把类型换成std::unordered_mapint, int别的一个字符没改耗时直接掉了一个数量级。反过来也有翻车的时候有人把一份需要「按 key 有序输出报表」的std::map也换成了std::unordered_map结果报表行序每次跑都不一样冒烟测试直接挂掉。两次都是「换容器」这一个动作一次是收益、一次是事故。差别只在底层数据结构一个是平衡二叉搜索树一个是哈希桶数组。2. 底层结构红黑树 vs 哈希桶先说结论std::map是有序关联容器ordered associative container标准只要求它的行为像一棵平衡二叉搜索树主流实现libstdc / libc / MSVC STL都选了红黑树red-black treestd::unordered_map是无序关联容器unordered associative container标准规定它是「由桶bucket组成的哈希表」。两者在内存里的样子完全不同std::map —— 红黑树每个节点单独堆分配中序遍历即为有序序列 ┌─────────┐ │ 40 (黑) │ └────┬────┘ ┌────────────┴────────────┐ ┌────┴─────┐ ┌──────┴───┐ │ 20 (红) │ │ 60 (红) │ └─┬──────┬─┘ └─┬──────┬─┘ ┌──┘ └──┐ ┌──┘ └──┐ [10] [30] [50] [70] 单节点 ≈ key value 父/左/右 三个指针 颜色位 查找路径 从根一路比较往下跳每跳一次基本是一次随机内存访问 std::unordered_map —— 桶数组 链地址法节点同样是独立堆分配 桶数组连续内存bucket_count 个「链表头」 ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 空 │ 空 │ ● │ 空 │ ● │ 空 │ 空 │ 空 │ └────┴────┴─┬──┴────┴─┬──┴────┴────┴────┘ │ │ ▼ ▼ [20]──►[60] [30]──►[10]──►nullptr 下标 std::hashKey{}(key) % bucket_count 负载因子 load_factor size / bucket_count超过 max_load_factor 就 rehash两个细节值得单独拎出来哈希表不是 O(1) 而是均摊 O(1)。桶数组容量不够时会触发 rehash重建桶数组、所有节点重新挂链这一次操作的代价是 O(n)。摊到每次插入上才是「均摊」。树的 O(log n) 是严格保证哈希的 O(1) 是平均情况。哈希函数写得差大量 key 落进同一个桶unordered_map会退化成链表最坏 O(n)这时它连map都不如。官方文档std::map、std::unordered_map3. 一张大表说清五个维度的差异维度std::mapstd::unordered_map底层结构红黑树平衡 BST哈希表桶数组 链地址法迭代顺序按 key 升序确定不确定随实现、插入顺序、rehash 变化查找平均O(log n)均摊 O(1)查找最坏O(log n)严格保证O(n)哈希退化成链表插入 / 删除平均O(log n)含旋转与变色均摊 O(1)可能触发 rehash对 key 的要求operator或自定义比较器严格弱序std::hash特化 operator每个元素额外开销3 个指针 颜色位64 位下约 32 字节起1 个 next 指针约 8 字节 桶数组均摊份额桶/节点分配模式每节点一次堆分配节点地址分散桶数组连续节点仍是一次堆分配一个缓存局部性差树高约 log₂n 次随机跳转中一次哈希 一次桶内链表走查常数更小迭代器失效insert全部保持有效不 rehash 时保持有效rehash 后全部失效迭代器失效erase只有被删元素失效只有被删元素失效可测试性好遍历顺序确定输出可断言差遍历顺序不确定测试要排序后再比支持的额外操作lower_bound/upper_bound/equal_range无没有顺序没法做范围查询这张表里有两个经常被忽略的维度值得展开说说。第一是内存开销的真实分布。红黑树每个节点固定背三个指针64 位下光指针就是 24 字节再算上颜色位、对齐填充和 key/value 本身一个mapint,int节点往往 32~48 字节。哈希表看起来更省节点只有一个next指针但别忘了那块桶数组bucket_count通常是元素个数的 1~2 倍每个桶槽位就是一个指针这份开销是按容器整体摊的。元素很少时比如只有几十个桶数组的固定占用反而比树更亏这也是为什么小数据量下map经常不输甚至更快。第二是缓存局部性cache locality。树查找要做约 log₂n 次指针跳转每次跳到的新节点在堆上什么位置完全说不准几乎必然是一次 cache miss。哈希表的路径更短一次哈希计算纯 CPU无内存访问、一次桶数组下标定位一段连续内存容易命中缓存、然后桶内链表通常只有一个节点。同样规模下哈希的访存次数更少这才是它快的根本原因不是因为「O(1) 比 O(log n) 高级」。官方文档C Core Guidelines — SL.con: Containers 容器章节选容器时该问自己的问题清单4. 第一个可运行示例有序性是唯一不可替代的能力如果想一句话记住区别std::map的遍历顺序是契约std::unordered_map的遍历顺序是实现细节。// ordered_iteration.cpp — 编译: g -stdc17 -Wall -O2 ordered_iteration.cpp -o demo #include cstdio #include map #include string #include unordered_map int main() { const std::mapstd::string, int scores{{charlie, 3}, {alice, 1}, {bob, 2}}; std::printf(std::map 的遍历顺序保证按 key 升序\n); for (const auto [name, score] : scores) { std::printf( %s %d\n, name.c_str(), score); } const std::unordered_mapstd::string, int hashed{{charlie, 3}, {alice, 1}, {bob, 2}}; std::printf(std::unordered_map 的遍历顺序实现相关别依赖\n); for (const auto [name, score] : hashed) { std::printf( ~~\n, name.c_str(), score); } std::printf(元素个数: %zu两种容器一样\n, hashed.size()); }std::map 的遍历顺序保证按 key 升序 alice 1 bob 2 charlie 3 std::unordered_map 的遍历顺序实现相关别依赖 ~~ ~~ ~~ 元素个数: 3两种容器一样上面unordered_map那三行的内容在同一份编译环境下是稳定的但它不受标准保证换个编译器、加点元素触发一次 rehash、甚至只是插入顺序不同行序都可能变。所以想要「按 key 有序输出」这个语义只能用map或者取出后自己std::sort。顺带一提map还独有lower_bound/upper_bound/equal_range能直接做范围查询比如「统计 key 落在 [100, 200) 的元素个数」。哈希表没有顺序这类需求根本无从谈起。5. 对 key 的要求一个要「小于」一个要「哈希 相等」这是选型时最实际的约束。用自定义类型当 key两种容器的门槛不一样// custom_key.cpp — 编译: g -stdc17 -Wall -O2 custom_key.cpp -o demo #include cstddef #include cstdio #include functional #include map #include string #include unordered_map struct Point { int x{}; int y{}; }; // std::map 只需要「严格弱序」的比较定义 operator bool operator(const Point lhs, const Point rhs) { return lhs.x ! rhs.x ? lhs.x rhs.x : lhs.y rhs.y; } // std::unordered_map 需要相等判断用来区分「同一个 key」和「哈希冲突」 bool operator(const Point lhs, const Point rhs) { return lhs.x rhs.x lhs.y rhs.y; } // std::unordered_map 还需要一个可调用的哈希函数 struct PointHash { std::size_t operator()(const Point p) const noexcept { constexpr std::size_t kMix 0x9e3779b97f4a7c15ULL; // 黄金比例常量用于打散哈希位 const std::size_t hx std::hashint{}(p.x); const std::size_t hy std::hashint{}(p.y); return hx ^ (hy kMix (hx 6) (hx 2)); } }; int main() { std::mapPoint, std::string by_order; by_order[Point{2, 3}] second; by_order[Point{1, 9}] first; const Point smallest by_order.begin()-first; std::printf(std::map 的首个 key (%d, %d)\n, smallest.x, smallest.y); std::unordered_mapPoint, std::string, PointHash by_hash; by_hash[Point{2, 3}] second; by_hash[Point{1, 9}] first; const bool both_found by_hash.find(Point{2, 3}) ! by_hash.end() by_hash.find(Point{1, 9}) ! by_hash.end(); std::printf(std::unordered_map 大小 %zu\n, by_hash.size()); std::printf(两次查找都命中: %s\n, both_found ? 是 : 否); }std::map 的首个 key (1, 9) std::unordered_map 大小 2 两次查找都命中: 是一个容易踩的坑给std::map写比较器时别用。不满足严格弱序strict weak ordering会破坏树的平衡假设轻则元素丢失重则越界崩溃。这条规则在《C sort 与自定义比较器为什么比较器不能用 》里会详细展开这里先记住结论比较器永远返回a b语义的「严格小于」。官方文档std::hash、std::map 的比较器要求6. 实测同一份数据两种容器的插入与查找耗时光看复杂度不够来看真实数字。下面这段基准程序用std::chrono::steady_clock对两种容器做同样的事插入 20 万个打乱顺序的key然后反复查找 10 轮。// map_bench.cpp — 编译: g -stdc17 -O2 -Wall map_bench.cpp -o bench #include chrono #include cstdint #include cstdio #include map #include unordered_map #include vector namespace { constexpr int kKeyCount 200000; // 插入多少个 key constexpr int kLookupRounds 10; // 查找重复多少轮 constexpr std::uint32_t kSeed 123456789u; constexpr std::uint32_t kMul 1664525u; // 线性同余生成器参数 constexpr std::uint32_t kInc 1013904223u; constexpr std::uint32_t kMod 1000000u; // 用线性同余生成「看似随机」的 key避免顺序插入给红黑树带来的偏置 std::vectorint makeKeys() { std::vectorint keys; keys.reserve(kKeyCount); std::uint32_t x kSeed; for (int i 0; i kKeyCount; i) { x x * kMul kInc; keys.push_back(static_castint(x % kMod)); } return keys; } template typename Map void bench(const char* name, const std::vectorint keys) { Map table; const auto t0 std::chrono::steady_clock::now(); for (int k : keys) { table[k] 1; } const auto t1 std::chrono::steady_clock::now(); long long hits 0; for (int round 0; round kLookupRounds; round) { for (int k : keys) { if (table.find(k) ! table.end()) { hits; } } } const auto t2 std::chrono::steady_clock::now(); long long key_sum 0; for (const auto entry : table) { key_sum entry.first; } const long long insert_ms std::chrono::duration_caststd::chrono::milliseconds(t1 - t0).count(); const long long lookup_ms std::chrono::duration_caststd::chrono::milliseconds(t2 - t1).count(); std::printf([%s]\n, name); std::printf( 元素个数: %zu\n, table.size()); std::printf( 插入耗时: %lld ms\n, insert_ms); std::printf( 查找耗时: %lld ms\n, lookup_ms); std::printf( 命中次数: %lld\n, hits); std::printf( key 求和: %lld\n, key_sum); } } // namespace int main() { const std::vectorint keys makeKeys(); std::printf( %d 个 key每个 key 查找 %d 轮 \n, kKeyCount, kLookupRounds); benchstd::mapint, int(std::map, keys); benchstd::unordered_mapint, int(std::unordered_map, keys); } 200000 个 key每个 key 查找 10 轮 [std::map] 元素个数: 181438 插入耗时: ~~ ms 查找耗时: ~~ ms 命中次数: 2000000 key 求和: 90505798790 [std::unordered_map] 元素个数: 181438 插入耗时: ~~ ms 查找耗时: ~~ ms 命中次数: 2000000 key 求和: 90505798790这段输出里只有耗时被~~盖住了因为绝对耗时依赖在线编译服务的机器负载、优化级别、容器实现同一份代码连跑两次都能差出百分之几十写死一个数字就是在编。要看的是数量级关系实测中unordered_map的插入和查找都只有map的几分之一。剩下三个值都是确定的可以直接当断言用元素个数 18143820 万个 key 里必然有重复线性同余取模到 100 万重复的会被容器合并所以最终元素数小于 20 万。两种容器拿到的是同一批 key个数必须一致。命中次数 2000000所有 key 都插进去了10 轮 × 20 万次查找必然全部命中与机器快慢无关。key 求和 90505798790两种容器装的是同一个 key 集合遍历求和必然相等。「重复 key 合并」这件事也不是小事。如果你要的是保留重复比如日志里同一个错误码出现几次都要记那不是关联容器该干的活应该用std::vectorstd::pairK, V或std::unordered_multimap。想自己看汇编确认「树查找是一串指针跳转」可以用 Compiler Explorer 打开这段代码对比两种容器的find。7. 迭代器失效规则哈希表还有个 rehash 的坑两种容器都承诺「erase只让被删元素的迭代器失效」但在insert上分道扬镳操作std::mapstd::unordered_mapinsert全部迭代器保持有效未触发 rehash → 有效触发 rehash →全部失效erase(it)只有it失效只有it失效指向元素的引用 / 指针insert/erase后均保持有效insert触发 rehash 时引用和指针仍然有效但迭代器失效clear全部失效全部失效bucket_count变化不适用只有rehash/reserve会改变它两个实用推论在unordered_map的insert循环里不要缓存迭代器跨插入使用一次 rehash 就全废了典型表现是段错误或死循环。如果提前知道元素总量先reserve(n)把桶数组一次性撑够可以避免后续 rehash这同时也是个性能优化。unordered_map里「元素地址稳定」是它相对vector/deque的一个隐藏优势insert只动链表指针节点本身不搬家。所以存T*指向 map 里的 value是安全的当然更推荐用std::unique_ptr之类的所有权语义。// safe_erase.cpp — 编译: g -stdc17 -Wall -O2 safe_erase.cpp -o demo #include cstdio #include unordered_map int main() { std::unordered_mapint, int table; table.reserve(64); // 提前撑大桶数组避免后续 rehash 让迭代器失效 for (int i 0; i 10; i) { table.emplace(i, i * i); } const std::size_t buckets_before table.bucket_count(); // erase 返回「下一个有效迭代器」—— 这是遍历中删除的正确姿势 for (auto it table.begin(); it ! table.end();) { if (it-first % 3 0) { it table.erase(it); // 用返回值续上别写 it } else { it; } } std::printf(删除 3 的倍数后大小 %zu\n, table.size()); std::printf(剩余 key: ); // 剩下的 key 只有 1,2,4,5,7,8 六个排序后输出才稳定 for (int k : {1, 2, 4, 5, 7, 8}) { if (table.count(k) ! 0) { std::printf(%d , k); } } std::printf(\n桶数组是否被 rehash 过: %s\n, table.bucket_count() buckets_before ? 没有 : 有); }删除 3 的倍数后大小 6 剩余 key: 1 2 4 5 7 8 桶数组是否被 rehash 过: 没有8. 选型决策流程图把前面所有约束压缩成一张判定图遇到新场景照着走一遍就行┌────────────────────────────────┐ │ 需要按 key 有序遍历 │ │ 需要 lower_bound 范围查询 │ └───────────────┬────────────────┘ 需要 ─────┤───── 不需要 │ │ ▼ ▼ ┌──────────────┐ ┌──────────────────────────┐ │ → std::map │ │ key 有可用的 std::hash │ └──────────────┘ │ 特化 operator 吗 │ └────────────┬─────────────┘ 有 ──────────────┤────────────── 没有 │ │ ▼ ▼ ┌──────────────────────────┐ ┌────────────────────────┐ │ 元素个数大概 1000 │ │ 自己写个 hash混入 key │ │ 或整个生命周期只查几次 │ │ 的所有字段或退回 map │ └────────┬─────────────────┘ └────────────────────────┘ 是 ───┤─── 否 │ │ ▼ ▼ ┌──────────────┐ ┌───────────────────────────────┐ │ → std::map │ │ → std::unordered_map │ │ 常数小、更省事│ │ 记得 reserve(n)别让 rehash │ └──────────────┘ └───────────────────────────────┘ 兜底检查key 的哈希分布是否均匀 · 均匀 → 均摊 O(1)unordered_map 赢 · 大量冲突例如 key 全是同一哈希值的倍数→ 退化成链表 O(n)map 反而稳9. 完整示例一份词频统计两种容器各司其职真实的代码很少「二选一」更常见的是分工统计阶段不需要顺序用unordered_map拿均摊 O(1)出报表阶段需要顺序用map一次性接住。// word_frequency.cpp — 编译: g -stdc17 -Wall -O2 word_frequency.cpp -o demo #include cstdio #include map #include string #include unordered_map #include vector namespace { // 统计阶段的容器只需要「key - 次数」的快速查找不关心顺序 using Counter std::unordered_mapstd::string, int; // 报表阶段的容器需要按字典序输出交给 std::map using Report std::mapstd::string, int; Counter countWords(const std::vectorstd::string words) { Counter counter; counter.reserve(words.size()); // 一次撑够桶数组避免统计过程反复 rehash for (const std::string word : words) { counter[word]; } return counter; } } // namespace int main() { const std::vectorstd::string words{ apple, banana, apple, cherry, banana, apple, date}; std::printf(单词总数: %zu\n, words.size()); const Counter counter countWords(words); // 用迭代器区间构造unordered_map 的无序迭代器照样能灌进有序容器 const Report report(counter.begin(), counter.end()); std::printf(按字典序输出词频报表:\n); for (const auto [word, count] : report) { std::printf( %-8s %d\n, word.c_str(), count); } std::printf(最高频词: %s\n, report.rbegin()-first.c_str()); }单词总数: 7 按字典序输出词频报表: apple 3 banana 2 cherry 1 date 1 最高频词: date注意最后一行report.rbegin()-first因为map有序「取字典序最大的词」只需要反序遍历一个元素O(1) 就能拿到。换成unordered_map就得把全部 key 扫一遍求最大值O(n)。有序性带来的不只是「输出好看」还有一类 O(1) 的极值查询。10. 延伸阅读std::map — cppreference成员函数清单、迭代器失效规则、比较器要求写代码时随手查std::unordered_map — cppreference重点看「Iterator invalidation」和「Bucket interface」两节rehash 的行为都写在这儿std::hash — cppreference自定义类型的哈希特化怎么写标准库内置了哪些特化C Core Guidelines — 容器选型 SL.con为什么默认该用标准容器以及选择时该考虑什么Compiler Explorer想确认「树查找是一串指针跳转、哈希查找是一次算术 一次访存」在这上面看汇编最直观本知识库内的相关篇目《unordered_map / unordered_set 完全指南哈希表、rehash 与自定义哈希》 —— 讲透 std::unordered_map 的哈希表结构——桶数组加链表具体实现由标准库定义《map / set 完全指南红黑树与有序容器》 —— 讲透 std::map / std::set 背后那棵红黑树——有序和 O(log n) 是同一套结构的《list 与 forward_list链表真的比 vector 快吗》 —— 用计数分配器和实测耗时把 std::list / std::forward_list 的真实开销算清楚11. 一句话总结先问「要不要有序」要有序遍历、范围查询、O(1) 求极值就只能std::map不要再看「key 好不好哈希、数据量大不大」规模上去且哈希均匀就用std::unordered_map并记得reserve规模很小或哈希质量存疑时std::map的稳定 O(log n) 反而更省心。