map用有序树组织元素，unordered_map用哈希表组织元素。二者都能按照键查找值，但复杂度保证、遍历顺序、内存开销和失效规则并不相同。
一、先看红黑树与哈希表
| 对比项 | map | unordered_map |
|---|---|---|
| 常见底层结构 | 平衡搜索树，通常是红黑树 | 哈希表（桶数组 + 节点） |
| 排序性 | 按键有序 | 不保证顺序 |
| 查找、插入、删除 | O(log n) | 平均 O(1)，最坏 O(n) |
| 范围查询 | 支持 | 不适合 |
| 键类型要求 | 提供满足严格弱序的比较器 | 提供匹配的哈希函数和相等判断 |
| 迭代器类别 | 双向迭代器 | 前向迭代器 |
| 插入后的迭代器 | 已有迭代器通常仍有效 | 未重新分桶时有效；重新分桶后失效 |
| 删除后的迭代器 | 只有指向被删除元素的迭代器失效 | 只有指向被删除元素的迭代器失效 |
| 内存特点 | 节点包含父子链接和颜色等信息 | 需要桶数组和节点，开销受桶数量与负载因子影响 |
unordered_map并不保证一定比map更省内存。map的每个节点需要维护树链接；unordered_map除了节点外还需要桶数组，实际占用取决于元素数量、桶数量、负载因子和具体标准库实现。
表中的迭代器规则也要区分引用和指针：unordered_map重新分桶（rehash）时迭代器会失效，但指向元素的引用和指针通常仍然有效；真正删除元素时，指向该元素的迭代器、引用和指针才会失效。
二、哈希表怎样完成查找
1. 键如何定位到桶
unordered_map可以先用哈希函数把键转换为哈希值，再根据桶数量确定目标桶。概念上可以理解为：
key -> hash(key) -> bucket index -> 在桶内比较 key例如常见实现可以通过类似hash(key) % bucket_count的方式定位桶，但标准并没有规定必须使用取模计算。找到目标桶后，还要使用KeyEqual比较键，不能只看哈希值。
自定义键时必须保证：如果KeyEqual(a, b)为true，那么Hash(a)与Hash(b)必须相同；反过来，哈希值相同并不代表两个键一定相等。
2. 什么是哈希冲突？
不同的键可能得到相同哈希值，也可能在映射桶下标后进入同一个桶，这就是哈希冲突。冲突无法彻底避免，因为键的取值空间通常远大于桶的数量。
图中apple和dog最终进入同一个桶。查找时先定位到该桶，再在桶内逐个比较键，因此冲突越集中，桶内查找成本越高。
3. 哈希冲突通常怎样解决？
| 解决方法 | 核心做法 | 优点 | 缺点 |
|---|---|---|---|
| 拉链法（分离链接法） | 每个桶保存一组节点，冲突元素放在同一桶中 | 实现直观；删除简单；能够容纳较多冲突元素 | 节点和指针有额外内存开销；桶内元素过多时查找会退化；缓存局部性较弱 |
| 开放寻址法 | 元素直接保存在槽位数组中；发生冲突后按探测规则寻找下一个位置 | 无链表指针；内存更紧凑；通常更利于缓存 | 对负载因子敏感；探测可能聚集；删除通常需要墓碑标记，处理更复杂 |
标准并没有强制unordered_map必须采用哪一种冲突处理算法。常见标准库实现通常使用桶数组配合节点链，可以把它理解为拉链法，但具体节点组织和桶增长策略属于实现细节，面试时不要回答成标准的硬性规定。
三、负载因子与桶管理
1. 负载因子衡量哈希表有多拥挤
负载因子等于“元素数量 ÷ 桶数量”，表示平均每个桶承载多少个元素。
- 负载因子较高：桶利用率高，但冲突增多，查找可能变慢。
- 负载因子较低：冲突较少，但空桶增多，会占用更多内存。
可以使用load_factor()查看当前值，使用max_load_factor()获取或设置允许的最大值。
2. 负载因子过高时会自动扩桶
插入元素后，如果负载因子超过限制，容器会增加桶数量，并把已有元素重新分配到新桶中，这称为重新分桶（rehash）。
重新分桶成本较高，并会使所有迭代器失效；但只要元素没有被删除，指向元素的引用和指针通常仍然有效。
需要注意：erase()通常只删除元素，不会自动减少桶数量。删除大量元素后，负载因子会下降，但已经分配的桶一般仍会保留。
3. 常用的桶管理接口
| 接口 | 作用 |
|---|---|
bucket_count() | 获取当前桶数量 |
max_load_factor(x) | 设置允许的最大负载因子 |
reserve(n) | 按预计元素数量提前准备桶，减少后续扩桶 |
rehash(n) | 请求重新调整桶数量，最终数量仍需满足负载要求 |
std::unordered_map<std::string,int>counts;counts.max_load_factor(0.75f);counts.reserve(1000);// 预计存放约 1000 个元素这里的reserve()是为预计元素数量准备哈希桶，不是像vector::reserve()那样预留一块连续元素空间。
四、哈希表的性能与适用场景
1. 为什么平均 O(1) 不等于永远更快？
哈希表需要计算哈希值并访问桶；发生冲突时，还要继续比较桶内元素。哈希函数质量差、负载因子过高或大量键集中在少数桶中时，单次操作最坏可能退化为 O(n)。
此外，小数据量下的哈希计算、节点分配和不连续内存访问也有额外成本，因此unordered_map不一定始终比map快。
2. 哪些场景适合哈希表？
- **快速等值查找：**根据键查值，且不关心遍历顺序。
- **去重与存在性判断：**使用
unordered_set记录已经出现的元素。 - **频次统计：**键保存数据，值记录出现次数。
- **索引与缓存映射：**通过唯一键快速定位对象或缓存条目。
面试回答：
unordered_map通过哈希函数定位桶，再使用相等比较确认键。不同键进入同一桶时会发生冲突，常见实现通常用桶数组配合节点链处理。负载因子过高时会扩桶并重新分桶，所以操作平均为 O(1)，冲突严重时最坏可能退化为 O(n)。
五、迭代器、指针和引用何时失效
map插入通常不影响已有迭代器。unordered_map重新分桶会让迭代器失效。- 重新分桶后，元素引用和指针通常仍保持有效。
- 删除操作只让被删除元素失效。
六、应该怎样选择
一般什么情况下使用map？
当需求不只是“根据键找到值”，而是还依赖键的顺序、范围或稳定性时，map更合适。
| 使用场景 | 核心需求 | map适合的原因 |
|---|---|---|
| 按键有序输出 | 遍历时自然得到升序或自定义顺序 | 插入后自动维护键的有序性 |
| 范围查询 | 查找某个键区间内的所有元素 | 支持lower_bound()、upper_bound()和equal_range() |
| 查找前驱、后继 | 定位最接近目标键的元素 | 有序迭代器可以向前或向后移动 |
| 需要稳定复杂度 | 不希望查找因哈希冲突退化 | 查找、插入和删除稳定为 O(log n) |
| 需要稳定迭代器 | 插入后继续使用已有迭代器或引用 | 节点式树结构插入通常不会使已有位置失效 |
| 自定义键适合排序 | 容易定义明确的大小关系，但不容易设计哈希 | 提供满足严格弱序的比较器即可 |
如果只需要按键做等值查找、不关心遍历顺序，并且能提供质量可靠的哈希函数，可以优先考虑unordered_map，获得平均 O(1) 的查找效率。
自定义类型作为map的键时，不是只能重载operator<；也可以向模板参数传入自定义比较器。无论采用哪种方式，比较规则都必须满足严格弱序。
**选择原则：**需要顺序、范围查询或最坏情况稳定性时选
map；只需要高效等值查找且哈希可靠时考虑unordered_map。不要只根据“平均 O(1) 比 O(log n) 快”做决定。
七、总结
- 底层结构不同。
map通常使用红黑树，键始终有序；unordered_map使用哈希表，只根据哈希值定位桶，不保证遍历顺序。 - 复杂度保证不同。
map的查找、插入和删除稳定为 O(log n)；unordered_map平均为 O(1)，但哈希冲突严重时最坏可能退化为 O(n)。 - 支持的查询能力不同。
map适合有序遍历、范围查询以及查找前驱和后继；unordered_map更适合不关心顺序的等值查找、频次统计和存在性判断。 - **内存与失效规则不同。**两者通常都采用节点式存储，但
unordered_map还需要桶数组；重新分桶会使所有迭代器失效，而map插入通常不会影响已有迭代器。 - **选择不能只比较 O(1) 和 O(log n)。**需要顺序、范围查询或稳定的最坏复杂度时选
map；只做高频等值查找，并且哈希函数可靠时考虑unordered_map。
**一句话记忆：**要顺序和范围选
map，只要平均 O(1) 的等值查找选unordered_map，但要同时考虑哈希质量、内存和重新分桶。
八、高频面试题（精选）
map和unordered_map的底层结构分别是什么？- 什么是哈希冲突？STL 中的
unordered_map通常怎样处理？ - 拉链法和开放寻址法各有什么优缺点？
unordered_map为什么最坏会退化到 O(n)？- 负载因子是什么？什么情况下会重新分桶？
- 重新分桶后哪些迭代器、引用和指针失效？
- 一般什么情况下使用
map？什么时候更适合使用unordered_map？
CodeACM 是面向算法竞赛和编程面试的 ACM 在线刷题网站，支持在线刷题、代码提交、在线判题与专题练习。网站地址：https://codeacm.cn
#C++面试 #STL容器 #map #unordered_map #CodeACM
