unordered_map / unordered_set
更新时间：2026-08-27。本文是
languages/cpp/主题入门层第 37 篇（存量stl-containers拆解迁入）。unordered_map是哈希表版字典：平均 O(1) 查找，比红黑树map快得多，但失去有序性。"只查不遍历用 unordered，需要有序用 map"——一句口诀背后是两种数据结构的本质差异。
本文要回答的问题
- 哈希表和红黑树差在哪？为什么 unordered 更快？
unordered_map的"平均 O(1)"是什么意思？- map 和 unordered_map 到底怎么选？
一、unordered_map：哈希表版字典
cpp
#include <unordered_map>
#include <unordered_set>
std::unordered_map<std::string, int> u;
u["alice"] = 95;
u["bob"] = 88;
auto it = u.find("alice"); // 平均 O(1)
u.count("alice"); // 0 或 1
std::unordered_set<int> s = {3, 1, 2};
s.insert(5);
s.erase(3);用法和 map 几乎一模一样——接口相同，区别在底层结构和顺序保证：
map / set | unordered_map / unordered_set | |
|---|---|---|
| 底层 | 红黑树 | 哈希表 |
| 查找/插入 | O(log n) | 平均 O(1)，最坏 O(n) |
| 有序性 | 按键有序遍历 | 无序（遍历顺序不保证） |
| 内存 | 树节点（省一点） | 哈希桶（多一块） |
| 适用 | 有序遍历、范围查询 | 纯快速查找 |
二、为什么 unordered 更快
哈希表把键直接算出一个桶位置（hash(key) % bucket_count），一次定位就到，不用像红黑树那样从根节点一路比较 log n 次：
对大数据量（几万、几十万键），O(log n) 和 O(1) 的差距肉眼可见：log₂(100000) ≈ 17 次比较 vs 1 次哈希。所以纯查找场景 unordered 全面占优。
三、"平均 O(1)"的三个字坑
- 哈希函数：好哈希让键均匀分布；哈希函数垃圾（或键故意构造对抗）时，全挤一个桶，退化为 O(n)（查链表）；
- 最坏情况：攻击者可以构造同哈希的键（哈希碰撞攻击），所以安全敏感场景要留意；
- 遍历无序：
unordered_map的遍历顺序由桶布局决定，和插入顺序、键大小都没关系——想按序输出，得先拷到vector再sort。
四、map vs unordered_map 选型
| 需求 | 选谁 |
|---|---|
| 快速查找、插入（量大的字典/缓存） | unordered_map |
| 需要按键有序遍历 | map |
| 范围查询（查"a"到"m"之间的键） | map（树支持范围） |
| 数据量很小（几十个） | 都行，map 稍省内存 |
| 键是自定义结构体 | 都要提供哈希/比较，unordered 稍麻烦 |
经验法则（存量文档的原话）：只查不遍历用 unordered_map；需要有序或范围查询用 map。词频统计、配置文件解析、缓存这类"键查值"场景，unordered 是默认首选。
五、和 C 对比
| 对比项 | C | C++ |
|---|---|---|
| 哈希表 | 手写哈希函数 + 桶数组 | std::unordered_map |
| 有序字典 | 手写树/数组排序 | std::map |
| 哈希碰撞 | 手写处理 | 自动（链地址法） |
| 扩容 | 手动 rehash | 自动 |
C 写哈希表是经典面试题（自己写哈希函数、处理碰撞、rehash），C++ 的 unordered_map 全自动——但理解哈希的原理对判断"什么时候它可能退化"依然必要，原理见 哈希表与冲突处理。
六、与本站主线衔接
- 哈希表、开放寻址 vs 链地址法，见 数据结构：哈希表；
- 下一篇：迭代器与范围 for——容器遍历的统一接口；
- 综合练习 61 篇（单词统计）会同时用到 unordered_map 和 map。
一句话总结
unordered_map/unordered_set 底层是哈希表：平均 O(1) 查找插入，比红黑树 map 快，但遍历无序、内存略多、最坏退化为 O(n)；选型口诀"只查不遍历用 unordered，需要有序或范围查询用 map"；数据量小、键自定义、要排序输出时选 map 更省事。
上一篇：set / map 下一篇：迭代器与范围 for