【001code】哈希表基本概念和应用
·
哈希表(Hash Table)是计算机中一种 高效的查找数据结构,它能够在 O(1) 平均时间复杂度 内进行插入、删除和查找操作。哈希表在许多算法和数据结构中都有应用,例如 LRU缓存、计数问题、映射关系存储 等。
1. 哈希表的基本概念
(1)哈希表的定义
哈希表(Hash Table)是一种 键值对(key-value)存储结构,它通过哈希函数将键(Key)映射到一个索引位置,并存储相应的值(Value)。
在 C++ 中,常用的哈希表实现:
unordered_map<Key, Value>(无序映射)unordered_set<Key>(无序集合)
(2)哈希函数(Hash Function)
哈希函数的作用是将键转换成数组索引,从而实现 O(1) 时间复杂度 进行存取。
常见的哈希函数:
- 直接取模:
index = key % table_size - 乘法哈希法
- 一致性哈希(应用于分布式系统)
示例(简单哈希函数取模):
int hashFunction(int key, int table_size) {
return key % table_size;
}
2. C++ STL 中的哈希表
(1)unordered_map(哈希映射)
用于存储键值对,支持 O(1) 平均查找/插入/删除。
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> scores;
// 插入元素
scores["Alice"] = 90;
scores["Bob"] = 85;
// 查找元素
if (scores.count("Alice")) {
cout << "Alice's score: " << scores["Alice"] << endl;
}
// 遍历哈希表
for (auto& pair : scores) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
常见操作:
| 方法 | 作用 |
|---|---|
map[key] = value; | 插入键值对 |
map.count(key); | 判断 key 是否存在 |
map.erase(key); | 删除 key |
map.find(key); | 查找 key,返回迭代器 |
(2)unordered_set(哈希集合)
- 只存储唯一元素
- 没有 key-value 结构,只有 key
- 适用于 去重、快速查找
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> numbers = {1, 2, 3, 4, 5};
// 插入元素
numbers.insert(10);
// 查找元素
if (numbers.count(3)) {
cout << "3 存在" << endl;
}
// 遍历哈希集合
for (int num : numbers) {
cout << num << " ";
}
return 0;
}
常见操作:
| 方法 | 作用 |
|---|---|
set.insert(value); | 插入元素 |
set.count(value); | 判断元素是否存在 |
set.erase(value); | 删除元素 |
set.find(value); | 查找元素,返回迭代器 |
3. 哈希冲突(Hash Collision)
哈希表有可能出现两个不同的键被映射到相同的索引,这称为 哈希冲突。
(1)解决方法
- 拉链法(Chaining):每个哈希桶存储一个链表,冲突元素存入链表中
- 开放地址法(Open Addressing):如果索引冲突,则寻找下一个空闲位置存储
4. 哈希表的时间复杂度
| 操作 | 平均时间复杂度 | 最坏时间复杂度(哈希冲突严重) |
|---|---|---|
插入 insert() | O(1) | O(n) |
删除 erase() | O(1) | O(n) |
查找 find() | O(1) | O(n) |
5. 哈希表的实际应用
(1)两数之和(Two Sum)
利用 unordered_map 进行 O(n) 优化:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.count(complement)) {
return {map[complement], i};
}
map[nums[i]] = i;
}
return {};
}
(2)找出数组中的唯一元素
用 unordered_set 进行去重:
vector<int> removeDuplicates(vector<int>& nums) {
unordered_set<int> unique(nums.begin(), nums.end());
return vector<int>(unique.begin(), unique.end());
}
(3)字符串频率统计
unordered_map<char, int> countFrequency(string s) {
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
return freq;
}
总结
| 知识点 | 说明 |
|---|---|
| 哈希表的核心思想 | 通过哈希函数将 key 映射到数组索引,支持 O(1) 查找 |
| unordered_map | 存储 key-value 对,适用于计数、映射关系 |
| unordered_set | 只存 key,用于去重和快速查找 |
| 哈希冲突解决方法 | 拉链法、开放地址法 |
| 哈希表的应用 | 两数之和、频率统计、去重等 |
更多推荐


所有评论(0)