哈希表基础概念
哈希表是一种用于存储数据的容器,本质是通过键值对(key-value)的形式组织数据。它的核心优势在于能实现元素的快速查找,理想情况下时间复杂度可达 O(1),远超二分查找的 O(log N)。
适用场景
当需要频繁查找某个特定元素时(例如统计字符出现频率、检测重复值),哈希表是最优选择。尤其适合处理需要高频查询的场景,以空间换时间显著提升效率。
实现方式
方法一:直接使用容器
利用编程语言内置的哈希表结构(如 C++ 的 unordered_map 和 unordered_set)。
方法二:数组模拟简易哈希表
- 适用条件:键为字符或小范围整数(如 ASCII 字符)。
- 原理:用数组索引直接表示键(如
index),存储值(如n[index])。 - 示例:统计字母出现次数时,可通过
char - 'a'将字符映射到数组下标。
关键注意事项
- 数组模拟法要求键的范围小且连续,否则会造成空间浪费。
- 实际应用中需处理哈希冲突(常用链地址法或开放寻址法)。
- 与二分查找对比:哈希表查询更快但耗内存;二分查找节省空间但要求数据有序且速度较慢。
经典题目实战
两数之和
题目要求给出一个数组,找出两个数和为 target。
暴力解法通常采用双重循环一一列举,时间复杂度为 O(n²)。虽然能通过测试,但效率较低。我们可以尝试固定一个数,在它前面找另一个数,这为引入哈希表做了铺垫。
优化思路: 从前往后遍历整个数组,前面的数入哈希表,遇到当前数时,在哈希表中查找是否存在目标值(target - nums[i])。因为需要返回下标,所以哈希表要将数据和下标进行绑定。这本质上是用空间换时间的策略。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash; // <nums[i], i>
for (int i = 0; i < nums.size(); i++) {
int tmp = target - nums[i]; // 目标值
if (hash.count(tmp)) {
return {hash[tmp], i};
}
hash[nums[i]] = i; // 当前数入哈希表
}
{, };
}
};


