深入理解C++中的 unordered_map 和 unordered_set
在C++标准库中，unordered_map 和 unordered_set 是两个基于哈希表（Hash Table）实现的高效容器。它们以O(1)的平均时间复杂度实现快速查找、插入和删除操作，特别适合需要高频操作且无需元素有序排列的场景。本文将从原理、用法、性能和应用场景等方面全面解析这两个容器。
一、核心概念与底层实现
1. 哈希表（Hash Table）
- 原理：通过哈希函数将键（Key）映射到存储位置（桶），直接定位数据。
- 冲突处理：当不同键映射到同一位置时，使用链地址法（链表存储冲突元素）或开放地址法。
2. unordered_map
- 定义：存储键值对（
key-value），键唯一，值可重复。 - 底层结构：哈希表存储
pair<const Key, Value>。
3. unordered_set
- 定义：存储唯一元素（仅键），自动去重。
- 底层结构：哈希表直接存储元素（键）。
-
二、基本操作与用法示例子
#include <unordered_map>
#include <unordered_set>// unordered_map 示例
std::unordered_map<std::string, int> wordCount = {{"apple", 5}, {"banana", 3}
};// unordered_set 示例
std::unordered_set<int> uniqueNumbers = {1, 2, 3, 4};2. 插入元素
// unordered_map
wordCount.insert({"grape", 2});
wordCount["orange"] = 4; // 支持下标操作符// unordered_set
uniqueNumbers.insert(5);3. 查找元素
// unordered_map
if (wordCount.find("apple") != wordCount.end()) {std::cout << "Found apple with count: " << wordCount["apple"] << std::endl;
}// unordered_set
if (uniqueNumbers.count(3) > 0) {std::cout << "3 exists in the set." << std::endl;
}4. 删除元素
// unordered_map
wordCount.erase("banana");// unordered_set
uniqueNumbers.erase(2);5. 遍历容器
/ 遍历 unordered_map
for (const auto& pair : wordCount) {std::cout << pair.first << ": " << pair.second << std::endl;
}// 遍历 unordered_set
for (const auto& num : uniqueNumbers) {std::cout << num << " ";
}三、性能特点与对比
1. 时间复杂度
| 操作 | 平均时间复杂度 | 最坏情况 |
|---|---|---|
| 插入、删除、查找 | O(1) | O(n)（哈希冲突严重时） |
2. 与有序容器的对比
| 特性 | unordered_map/set | map/set |
|---|---|---|
| 底层结构 | 哈希表 | 红黑树（平衡二叉搜索树） |
| 元素顺序 | 无序 | 按键有序排列 |
| 查找速度 | 更快（平均O(1)） | O(log n) |
| 内存占用 | 较低（无额外指针） | 较高（树结构） |
四、应用场景
1. unordered_map 典型场景
- 统计词频：快速记录单词出现次数。
- 缓存系统：通过键直接获取缓存值。
- 唯一键值存储：如用户ID到用户信息的映射。
2. unordered_set 典型场景
- 去重操作：过滤重复元素（如日志去重）。
- 存在性检查：快速判断元素是否存在（如黑名单验证）。
- 集合运算：求交集、并集（需结合其他方法）。
五、高级用法与注意事项
1. 自定义哈希函数
当键为自定义类型时，需提供哈希函数和相等比较器：
struct Person {std::string name;int age;
};// 自定义哈希函数
struct PersonHash {size_t operator()(const Person& p) const {return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);}
};// 自定义相等比较
struct PersonEqual {bool operator()(const Person& p1, const Person& p2) const {return p1.name == p2.name && p1.age == p2.age;}
};// 使用自定义类型
std::unordered_set<Person, PersonHash, PersonEqual> personSet;2. 调整哈希表性能
六、总结
何时选择 unordered_map/set？
通过合理选择容器，可以显著提升程序性能。对于大多数高频操作场景，unordered_map 和 unordered_set 凭借其哈希表的高效性，成为C++开发者的首选工具。
本文的讲解到此结束，谢谢大家的观看，有问题欢迎给我留评论。
- 负载因子（Load Factor）：桶中元素平均数量，影响冲突概率。
-
wordCount.max_load_factor(0.7); // 设置最大负载因子 wordCount.rehash(100); // 预分配桶数量3. 常见陷阱
- 哈希冲突：劣质哈希函数可能导致性能退化至O(n)。
- 迭代器失效：插入操作可能导致迭代器失效（触发rehash时）。
- 需要快速查找、插入、删除且不关心元素顺序时。
- 数据规模较大，且哈希函数设计合理时。
- 需要元素按序排列，或频繁进行范围查询（如
lower_bound）。
