专题 02哈希表

2.1哈希表的本质：拿空间换一次查找

很多数组题的暴力解长这样：「对第 i 个数，再扫一遍后面的数，看有没有我要找的那个」。 内层这遍扫描，是 O(n) 的查找。哈希表要解决的，就是把这次查找变成 O(1)。

O(1) 是怎么来的

哈希表内部是一个数组（叫「桶」）。它用一个哈希函数把 key 算成一个整数下标，直接定位到桶里的位置： 存的时候放进去，查的时候用同样的哈希函数算下标、一步拿到。只要哈希函数足够均匀、冲突不多， put 和 get 都接近常数时间。

「拿空间换时间」到底换了什么

代价是额外内存：你为那 n 个数额外开了哈希表（大约 O(n) 空间）。收益是时间： 把 O(n²) 砍成 O(n)。刷题（和面试）里，这个交换几乎是永远划算的——除非题目明说「O(1) 空间」。

一个直觉例子（先不写代码）

假设要找一个数组里「有没有两个数加起来等于 10」。暴力是两层循环枚举所有对。 换哈希思路：一边遍历，一边把走过的数记到哈希表里；每走到一个新数 x，就查一下 10 - x 在不在表里。 在，就找到了；不在，就把 x 存进去继续。整个过程中，每个数只被看一次，查找是 O(1)——这正是下一节两数之和的思路。

2.2Java 哈希三件套怎么选

Java 里「哈希」相关工具有好几个，初学者最容易乱用。其实按需求选，只有三件：

① HashMap：键值对，要「通过 key 找 value」

当你需要「记住某个东西，并且以后通过它反查另一个东西」时用。典型：两数之和里存「数值 → 下标」。

Map<Integer, Integer> map = new HashMap<>();
map.put(7, 1);            // 把 7 和下标 1 绑定
int idx = map.get(7);     // O(1) 拿到 1

② HashSet：只要「存在性」，不关心对应的值

当你只需要回答「这个数我见过没有」，不需要记下标或其他信息，用 HashSet（它其实就是 value 被忽略的 HashMap）。 典型：最长连续序列里判断「x+1 在不在」。注意 Set.contains 才是 O(1)，List.contains 是 O(n)，别用错容器。

Set<Integer> set = new HashSet<>();
set.add(3);
boolean seen = set.contains(3);  // O(1)

③ int[26] / int[128] 数组计数：键是小范围整数时最快

如果「键」是有限的、范围小的整数（比如小写字母只有 26 个、ASCII 128 个），直接用数组当下标比 HashMap 还快： 数组访问是纯机器层面的 O(1)，没有哈希计算、没有装箱。这是面试加分项——看到「字母频次」就条件反射用 int[26]。

int[] count = new int[26];
count[s.charAt(i) - 'a']++;   // 'a'→0, 'b'→1 ... 直接当下标

一个具体对比：数一下「a」出现了几次

假设要统计字符串里字母 'a' 的出现次数，两种写法都正确，但差别一目了然：

// 写法 A：HashMap（通用但啰嗦、有装箱开销）
Map<Character, Integer> m = new HashMap<>();
m.put('a', m.getOrDefault('a', 0) + 1);

// 写法 B：int[26]（键是小写字母时的首选）
int[] count = new int[26];
count['a' - 'a']++;   // 直接当下标，无哈希、无装箱

写法 B 没有哈希计算、没有 Integer 装箱拆箱，数组访问就是一次加法取址，又快又省。 面试信号：看到「字母 / ASCII / 0~10⁵ 小范围整数 + 频次统计」就先想数组，再用 HashMap 兜底—— 这个下意识的的选择本身就能给面试官留下好印象。

2.3两数之和（简单，力扣 1）

简单 核心：边遍历边查 complement

题意：给定数组 nums 和整数 target，找出和为 target 的两个元素的下标（假设恰好一组解，且不能重复使用同一个元素）。 例：nums = [2,7,11,15], target = 9，因为 2 + 7 = 9，返回 [0, 1]。

思路推导

第一步，暴力。两层循环枚举所有 (i, j)，看 nums[i] + nums[j] == target，O(n²)。n 到 10⁴ 就超时。

第二步，把内层循环翻译成查找。固定 i 时，我们要找的其实是「target - nums[i] 这个值，在数组里出现过吗，下标是多少」。 这就是 2.1 节说的「在已遍历元素里找一个数」。如果我们能把「走过的数 → 它的下标」用哈希记下来， 这层查找就是 O(1)。

第三步，边走边查、先查后存。遍历到第 i 个时，先算 need = target - nums[i]，去哈希表查 need： 查到了，说明前面有个下标 j 满足 nums[j] == need，而 nums[j] + nums[i] == target，直接返回 [j, i]； 查不到，就把当前 (nums[i], i) 存进表，继续。

为什么「先查后存」能保证不重复使用同一元素？因为当前元素 nums[i] 在查的时候还没被存进表， 所以不可能和自己配对（need 若等于 nums[i]，表里没有它，不会误返回 [i, i]）。

参考代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // 数值 → 下标
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];             // 我们要找的另一个数
            if (map.containsKey(need)) {             // 它在之前出现过吗？
                return new int[]{map.get(need), i};  // 出现过，返回两个下标
            }
            map.put(nums[i], i);                     // 没出现，把当前值和下标记下来
        }
        return new int[]{};                          // 题目保证有解，这里只是语法兜底
    }
}

复杂度

O(n) 时间（只遍历一遍，查找均摊 O(1)），O(n) 空间（哈希表最多存 n 个数）。相比暴力 O(n²)，这是哈希换时间的典型胜利。

2.4有效的字母异位词（简单，力扣 242）

