不需要顺序、只追求最快查找速度时的选择——底层用哈希表实现，平均查找速度 O(1)，比 map 的 O(log n) 更快。
如果你不需要元素保持有序，只追求最快的查找速度，可以用 unordered_map。它底层用哈希表实现，平均查找速度是 O(1)，比 map 的 O(log n) 更快。代价是元素没有顺序，遍历时是乱的。使用前需引入 <unordered_map> 头文件。
map 的红黑树那样一层层比较。这就是为什么 unordered_map 平均是 O(1)，但代价是元素在内存里的排列和"键的大小"毫无关系——遍历顺序看起来是乱的。
| 1 | #include <iostream> |
| 2 | #include <unordered_map> // 必须包含这个头文件 |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | unordered_map<string, int> um; // 用法和 map 完全一样 |
| 8 | um["Alice"] = 85; |
| 9 | um["Bob"] = 92; |
| 10 | um.insert({"Carol", 78}); |
| 11 | return 0; |
| 12 | } |
unordered_map 的接口和 map 几乎完全一样——[]、at()、insert()、erase()、find()、count() 全都能直接照搬，11.8 节学的所有陷阱（[] 自动插入、insert 不覆盖）在这里同样适用。唯一的本质区别是：没有顺序。| 1 | unordered_map<string, int> um; |
| 2 | um["Alice"] = 85; // 用法和 map 完全一样 |
| 3 | um["Bob"] = 92; |
| 4 | um.insert({"Carol", 78}); |
| 5 | |
| 6 | // 查找也是 O(1)，比 map 更快 |
| 7 | if (um.count("Alice")) |
| 8 | { |
| 9 | cout << um["Alice"] << endl; |
| 10 | } |
| 11 | |
| 12 | // 遍历——注意顺序是乱的！ |
| 13 | for (auto& p : um) |
| 14 | { |
| 15 | cout << p.first << ": " << p.second << endl; // 输出顺序不确定 |
| 16 | } |
unordered_map 的遍历顺序都可能不一样。如果题目要求按某种顺序输出，千万不要用 unordered_map，要么用 map，要么把键取出来单独排序。| 对比项 | map | unordered_map |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 查找/插入/删除 | O(log n) | 平均 O(1)，最坏 O(n) |
| 遍历顺序 | 按键自动升序 | 无序，不可预测 |
| 键的要求 | 需支持 < 比较 | 需支持哈希和 == |
| 典型场景 | 需要顺序、范围查询 | 只要快速查找，不关心顺序 |
| 1 | #include <iostream> |
| 2 | #include <unordered_map> |
| 3 | #include <vector> |
| 4 | using namespace std; |
| 5 | |
| 6 | int main() |
| 7 | { |
| 8 | unordered_map<string, int> wordCount; |
| 9 | |
| 10 | // 统计单词出现次数（不需要顺序，最适合 unordered_map） |
| 11 | vector<string> words = {"apple", "banana", "apple", "cherry", "apple"}; |
| 12 | for (auto& w : words) { |
| 13 | wordCount[w]++; // 不存在则自动插入 0，再 +1 |
| 14 | } |
| 15 | |
| 16 | for (auto& p : wordCount) { |
| 17 | cout << p.first << ": " << p.second << endl; |
| 18 | } |
| 19 | // 输出顺序不确定，但每个单词的计数一定是对的： |
| 20 | // apple: 3, banana: 1, cherry: 1（顺序可能不同） |
| 21 | |
| 22 | return 0; |
| 23 | } |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用——和 map 几乎一模一样，主要区别在备注列。
| 方法 | 分类 | 作用 |
|---|---|---|
| um[key] = val | 插入/修改 | 赋值，键存在则覆盖，不存在则插入 |
| um.insert({key, val}) | 插入 | 插入，键已存在则不覆盖 |
| um.erase(key) | 删除 | 删除指定键的元素 |
| um[key] | 查找 | 键不存在时自动插入默认值，要小心 |
| um.at(key) | 查找 | 键不存在时抛出异常，更安全 |
| um.find(key) | 查找 | 返回迭代器，没找到返回 end()，平均 O(1) |
| um.count(key) | 查找 | 判断键是否存在，返回 0 或 1 |
| um.size() / um.empty() | 容量 | 元素个数 / 判断是否为空 |
| um.clear() | 容量 | 清空所有元素 |
| um.begin() / um.end() | 遍历 | 迭代器范围，顺序不保证，不要依赖 |
unordered_map 通常比 map 快不少。但如果键的哈希冲突很多，最坏情况会退化到 O(n)，竞赛中要留意这一点。