unordered_map
std::unordered_map 是 C++11 引入的无序关联容器，用来存储“键值对”。它基于哈希表实现，核心目标是让查找、插入、删除在平均情况下接近常数时间。
和 std::map 相比：
unordered_map不保证按键有序。- 典型操作平均复杂度更低（平均
O(1)）。 - 不能做基于顺序的范围查找（如
lower_bound）。
头文件与基本特征
#include <unordered_map>
常见特征如下：
| 特征 | 说明 |
|---|---|
| 元素类型 | std::pair<const Key, T> |
| 顺序 | 无序（迭代顺序不稳定） |
| 底层结构 | 哈希表（桶 + 链/节点） |
| 查找复杂度 | 平均 O(1)，最坏 O(n) |
| 键是否重复 | 不允许重复键 |
基本用法
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 88;
scores["Cathy"] = 91;
std::cout << "Alice = " << scores["Alice"] << '\n';
return 0;
}
operator[] 在键不存在时会自动插入默认值，再返回该值引用。
交互演示（MDX + React）
下面这个面板会模拟 unordered_map 的桶分布和常见操作，适合快速理解：
insert/operator[]更新行为。find与erase的查询删除路径。reserve后bucket_count和load_factor的变化。- 冲突时同一桶内挂载多个键值对。
unordered_map 哈希桶交互演示
观察 insert / find / erase 与 bucket_count、load_factor、冲突桶分布的变化。
bucket #0
empty
bucket #1
empty
bucket #2
- cat: 7
bucket #3
- banana: 5
bucket #4
- apple: 3
最近操作
- 初始化: 已插入 apple/banana/cat
遍历
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 88;
scores["Cathy"] = 91;
for (std::unordered_map<std::string, int>::iterator it = scores.begin(); it != scores.end(); ++it) {
std::cout << it->first << " = " << it->second << '\n';
}
return 0;
}
输出顺序可能和插入顺序不同，也不保证每次运行都一样。
常用成员函数
| 函数 | 作用 |
|---|---|
begin() / end() | 遍历容器 |
empty() | 是否为空 |
size() | 元素数量 |
clear() | 清空 |
insert() | 插入键值对 |
erase() | 删除键或迭代器位置元素 |
find() | 查找键 |
count() | 统计键出现次数（0 或 1） |
at() | 按键访问，不存在会抛异常 |
bucket_count() | 当前桶数量 |
load_factor() | 当前负载因子 |
rehash(n) | 调整桶数量 |
reserve(n) | 预留至少可容纳 n 个元素的桶容量 |
插入与更新
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> m;
m.insert(std::make_pair(std::string("apple"), 3));
m["banana"] = 5;
std::pair<std::unordered_map<std::string, int>::iterator, bool> result =
m.insert(std::make_pair(std::string("apple"), 100));
if (!result.second) {
result.first->second = 100;
}
return 0;
}
insert 在键已存在时不会覆盖旧值；operator[] 会覆盖。
查找与删除
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> m;
m["cpp"] = 11;
m["c"] = 98;
std::unordered_map<std::string, int>::iterator it = m.find("cpp");
if (it != m.end()) {
std::cout << it->first << " = " << it->second << '\n';
}
m.erase("c");
return 0;
}
如果只想查询是否存在，优先 find 或 count，避免误用 operator[] 导致意外插入。
哈希与桶
unordered_map 把元素按哈希值分配到不同桶中。当元素太多、负载因子过高时，可能触发 rehash，重新分配桶并重排元素。
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m;
m.reserve(1000);
for (int i = 0; i < 1000; ++i) {
m[i] = i * i;
}
std::cout << "bucket_count = " << m.bucket_count() << '\n';
std::cout << "load_factor = " << m.load_factor() << '\n';
return 0;
}
在已知数据规模时提前 reserve，可减少 rehash 次数并提升整体性能。
自定义键类型
当键是自定义类型时，需要提供哈希函数和相等比较。
#include <iostream>
#include <string>
#include <unordered_map>
struct User {
std::string name;
int id;
};
struct UserHash {
std::size_t operator()(const User& u) const {
return std::hash<std::string>()(u.name) ^ (std::hash<int>()(u.id) << 1);
}
};
struct UserEqual {
bool operator()(const User& lhs, const User& rhs) const {
return lhs.name == rhs.name && lhs.id == rhs.id;
}
};
int main() {
std::unordered_map<User, int, UserHash, UserEqual> scores;
User tom;
tom.name = "Tom";
tom.id = 1;
scores[tom] = 95;
std::cout << scores[tom] << '\n';
return 0;
}
哈希函数和相等比较应保持一致性：若两个键相等，它们的哈希值也应相同。
unordered_map 与 map 如何选择
- 只关心快速查找，不关心顺序：优先
unordered_map。 - 需要按键有序遍历、范围查询：选择
map。 - 数据量较大、键分布较好时：
unordered_map通常更快。 - 需要稳定有序输出结果：
map更适合。
使用注意
- 不要依赖
unordered_map的遍历顺序。 operator[]可能导致隐式插入。- rehash 后，迭代器可能失效。
- 最坏情况下复杂度可能退化到
O(n)。 - 自定义键时，务必正确实现哈希与相等比较。
小结
std::unordered_map 是 C++11 里非常高频的容器之一，适合“键唯一 + 高频查找”的场景。掌握 insert、find、erase、reserve 以及自定义哈希后，就能覆盖大多数工程中的映射需求。