通过动态演示、代码联动和交互操作，直观理解哈希表的工作原理和操作过程
哈希表（Hash Table）是一种基于哈希函数实现的数据结构，它提供了近乎常数时间复杂度的查找、插入和删除操作，是许多应用中的关键数据结构。
在本演示中，我们将重点关注链地址法解决碰撞的哈希表实现，这是C++标准库中unordered_map和unordered_set的基本实现原理。
通过下面的交互式演示，您可以观察哈希表的插入、查找和删除操作，以及碰撞的处理过程。
此演示展示了使用链地址法处理碰撞的哈希表。每个索引位置都有一个链表，可以存储多个具有相同哈希值的元素。
可以通过上方的输入框和按钮尝试插入、查找和删除操作。
在哈希表中插入一个新的键值对需要以下步骤：
插入操作的平均时间复杂度为O(1)，但在最坏情况下（所有键都映射到同一个桶）可能达到O(n)。
在哈希表中查找一个键需要以下步骤：
查找操作的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)。
从哈希表中删除一个键值对需要以下步骤：
删除操作的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)。
以下是C++ STL中map和unordered_map的常用操作示例：
#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
int main() {
// 创建容器
std::map<std::string, int> ordered_map;
std::unordered_map<std::string, int> hash_map;
// 1. 插入元素
// 方法1：使用insert
ordered_map.insert({"apple", 1});
hash_map.insert({"apple", 1});
// 方法2：使用[]运算符
ordered_map["banana"] = 2;
hash_map["banana"] = 2;
// 方法3：使用emplace
ordered_map.emplace("orange", 3);
hash_map.emplace("orange", 3);
// 2. 访问元素
// 使用[]（如果键不存在会创建新元素）
std::cout << ordered_map["apple"] << "\n";
// 使用at（如果键不存在会抛出异常）
try {
std::cout << hash_map.at("banana") << "\n";
} catch (const std::out_of_range& e) {
std::cout << "Key not found\n";
}
// 3. 查找元素
auto it1 = ordered_map.find("orange");
if (it1 != ordered_map.end()) {
std::cout << "Found: " << it1->second << "\n";
}
// 4. 删除元素
ordered_map.erase("apple");
hash_map.erase("apple");
// 5. 遍历
for (const auto& [key, value] : ordered_map) {
std::cout << key << ": " << value << "\n";
}
// 6. 其他常用操作
size_t size = ordered_map.size();
bool empty = hash_map.empty();
ordered_map.clear();
return 0;
}
| 特性 | std::map | std::unordered_map |
|---|---|---|
| 底层实现 | 红黑树 | 哈希表 |
| 时间复杂度 |
插入: O(log n) 查找: O(log n) 删除: O(log n) |
插入: 平均O(1) 查找: 平均O(1) 删除: 平均O(1) |
| 元素顺序 | 按键排序 | 无序 |
| 内存占用 | 较低 | 较高 |
| 迭代器失效 | 插入时不失效 | 插入时可能失效 |
| 适用场景 |
- 需要有序遍历 - 需要范围查询 - 内存敏感 |
- 需要快速查找 - 不需要排序 - 性能优先 |
以下是一些经典的哈希表相关练习题，帮助您加深对哈希表的理解：