简单 核心：数组计数取代 HashMap

题意：给定两个字符串 s 和 t，判断它们是否字母异位词—— 即包含完全相同的字母、且每种字母出现次数相同，只是顺序可以不同。字符串只含小写字母。 例：s="anagram", t="nagaram" → true；s="rat", t="car" → false。

思路推导

第一步，暴力 / 排序。把两个串排序后直接比是否相等，O(n log n)。能过，但不是最优，且没用到「只有小写字母」这个条件。

第二步，异位词的等价定义。两串是异位词 ⇔ 每个字母的出现次数一模一样。 那我们只要各自数出 26 个字母的频次，比对频次数组即可。

第三步，为什么用 int[26] 而不是 HashMap。字母只有 26 种，固定且范围小，用数组当下标最快： count[ch - 'a'] 就是字母 ch 的桶。我们甚至可以只用一个数组：遍历 s 时对应桶 +1，遍历 t 时对应桶 -1， 最后数组全为 0 说明两串频次完全抵消、是异位词。先比长度能提前剪枝（长度不同必不是）。

参考代码

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false; // 长度不同，必不是异位词，直接返回
        int[] count = new int[26];                   // 26 个小写字母的计数桶
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;              // s 里出现一次，对应桶 +1
            count[t.charAt(i) - 'a']--;              // t 里出现一次，对应桶 -1
        }
        for (int c : count) {
            if (c != 0) return false;                // 有任何一个桶不为 0，频次不一致
        }
        return true;
    }
}

复杂度

O(n) 时间（两遍遍历 + 一遍查 26 个桶），O(1) 空间（固定 26 长度数组，与 n 无关）。比排序法更快且更体现「小范围整数用数组」的意识。

2.5字母异位词分组（中等，力扣 49）

中等 核心：设计「签名」当 key

题意：给定字符串数组 strs，把其中互为字母异位词的字符串分到同一组，返回分组结果（组内顺序、组间顺序不限）。 例：strs = ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"], ["tan","nat"], ["bat"]]。

思路推导

第一步，暴力。每两个串比较是否异位词（复用 2.4 的计数法），O(n²·k)，n 大必超时，而且「比较」本身很笨重。

第二步，关键洞察——异位词有共同的「签名」。如果把一个串的字母排序，那么所有互为异位词的串，排序后一定得到同一个字符串。 比如 "eat"、"tea"、"ate" 排序后都是 "aet"。这个排序串就是它们的「分组身份证」。

第三步，用 HashMap 把同签名归拢。key = 排序后的串，value = 这组原串的列表。 遍历每个串，算它的签名，把原串加进对应列表。最后把所有列表收回来就是答案。 为什么这样对？因为签名相同的串必然互为异位词（排序结果相同 ⇔ 字母频次相同），签名不同的一定不是——分组恰好正确。

第四步，key 的设计还有更优解（面试加分）。排序串要对每个串做 O(k log k)（k 是串长）。 其实可以改用「计数串」当 key：统计 26 字母频次，拼成 "a1e1t1" 这样的字符串当 key，只需 O(k)。 两者思路一致，计数串避免排序、常数更优，面试时提一句能显得你考虑过效率。

参考代码（排序串为 key）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);                 // 异位词排序后一定相同，作为分组 key
            String key = new String(cs);
            // 没有这个 key 就新建列表，有就直接把原串加进去
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values()); // 把所有分组作为结果返回
    }
}

复杂度

排序串方案：O(n · k log k)（n 个串、每个排序 O(k log k)），O(n·k) 空间（存 key 和原串）。 计数串方案：O(n·k) 时间，更优。两种都能过。

2.6最长连续序列（中等，力扣 128）

中等 核心：HashSet + 只从起点数

题意：给定未排序的整数数组 nums，找出最长连续递增序列的长度 （序列中的数字必须连续且按数值递增，如 [1,2,3,4] 长度 4，但 [1,2,4] 不算连续因缺 3）。 例：nums = [100,4,200,1,3,2] → 最长连续序列是 [1,2,3,4]，返回 4。

思路推导

第一步，排序法。先排序再数连续段，O(n log n)。题目要求进阶 O(n)，所以要想办法去掉排序。

第二步，用 HashSet 把查找变 O(1)。把所有数丢进 HashSet，这样「x 在不在数组里」一查便知。 连续序列的本质是：从某个数 x 出发，不断检查 x+1, x+2, ... 在不在。

第三步，灵魂优化——只从「序列起点」开始数。什么叫起点？就是数组里没有 x-1 这个数的 x。 为什么只数起点就够了？因为对于任意一个连续段（比如 1,2,3,4），我们只在最前面的 1 处才会发起「往后数 2,3,4」； 而 2、3、4 这些非起点（它们的前一个数都在数组里）我们主动跳过，不去重复发起计数。 这样每个数最多被「数」一次，总工作量 O(n)。

第四步，正确性直觉。每个连续段只在它的最小元素处被完整数一遍；段内其他元素因「前驱存在」被跳过，不会漏数也不会重复数。 max 记录历史最长即可。

参考代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);     // 全部入集合，后续查找 O(1)
        int ans = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue; // x 不是序列起点（前面还有），跳过
            int cur = x, len = 1;
            while (set.contains(cur + 1)) {     // 从 x 往后数连续的数
                cur++; len++;
            }
            ans = Math.max(ans, len);           // 更新历史最长
        }
        return ans;
    }
}

复杂度

O(n) 平均时间（每个数入集合一次、被「数」最多一次，HashSet 操作均摊 O(1)），O(n) 空间（集合）。这是「HashSet 去重 + 起点剪枝」的典范。

2.7本专题常见坑

2.8自测题