引言：哈希 —— 算法世界的第一把加速器

在刷题初期，我们常被暴力解法的 O(n²) 甚至 O(n³) 折磨。而哈希表，往往是打破僵局的第一把钥匙。它不依靠复杂的逻辑推理，而是凭借 “记住已经见过的东西” 这种朴素思想，让查找从线性变为常数。

Java 中的 HashMap 和 HashSet 是哈希表的两种基本形态。前者存储键值对，后者只存键（本质上是值为常量的 HashMap）。它们平均时间复杂度均为 O(1)，代价是额外的内存开销。这正是 “空间换时间” 的典型体现。

LeetCode 热门 100 题中，有三道题是哈希表的"代言人"：第 1 题、第 49 题、第 128 题。它们分别展示了哈希在 配对查找、归类聚合、连续性判断 三个不同维度的应用。下面逐一拆解。

1. 两数之和（LeetCode 1）

题目：在无序数组中，找到两个数，使它们的和等于目标值，返回下标。

暴力法：双重循环枚举所有组合，O(n²)。当 n 很大时必然超时。

哈希优化思路：遍历数组时，对于当前数 nums[i]，我们只需要知道 之前是否出现过 target - nums[i]。如果出现过，就找到了答案。如果没有，就把当前数存入哈希表，供后续元素查找。

具体步骤：

• 初始化一个空 HashMap<Integer, Integer>，键为数值，值为下标。
• 从左到右遍历数组，对每个元素 x：
  • 计算 complement = target - x。
  • 查询哈希表是否包含 complement。若包含，直接返回 {map.get(complement), i}。
  • 若不包含，将 (x, i) 存入哈希表。

为什么高效？ 因为哈希表的查找和插入都是 O(1)，所以整体复杂度降为 O(n)。这个思路的本质是 “用空间记录历史，避免未来重复查找”。

易错点：不能先把所有元素存入哈希表再查找，因为这样可能匹配到同一个元素两次（例如 [3,3] target=6，如果先存再找，会返回 (0,0)）。边遍历边存，天然避免了这个问题。

2. 字母异位词分组（LeetCode 49）

题目：给定字符串数组，将字母异位词（由相同字母不同排列组成）分到同一组。

暴力法：两两比较每个字符串是否是异位词，复杂度 O(n² * L log L)，不可接受。

哈希优化思路：异位词的本质是 字母构成完全相同。那么，我们可以找到一个 归一化标识，使得所有异位词的标识相同。最直接的方法就是 排序：对字符串的字符数组排序，排序后的结果就是唯一标识。

具体步骤：

• 创建一个 HashMap<String, List<String>>，键为排序后的字符串，值为异位词列表。
• 遍历所有字符串 s：
  • 将 s 转换为字符数组，排序，再转回字符串 key。
  • 若哈希表中不存在 key，新建一个 ArrayList 放入。
  • 将 s 添加到该 key 对应的列表中。
• 最后返回哈希表的所有 value 组成的列表。

为什么高效？ 每个字符串只需一次排序（O(L log L)）和一次哈希操作，总体时间复杂度为 O(n * L log L)，远优于两两比较。

进一步优化：如果字符串长度很长，排序开销变大，可以用 字母计数 作为键：统计每个字符出现次数，拼接成 "a3b1c2" 这种形式。但排序在 Java 中更简洁，且实际题量下足够。

关键点：哈希表在这里充当了 “分类器”，将具有相同特征（排序后相等）的元素聚合到一起，避免了嵌套循环的碰撞判断。

3. 最长连续序列（LeetCode 128）

题目：给定未排序的整数数组，找出最长的连续数字序列（如 [100,4,200,1,3,2] 中最长连续序列为 [1,2,3,4]，长度为 4）。

暴力法：排序后遍历，复杂度 O(n log n)，但题目要求 O(n)，所以排序不可取。

哈希优化思路：我们只需要 从每个连续序列的起点开始 计数。如何判断一个数是否是起点？—— 如果 num - 1 不在数组中，则 num 就是起点。这样，我们只需对每个起点向后查找 num+1, num+2...，直到断掉。

具体步骤：

• 将所有数存入 HashSet<Integer>，去重并支持 O(1) 查找。
• 遍历集合中的每个数 num：
  • 如果 set.contains(num - 1)，说明 num 不是起点，直接跳过（因为它的序列会被起点统计）。
  • 否则，从 num 开始，用 while (set.contains(current)) 递增计数，记录长度。
  • 更新全局最大长度。

为什么高效？ 每个数最多被访问两次：一次作为起点被扫描序列，一次被跳过（作为非起点）。所以总复杂度 O(n)。

易错点：必须遍历 HashSet 而不是原数组，避免重复处理相同数字。另外，在 while 循环中，每次 current++ 时，不必从集合中删除当前数，因为后面不会再遇到（即使遇到也会被跳过或已处理），但删除可以略微加速，不是必须。

三题对比与启发

共同本质：都是利用哈希表的 “存在性查询” 能力，将原本需要嵌套循环的匹配问题，转化为单次遍历中的即时判断。

不同侧重：

• 两数之和：查询的是 “补数是否存在”，属于一对一匹配。
• 字母异位词分组：查询的是 “是否存在相同的归一化键”，属于一对多归类。
• 最长连续序列：查询的是 “下一个数是否存在”，属于链式延伸。

总结：哈希模块的核心心法

哈希表是一种"记忆"工具。它让我们在遍历过程中，能够瞬间回想起之前见过的任何元素，从而避免重复扫描。

应用哈希表的通用步骤：

1. 识别问题中是否存在 “查找” 或 “判断存在” 的需求。
2. 确定 键 是什么（原始值、变换后的值、组合值）。
3. 确定 值 是什么（下标、计数、列表、布尔标志）。
4. 遍历数据，边处理边维护哈希表，利用实时信息决策。

掌握这三道经典题，你就掌握了哈希表在算法竞赛中的绝大多数应用场景。后续遇到类似"求和"、“分组”、“连续"等关键词，第一反应就应该想到哈希表。

扩展思考

• 如果两数之和要求返回所有不重复的组合，哈希表如何处理？—— 可以排序后使用双指针，或者哈希表记录频次。
• 如果字母异位词分组要求按出现顺序输出，如何保证顺序？—— 使用 LinkedHashMap 或单独维护顺序列表。
• 如果最长连续序列要求返回具体序列而不是长度，如何修改？—— 在 while 循环中收集元素即可。

哈希表并非万能，当键值规模极大或哈希冲突严重时，可能退化为 O(n) 甚至更差。但在面试和竞赛中，它始终是解决问题的首选利器之一。