本文目录 4 个章节
C++ std::map 与 std::unordered_map 的区别
note · 名称 C++ 标准库没有名为
hashmap的标准容器；对应的哈希关联容器是std::unordered_map。
核心差异
| 维度 | std::map |
std::unordered_map |
|---|---|---|
| 组织方式 | 有序关联容器，通常由平衡搜索树实现 | 无序关联容器，通常由哈希表实现 |
| 键顺序 | 按比较器排序 | 没有稳定的键顺序保证 |
| 查找/插入/删除 | O(log n) |
平均 O(1)，最坏 O(n) |
| 范围查询 | 支持 lower_bound、有序遍历 |
不适合按键范围查询 |
| 主要失效条件 | 删除元素使被删元素的迭代器失效 | rehash 可使所有迭代器失效 |
| 额外要求 | 键需要严格弱序比较 | 键需要哈希函数与相等判断一致 |
标准规定的是行为和复杂度要求，不强制某一种底层数据结构。常见实现中 map 使用红黑树，unordered_map 使用桶数组与链式/节点结构，但不应把实现细节当成跨平台保证。
如何选择
选择 std::map：
- 需要按键排序遍历；
- 需要范围查询或相邻键；
- 希望复杂度有稳定的对数上界；
- 无法提供可靠、廉价的哈希函数。
选择 std::unordered_map：
- 主要是精确键查询；
- 不依赖遍历顺序；
- 哈希分布可控，且平均常数时间带来实际收益。
哈希表不一定更快：小数据量、缓存局部性、节点分配、哈希成本、负载因子和碰撞都会影响结果。应使用真实键和值在目标平台做基准测试。
常用控制项
#include <unordered_map>
std::unordered_map<int, int> values;
values.reserve(1000); // 预计元素数，减少 rehash
values.max_load_factor(0.8f);
自定义键时，若 a == b，哈希函数必须保证两者哈希值相同；反过来哈希值相同不要求键相等。