一、HashTable（哈希表）
（1）HashTable与其核心思想
哈希表（Hash Table）是一种基于哈希函数的键值映射数据结构，它能在O(1) 的均摊时间复杂度内完成查找、插入和删除操作。
核心思想：
- 通过哈希函数（Hash Function） 计算键的哈希值，映射到一个索引位置。
- 若索引位置冲突（两个键映射到相同索引），使用冲突解决策略（如链地址法或开放寻址法） 处理。
- 负载因子（Load Factor） 影响哈希表性能，通常超过阈值时会进行动态扩容。
其中，负载因子是指哈希表中已存储元素数量与总容量的比值，用于衡量哈希表的填充程度。
（2）HashTable的实现
| STL 容器 | 底层实现 | 是否有序 | 允许重复键/值 |
|---|---|---|---|
unordered_map | 哈希表 | ❌ | ❌ |
unordered_multimap | 哈希表 | ❌ | ✅ |
unordered_set | 哈希表 | ❌ | ❌ |
unordered_multiset | 哈希表 | ❌ | ✅ |
使用建议：
- 需要 O(1) 查找？用
unordered_map（哈希表）。 - 需要唯一键值？用
unordered_set（哈希集合）。 - 需要允许重复键？用
unordered_multimap。 - 需要允许重复值？用
unordered_multiset。
（3）红黑树（map） vs 哈希表（unordered_map）
红黑树 (map) | 哈希表 (unordered_map) | |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 插入/删除/查找 | O(log n) | O(1)（均摊） |
| 是否有序 | 是（按键排序） | 否（无序存储） |
| 适用场景 | 需要排序、范围查询 | 仅关心查找速度 |
二、unordered_map（哈希表的键值映射）
（1）常用函数
| 函数 | 作用 |
|---|---|
insert({Key, Value}) | 插入键值对 |
find(Key) | 查找键，返回迭代器（不存在则 end()） |
erase(Key) | 删除键 |
count(Key) | 返回键的个数（对于 unordered_map 只能是 0 或 1） |
size() | 返回元素个数 |
clear() | 清空哈希表 |
（2）基本使用
#include <iostream>
using namespace std;
#include <unordered_map>
#include <string>int main() {unordered_map<string, int> hash_table;// 插入键值对hash_table["Apple"] = 10;hash_table["Banana"] = 20;hash_table["Cherry"] = 30;// 查找键值对if (hash_table.find("Banana") != hash_table.end()){cout << "Banana 的值是: " << hash_table["Banana"] << endl;}// 遍历哈希表（无序）cout << "哈希表内容:" << endl;for (const auto& pair : hash_table){cout << pair.first << " -> " << pair.second << endl;}system("pause");return 0;
}
注意：
unordered_map中采用无序存储。- 查找
find()的复杂度为O(1) 。 []访问键时，若键不存在，会创建默认值。
三、unordered_set（哈希表的无序集合）
（1）常用函数
| 函数 | 作用 |
|---|---|
insert(Value) | 插入元素 |
find(Value) | 查找元素，返回迭代器 |
erase(Value) | 删除元素 |
count(Value) | 返回元素个数（只能是 0 或 1） |
size() | 返回集合大小 |
clear() | 清空集合 |
（2）基本使用
#include <iostream>
using namespace std;
#include <unordered_set>int main() {unordered_set<int> hash_set = {10, 20, 30, 40};// 插入元素hash_set.insert(50);hash_set.insert(30); // 30 已存在，不会重复插入// 查找元素if (hash_set.find(20) != hash_set.end()){cout << "20 存在于哈希集合中" << endl;}// 遍历哈希集合（无序）cout << "哈希集合中的元素: ";for (int num : hash_set){cout << num << " ";}cout << endl;system("pause");return 0;
}
注意：
unordered_set基于哈希表实现集合（元素唯一，自动去重）。- 采用无序存储，适用于快速去重、判重、查找。
- 查找
find()的复杂度为O(1) 。
四、unordered_multimap 和 unordered_multiset（允许重复键/值的哈希表）
unordered_multimap——允许 重复键 的无序哈希表。unordered_multiset——允许 重复值 的无序哈希集合。
（1）unordered_multimap的使用
#include <iostream>
using namespace std;
#include <unordered_map>
#include <string>int main() {unordered_multimap<int, string> multi_hash_map;// 插入重复键multi_hash_map.insert({ 1, "Apple" });multi_hash_map.insert({ 2, "Banana" });multi_hash_map.insert({ 1, "Avocado" }); // 允许重复键// 遍历哈希表cout << "unordered_multimap 内容:" << endl;for (const auto& pair : multi_hash_map){cout << pair.first << " -> " << pair.second << endl;}system("pause");return 0;
}
注意：
unordered_multimap允许多个相同键，适用于数据库索引等。
（2）unordered_multiset的使用
#include <iostream>
using namespace std;
#include <unordered_set>int main() {unordered_multiset<int> hash_multiset = { 10, 20, 30 };// 插入元素hash_multiset.insert(20); // 允许重复值hash_multiset.insert(30); // 允许重复值hash_multiset.insert(40);// 遍历哈希集合（无序）cout << "哈希集合中的元素: ";for (int num : hash_multiset){cout << num << " ";}cout << endl;system("pause");return 0;
}
