std::unordered_set
std::unordered_set 是一个哈希表实现的集合，用于存储唯一的元素。
特点
- 唯一性：集合中的每个元素都是唯一的。
- 无序：元素的存储顺序不按照插入顺序，也不按照大小排序。
- 快速查找：插入、删除和查找操作的时间复杂度平均为 O(1)。
核心原理
(1) 数据存储结构
- 使用 哈希表（Hash Table） 存储元素。
- 哈希表的每个位置称为 桶（Bucket），由哈希函数将元素映射到某个桶中。
(2) 哈希函数
-
使用一个哈希函数
std::hash将元素的值转换为哈希值。 -
哈希值通过 取模操作 映射到桶索引，即：
- bucket_index=hash(value)%bucket_count
-
哈希函数确保相同值的元素总是映射到同一桶。
(3) 冲突处理
- 如果多个元素映射到同一个桶（称为哈希冲突），使用链地址法（Separate Chaining）解决冲突。
- 每个桶内部使用链表存储冲突的元素。
(4) 插入和查找
- 插入：计算元素的哈希值，找到桶索引，将元素插入链表中（如果不重复）。
- 查找：计算元素的哈希值，找到桶索引，遍历链表查找目标值。
内部成员
(1) 哈希函数
-
默认使用
std::hash<T>提供的哈希函数。 -
可以通过模板参数自定义哈希函数：
std::unordered_set<int, CustomHashFunction> mySet;
(2) 负载因子
- 负载因子（Load Factor） 是当前元素个数与桶数的比值：
- load_factor = size / bucket_count
- 当负载因子超过指定的上限（默认值为 1.0），哈希表会 自动扩容。
(3) 再散列
- 再散列（Rehashing）会创建一个更大的哈希表，并重新分配所有元素到新的桶中。
- 再散列的触发条件：
- 插入新元素后，负载因子超过
max_load_factor。 - 手动调用
rehash()或reserve()。
- 插入新元素后，负载因子超过
工作流程
插入流程
- 使用哈希函数计算元素的哈希值。
- 根据哈希值找到桶索引。
- 检查目标桶中的链表是否已经存在该元素：
- 如果不存在，插入元素。
- 如果存在，不插入（确保元素唯一）。
查找流程
- 使用哈希函数计算元素的哈希值。
- 根据哈希值找到桶索引。
- 遍历目标桶的链表，查找是否存在目标元素。
常用成员函数
insert：插入元素。find：查找元素。erase：删除元素。size：获取集合的大小。count：检查某个元素是否存在。
示例
#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;// 插入元素uset.insert(10);uset.insert(20);uset.insert(30);// 插入重复元素（不会生效）uset.insert(20);// 遍历集合std::cout << "Unordered Set Elements: ";for (int val : uset) {std::cout << val << " ";}std::cout << std::endl;// 查找元素if (uset.find(20) != uset.end()) {std::cout << "Element 20 found in the set." << std::endl;}// 删除元素uset.erase(10);// 检查元素是否存在if (uset.count(10) == 0) {std::cout << "Element 10 is not in the set." << std::endl;}return 0;
}
std::unordered_map
特点
- 键唯一：每个键是唯一的。
- 无序：键值对的存储顺序无关插入顺序或键的大小。
- 快速操作：插入、删除和查找操作的时间复杂度平均为 O(1)。
核心原理
(1) 数据存储结构
- 使用 哈希表（Hash Table） 作为底层数据结构。
- 哈希表由若干个 桶（Bucket） 组成，每个桶负责存储一组键值对。
(2) 哈希函数
- 使用默认的哈希函数
std::hash<T>或用户自定义的哈希函数，将键值（key）转换为哈希值。 - 哈希值通过取模操作，映射到具体的桶索引：
- bucket_index=hash(key)%bucket_count
(3) 冲突处理
- 如果多个键映射到同一个桶（哈希冲突），使用 链地址法（Separate Chaining） 来解决。
- 每个桶内部以链表或其他结构存储冲突的键值对。
(4) 键值对存储
- 键值对以
std::pair<const Key, Value>的形式存储。 - 键（
Key）是唯一的，值（Value）可以重复。
内部成员
(1) 哈希函数
-
默认使用
std::hash<Key>提供的哈希函数：
std::unordered_map<int, std::string> umap; -
用户可以自定义哈希函数：
struct CustomHash {size_t operator()(const std::string& key) const {return std::hash<std::string>{}(key) ^ (key.length() << 1);} }; std::unordered_map<std::string, int, CustomHash> custom_map;
(2) 负载因子
- 负载因子（Load Factor）：当前元素数与桶数量的比值。
- load_factor = size / bucket_count
- 当负载因子超过
max_load_factor时，哈希表会 自动扩容，并进行 再散列（Rehashing）。
(3) 再散列（Rehashing）
- 再散列会分配一个更大的哈希表，并将原来的键值对重新分布到新桶中。
- 再散列触发条件：
- 插入新元素后，负载因子超过
max_load_factor。 - 手动调用
rehash()或reserve()。
- 插入新元素后，负载因子超过
工作流程
插入元素
- 使用哈希函数计算键的哈希值。
- 根据哈希值找到桶索引。
- 遍历目标桶的链表，检查键是否存在：
- 如果键存在，更新对应的值。
- 如果键不存在，将键值对插入链表。
查找元素
- 使用哈希函数计算键的哈希值。
- 根据哈希值找到桶索引。
- 遍历目标桶的链表，查找目标键，返回对应的值。
删除元素
- 使用哈希函数计算键的哈希值。
- 根据哈希值找到桶索引。
- 遍历目标桶的链表，删除匹配的键值对。
常用成员函数
insert：插入键值对。operator[]：通过键访问或插入值。find：查找键是否存在。erase：删除键值对。size：获取字典的大小。
示例
#include <iostream>
#include <unordered_map>int main() {std::unordered_map<std::string, int> umap;// 插入键值对umap["Alice"] = 25;umap["Bob"] = 30;umap["Charlie"] = 35;// 插入方式二umap.insert({"David", 40});// 遍历字典std::cout << "Unordered Map Elements:\n";for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}// 查找键if (umap.find("Bob") != umap.end()) {std::cout << "Bob's age is " << umap["Bob"] << std::endl;}// 删除键值对umap.erase("Alice");// 检查键是否存在if (umap.find("Alice") == umap.end()) {std::cout << "Alice is not in the map." << std::endl;}return 0;
}
std::unordered_set和 std::unordered_map的比较
| 特性 | std::unordered_set | std::unordered_map |
|---|---|---|
| 存储内容 | 仅存储键，值为元素本身 | 存储键值对 |
| 键的唯一性 | 键必须唯一 | 键必须唯一 |
| 存储顺序 | 无序 | 无序 |
| 访问复杂度 | 平均 O(1) | 平均 O(1) |
| 使用场景 | 集合操作（如元素存在性检查） | 键值对操作（如映射关系） |
高级实例
示例 1：使用 std::unordered_map 统计字符串中字符的频率
#include <iostream>
#include <unordered_map>
#include <string>int main() {std::string str = "hello world";std::unordered_map<char, int> freq;// 统计每个字符的频率for (char c : str) {if (c != ' ') { // 忽略空格freq[c]++;}}// 输出结果std::cout << "Character Frequencies:\n";for (const auto& pair : freq) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}
示例 2：使用 std::unordered_set 去除数组中的重复元素
#include <iostream>
#include <unordered_set>
#include <vector>int main() {std::vector<int> nums = {1, 2, 2, 3, 4, 4, 5};std::unordered_set<int> uniqueNums(nums.begin(), nums.end());std::cout << "Unique Elements: ";for (int num : uniqueNums) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
注意事项
- 无序性
std::unordered_set和std::unordered_map中的元素顺序不可预测。- 如果需要有序容器，使用
std::set或std::map。
- 哈希函数的性能
- 默认使用标准库的哈希函数，如果存储自定义类型，需要为其提供自定义哈希函数。
- 迭代器的稳定性
- 删除元素时，指向已删除元素的迭代器会失效。
总结
-
std::unordered_set和std::unordered_map是高效的容器，适合用于频繁查找、插入和删除操作的场景。 -
std::unordered_set适用于集合操作，std::unordered_map适用于键值对操作。
