哈希表专题导读

链表专题告一段落，本篇开启新的专题：哈希表。如果说链表训练的是"指针操作的严谨"，哈希表训练的就是"工具选择的判断力"——什么时候用数组、什么时候用 Set、什么时候用 Map，选错了载体，代码要么写不对，要么白白浪费空间。

一、哈希原理：用函数换时间

哈希表的核心思想一句话就能说清：通过哈希函数，把关键码映射到存储位置，从而用 O(1) 的期望时间完成查找。

key --哈希函数 h()--> 下标 index --数组--> O(1) 定位

没有哈希表时，判断"某个元素在不在集合里"只能遍历，O(n)；有了哈希表，"在不在"这个问题被压缩成一次下标计算。这就是哈希的本质：用空间和一次函数计算，换取 O(n) 到 O(1) 的查找加速。

不过映射不一定一一对应：两个不同的 key 可能算出同一个下标，这就是哈希冲突。

二、冲突解决：链地址法与开放寻址法

Java 面试高频问题，两种主流策略都要能说出来：

2.1 链地址法（拉链法）

数组的每个槽位后面挂一条链表，冲突的元素依次接在链上。查找时先定位到槽位，再在链表里顺序比对。JDK 8 之后的 HashMap 就是这个方案，并且做了优化：链表长度超过 8 且数组容量达到 64 时，链表转红黑树，把最坏退化从 O(n) 压到 O(log n)。

槽位:  [0] -> (a) -> (b)
       [1] -> (c)
       [2] -> (d) -> (e) -> (f)   <- 长链可能转红黑树

2.2 开放寻址法

冲突后不挂链，而是在数组里继续探测下一个可用位置。最简单的是线性探测：位置被占了就看下一个，直到找到空位。缺点是元素堆积（"聚集"）后探测会变长，且删除元素需要特殊标记（直接置空会截断探测路径）。ThreadLocalMap 用的是这套方案。

维度	链地址法	开放寻址法
冲突处理	槽位挂链表	向后探测空位
删除	正常删除节点	需墓碑标记
空间利用	可超过装填因子 1	装填因子须小于 1
典型实现	JDK HashMap	ThreadLocalMap

刷题阶段不必手写这些结构，Java 的 HashMap/HashSet 开箱即用；但原理要懂，它是后续理解"为什么设计哈希集合/哈希映射"类题目的基础。

三、Java 三种哈希载体怎么选

刷哈希题时，载体只有三种候选。选型的第一依据是关键码的值域特征，第二依据是要不要存附加信息。

3.1 三者对比表

载体	适用关键码	查找	优势	局限
`int[26]` 数组	值域小且可枚举（如小写字母）	O(1)	无装箱、无哈希开销，最快最省	值域一大就要爆内存
`HashSet`	只需回答"在不在"	O(1)	自动去重，语义清晰	存不下附加信息
`HashMap`	需要存"key 对应的值"	O(1)	一并携带次数/下标等数据	开销略高于数组

3.2 代码形态

// 载体一：数组——只统计小写字母时首选
int[] count = new int[26];
count[c - 'a']++;
 
// 载体二：HashSet——只关心存在性
Set<Integer> seen = new HashSet<>();
seen.contains(x); seen.add(x);
 
// 载体三：HashMap——key 之外还要带数据
Map<Character, Integer> freq = new HashMap<>();
freq.merge(c, 1, Integer::sum); // 计数常用写法

一个经验法则：小写字母统计直接上 int[26]；值域是无界的 int/String 就在 Set 和 Map 里选——只判存在选 Set，还要次数或位置选 Map。

四、哈希的三大使用场景

哈希题的问法千变万化，但剥开壳只有三种诉求：

查存在："这个元素见过吗？"——典型如两数之和里查 target - nums[i] 是否出现过、两个数组的交集。
计频率："这个元素出现了几次？"——典型如有效的字母异位词、赎金信，本质是拿计数数组互相比对。
建映射："这个 key 对应什么信息？"——典型如两数之和里"值 -> 下标"的映射、四数相加 II 里"A+B 的和 -> 出现次数"。

做题时先问自己属于哪一种，载体选择基本就定下来了。

五、LeetCode 题单清单

按推荐学习顺序整理，并标注每题的推荐载体：

题号	题名	一句话考点	推荐载体
242	有效的字母异位词	26 长度计数数组互比	`int[26]` 数组
349	两个数组的交集	求交集并去重	HashSet（结果集 + 查重集）
202	快乐数	判断循环：重复数字即死循环	HashSet 记录出现过的和
1	两数之和	一遍扫 + 查补数是否存在	HashMap（值 -> 下标）
454	四数相加 II	分两组，统计和的出现次数	HashMap（和 -> 次数）
383	赎金信	242 的变体，计数做减法	`int[26]` 数组
15	三数之和	排序 + 双指针收缩，哈希去重反而麻烦	数组 + 双指针
18	四数之和	15 的扩展，两层循环 + 双指针，防溢出	数组 + 双指针

注意最后两题是特例：15 和 18 的正解是排序 + 双指针而不是哈希。因为它们要求返回的是不重复的元组本身，用哈希去重非常繁琐；而"凑和"类题目（1、454）里哈希才是主场。把"哪题用哈希、哪题不用"也纳入选型思考，是这个专题真正的收获。

六、学习方法建议

先写 242 和 1，把"计数数组"和"一遍扫描查映射"两个模板焊牢，后面的题大多是它们的变形；
每道题动笔前，先口头回答三个问题：关键码值域多大？要存什么附加信息？属于查存在、计频率还是建映射？
349/202 这类"判存在"的题，写完可以想想：如果值域只有 26 个字母，能不能换成数组加速？

参考

代码随想录 · 哈希表专题