哈希表详解
哈希表是面试中最常用的数据结构之一。关键不是背实现，而是理解为什么哈希表能 O(1) 查找，以及哈希冲突是什么、怎么处理。
面试考察点
面试官通过这道题想考察：
1. 你是否理解哈希表的核心思想
2. 你是否能解释什么是哈希冲突
3. 你是否理解不同冲突解决方法的特点
4. 你是否能根据场景设计合适的哈希函数
一、哈希表的核心思想
1.1 什么是哈希表？（小白解释）
面试官追问："为什么哈希表查找是 O(1)？"
哈希表 = 数组 + 哈希函数
核心思想：
通过哈希函数，把"键"转换成数组"索引"
然后直接用索引访问数组
类比：
- 普通数组：知道学号，知道在第几个，但还是要 O(n) 找
- 哈希表：知道学号，直接算出在哪个"桶"里
举例：存成绩
学号：1 → 哈希函数 → 位置 1 → 存 95 分
学号：2 → 哈希函数 → 位置 2 → 存 87 分
学号：3 → 哈希函数 → 位置 3 → 存 92 分
查找时：
学号 2 → 哈希函数 → 位置 2 → 立即得到 87 分
↑
一次计算就能定位！
1.2 什么是哈希函数？
哈希函数：把任意输入转换成固定范围的整数
好哈希函数的特点：
1. 确定性：相同输入 → 相同输出
2. 均匀性：输出均匀分布
3. 高效性：计算速度快
简单哈希函数示例：
int hash(key, size) {
return key % size; // 取模
}
问题：如果 key = 100, size = 10，hash = 0
如果 key = 200, size = 10，hash = 0
冲突！
面试加分点：
好的哈希函数应该让结果分布均匀，
Java String 的 hashCode 用的是：
h = s[0]*31^(n-1) + s[1]*31^(n-2) + ...
这能让字符的排列得到不同的哈希值
二、哈希冲突（面试核心）
2.1 什么是哈希冲突？
面试官追问："什么是哈希冲突？为什么会发生？"
哈希冲突：不同的 key 通过哈希函数得到相同的哈希值
鸽巢原理：
如果有 10 个桶，11 只鸽子，
至少有 1 个桶有 2 只或更多鸽子。
同理：
如果哈希值范围是 0-9，
但要存储 11 个元素，
至少有 2 个元素哈希值相同！
冲突是不可避免的，只能处理！
2.2 冲突解决方法 1：链地址法（Separate Chaining）
面试官追问："链地址法是怎么处理冲突的？"
链地址法：冲突的元素放在同一个桶的链表里
结构：
桶 0: [key1, key2, ...] → null
桶 1: [key3] → null
桶 2: [] → null
...
插入：算出哈希值，加到对应桶的链表头部
查找：算出哈希值，在对应链表里遍历
时间复杂度：
- 理想情况（哈希均匀）：O(1) 找到桶，O(k/n) 遍历链表
k = 元素总数，n = 桶数
如果桶数足够多，链表很短 → 接近 O(1)
- 最坏情况（全部冲突）：O(k)
优点：实现简单，删除容易
缺点：链表长时退化
图解：
哈希函数: key % 5
桶0: [0, 5, 10] → null
桶1: [1, 6] → null
桶2: [2, 7] → null
桶3: [3] → null
桶4: [4, 9] → null
插入 12: 12 % 5 = 2 → 加到桶2
2.3 冲突解决方法 2：开放地址法（Open Addressing）
面试官追问："开放地址法怎么处理冲突？"
开放地址法：冲突时，找另一个空位置
探测序列：h(0), h(1), h(2)...
1. 线性探测：依次往后找空位
h(key) + 0, h(key) + 1, h(key) + 2, ...
优点：简单
缺点：容易产生"聚集"（连续位置被占）
2. 平方探测：探测 h(key) + 1², h(key) - 1², h(key) + 2², ...
优点：避免聚集
缺点：可能探测不到所有位置
3. 双重哈希：h(key) + i * h2(key)
用两个哈希函数
优点：分布更均匀
图解 - 线性探测：
哈希函数: h(key) = key % 5
依次插入 12, 8, 5, 9:
12 % 5 = 2，位置 2 是空的，放
12: [_, _, 12, _, _]
8 % 5 = 3，位置 3 是空的，放
8: [_, _, 12, 8, _]
5 % 5 = 0，位置 0 是空的，放
5: [5, _, 12, 8, _]
9 % 5 = 4，位置 4 是空的，放
9: [5, _, 12, 8, 9]
2.4 两种方法的对比
┌─────────────────────────────────────────────────┐
│ 冲突解决方法对比 │
├─────────────────────────────────────────────────┤
│ │
│ 链地址法 开放地址法 │
│ ───────── ────────── │
│ 用链表存冲突元素 用空槽存冲突元素 │
│ 桶数量固定 负载因子超过阈值需扩容 │
│ 删除容易 删除复杂（标记删除） │
│ 适合不确定数据量 适合确定数据量 │
│ │
└─────────────────────────────────────────────────┘
三、哈希表的扩容
3.1 为什么要扩容？
面试官追问："哈希表什么时候扩容？为什么？"
负载因子 = 元素数量 / 桶数量
负载因子越大，冲突越多！
- 负载因子 0.5：一半一半，冲突较多
- 负载因子 0.8：非常拥挤
- 负载因子 1.0：满了！
当负载因子超过阈值（通常是 0.75），
就需要扩容！
扩容后：
- 桶数量增加
- 负载因子降低
- 冲突减少
但扩容有代价：需要重新哈希所有元素！
这步是 O(n) 的。
所以：平均 O(1) 插入，偶尔 O(n) 扩容
3.2 扩容时为什么需要重新哈希？
因为哈希值是对桶数量取模！
扩容前：桶数量 = 5
key = 7, 7 % 5 = 2
扩容后：桶数量 = 10
key = 7, 7 % 10 = 7 ← 位置变了！
所以必须重新计算所有元素的哈希值！
四、面试应用
4.1 两数之和（LeetCode 1）
考察点：哈希表的实际应用
问题：数组中找和为 target 的两个数
方法对比：
方法1 - 暴力：
两层循环，O(n²)
方法2 - 排序 + 双指针：
先排序，O(n log n)
方法3 - 哈希表：
遍历数组，对每个数，检查 target - num 是否在哈希表里
是 → 找到
否 → 把当前数加入哈希表
时间：O(n)
空间：O(n)
面试加分点：能解释为什么哈希表能解决这个问题
"因为对于每个数，我只需要知道"配对的那个数是否存在"
这是 O(1) 的查询操作！"
4.2 LRU 缓存（LeetCode 146）
考察点：哈希表 + 双向链表
问题：实现 LRU 缓存
需要操作：
1. get(key) - O(1)
2. put(key, value) - O(1)
O(1) 的 get → 哈希表
O(1) 的 删除"最近最少使用" → 双向链表
为什么用双向链表？
- 删除操作需要找到前驱节点
- 单链表无法 O(1) 找到前驱
- 双向链表可以！
结构：
哈希表 → 双向链表（按访问顺序排列）
最近使用的在头部
最久未使用的在尾部
五、面试总结
哈希表核心要点
┌─────────────────────────────────────────────────┐
│ 哈希表 │
├─────────────────────────────────────────────────┤
│ │
│ 核心思想：哈希函数 + 数组 = O(1) 查找 │
│ │
│ 冲突处理： │
│ - 链地址法：用链表存冲突元素 │
│ - 开放地址法：找空位置存 │
│ │
│ 扩容：当负载因子 > 0.75，扩容 + 重新哈希 │
│ │
│ 应用： │
│ - 两数之和 │
│ - LRU 缓存 │
│ - 字符串计数 │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释为什么是 O(1)
"通过哈希函数直接计算位置，不需要遍历"
2. 能解释冲突处理
"链地址法用链表存冲突元素，开放地址法找空位"
3. 能解释扩容
"负载因子超过阈值时扩容，通常是 0.75"
4. 能设计哈希表 + 链表的组合
"LRU 缓存用哈希表 O(1) 查找，用双向链表 O(1) 删除"
相关题目
- LeetCode 1 - 两数之和 - 哈希表基础
- LeetCode 146 - LRU 缓存 - 哈希表 + 链表
- LeetCode 128 - 最长连续序列 - 哈希表应用