算法面试突击手册 —— 哈希表

一、概念与特点

大白话 + 类比

哈希表 = 图书馆的索引卡片柜

你去图书馆找一本书，如果一本一本翻架子，可能要翻几小时（O(n)）。但如果有一个卡片柜，每张卡片上写着书名 → 书架位置，你查到卡片就能直接走过去拿书。这就是哈希表：用 key 瞬间定位 value，查询 O(1)。

哈希函数就像”分类员”：你把书名给它，它告诉你卡片在哪个抽屉。好的哈希函数让每个抽屉的卡片数量均匀；不好的哈希函数会把所有卡片塞进同一个抽屉（哈希冲突），那就退化成翻抽屉了。

核心特征（什么时候该想到用它）

特征	说明
O(1) 查找	需要频繁查询某个值是否存在
key-value 映射	需要建立元素和某个信息的对应关系
去重 / 计数	统计出现次数、判断重复
”之前见过”	遍历时想知道当前元素之前是否出现过

识别信号词

题目中出现这些关键词，优先考虑哈希表：

“两数之和”、“是否存在”、“查找” → 用 HashMap 存值→下标
“出现次数”、“频率”、“重复” → 用 HashMap 计数
“最长连续”、“去重” → 用 HashSet 快速判断存在性
“只出现一次” → 优先考虑异或，其次 HashMap
“分组”、“分类” → HashMap<String, List> 模式

二、应用场景

五大套路模板

套路	典型题	HashMap 存什么
值→下标	Two Sum	`map<值, 下标>` 遍历时回头查
值→次数	Majority Element, Group Anagrams	`map<值, 出现次数>`
值→是否存在	Longest Consecutive	`set<值>` 只关心存在性
异或去重	Single Number	不显式用 HashMap，用异或性质
分组归类	Group Anagrams	`map<特征key, List<成员>>`

Java 常用操作速查

Map<Integer, Integer> map = new HashMap<>();
map.put(key, val);           // 存
map.get(key);                // 取（不存在返回 null）
map.getOrDefault(key, 0);    // 取，不存在返回默认值
map.containsKey(key);        // 是否包含 key
map.remove(key);             // 删除
for (Map.Entry<Integer, Integer> e : map.entrySet()) { } // 遍历

Set<Integer> set = new HashSet<>();
set.add(x);                  // 添加
set.contains(x);             // 是否存在
set.remove(x);               // 删除

三、Hot 100 精讲题目

1. Two Sum 两数之和

📌 给定一个整数数组 nums 和一个目标值 target，找出和为 target 的两个数的下标。假设只有一组解。

🔍 解题分析

为什么用哈希表：暴力双循环 O(n²)。我们想要的是：遍历到 nums[i] 时，立刻知道 target - nums[i] 之前有没有出现过。这正是哈希表的专长。

核心思路（一步步拆解）：

初始化一个空的 HashMap，key=数值，value=下标
从左到右遍历数组
对每个 nums[i]，计算 complement = target - nums[i]
查看 complement 是否在 HashMap 中
如果在，返回 [map.get(complement), i]
如果不在，把 (nums[i], i) 存入 HashMap，继续

易错点：不能先把所有元素放入 HashMap 再查找，否则像 nums=[3,3], target=6 这种情况，同一个元素会被用两次。

✅ 完整 Java 实现

public int[] twoSum(int[] nums, int target) {
    // key = 数值, value = 该数值在数组中的下标
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i]; // 我需要找的搭档

        // 回头看一眼：我需要的那个人之前出现过吗？
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }

        // 把自己登记在册，供后来的人查找
        map.put(nums[i], i);
    }

    return new int[]{-1, -1}; // 不会走到这里，题目保证有解
}

⏱ 复杂度分析

时间复杂度：O(n) —— 每个元素遍历一次，HashMap 查找 O(1)
空间复杂度：O(n) —— 最坏情况存 n 个元素

💡 记忆口诀

“边看边登记，回头找搭档”

49. Group Anagrams 字母异位词分组

📌 给定字符串数组，将字母异位词（相同字母不同排列）分到同一组。如 ["eat","tea","tan","ate","nat","bat"] → [["bat"],["nat","tan"],["ate","eat","tea"]]

🔍 解题分析

为什么用哈希表：需要把”同一类”的字符串聚合。关键问题是：怎么给每种异位词生成一个统一的”分类 key”？两种方法：

排序法："eat" 和 "tea" 排序后都是 "aet"，用它做 key
计数法：用 #a1#e1#t1 这种编码做 key

核心思路：

创建 HashMap，key = 排序后的字符串（或计数编码），value = 原始字符串列表
遍历每个字符串，排序得到 key
把原字符串加到对应 key 的列表中
返回所有列表

易错点：返回 new ArrayList<>(map.values()) 即可，不需要再复制。

✅ 完整 Java 实现

public List<List<String>> groupAnagrams(String[] strs) {
    // key = 排序后的字符串, value = 同一组异位词的列表
    Map<String, List<String>> map = new HashMap<>();

    for (String s : strs) {
        // 核心：把字符串排序作为统一标识
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars); // "eat" → "aet"

        // 如果这个 key 还没出现过，新建一个列表
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(s);
    }

    return new ArrayList<>(map.values());
}

⏱ 复杂度分析

时间复杂度：O(n·klogk)，n 个字符串，每个长度 k 排序
空间复杂度：O(n·k)，存储所有字符串

💡 记忆口诀

“字母异位都一样，排序之后一个样”

128. Longest Consecutive Sequence 最长连续序列

📌 给定未排序的整数数组，找出最长连续序列的长度。要求 O(n) 时间。如 [100,4,200,1,3,2] → 4（序列为 [1,2,3,4]）

🔍 解题分析

为什么用哈希表：O(n) 时间要求，不能用排序。我们只关心”一个数是否存在于数组中”，这是 HashSet 的专长。

核心思路（关键技巧）：

把所有数字放入 HashSet
遍历每个数字 num
核心剪枝：只有当 num-1 不在 Set 中时，才说明 num 是一个连续序列的起点
从起点开始，不停检查 num+1, num+2, ... 是否在 Set 中
统计最长长度

为什么这样是 O(n)：虽然有两层循环，但每个数字最多被访问两次（一次作为起点检查，一次在某个序列内部被访问）。只有作为”起点”时才会进入内层 while 循环。

易错点：必须加 if (!set.contains(num - 1)) 剪枝，否则退化成 O(n²)。

✅ 完整 Java 实现

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);   // 全部扔进 HashSet，O(1) 判断存在性
    }

    int maxLen = 0;

    for (int num : set) {
        // 关键剪枝：只从序列的"起点"开始计数
        // 如果 num-1 存在，那 num 不是起点，跳过
        if (!set.contains(num - 1)) {
            int currentNum = num;
            int currentLen = 1;

            // 向后延伸，数这个连续序列有多长
            while (set.contains(currentNum + 1)) {
                currentNum++;
                currentLen++;
            }

            maxLen = Math.max(maxLen, currentLen);
        }
    }

    return maxLen;
}

⏱ 复杂度分析

时间复杂度：O(n) —— 每个数字最多进入内层循环 1 次
空间复杂度：O(n) —— HashSet 存储

💡 记忆口诀

“全扔 Set 里，只从起点往前数”

136. Single Number 只出现一次的数字

📌 非空整数数组，除一个数只出现一次外，其余每个数都出现两次。找出那个只出现一次的数。要求 O(n) 时间，O(1) 空间。

🔍 解题分析

为什么不用 HashMap：HashMap 需要 O(n) 空间，但题目要求 O(1) 空间。这里用到异或运算的性质：

a ⊕ a = 0（相同为 0）
a ⊕ 0 = a（与 0 异或等于自己）
交换律和结合律：a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

核心思路：把数组中所有数字异或起来，成对的互相抵消为 0，最后剩下的就是落单的那个数。

类比他：就像参加舞会，一个一个人进房间。第一个进去独自跳舞；第二个相同的人进去，两人配对消失。最后留在房间里跳舞的就是那个单身狗。

✅ 完整 Java 实现

public int singleNumber(int[] nums) {
    int result = 0;

    for (int num : nums) {
        result ^= num; // 异或：相同的消掉，最后剩下那个单身的
    }

    return result;
}

⏱ 复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

💡 记忆口诀

“全部异或，成对消失，落单留下”

169. Majority Element 多数元素

📌 找出数组中出现次数超过 ⌊n/2⌋ 的元素。假设一定存在。

🔍 解题分析

这道题有两种解法，面试建议两种都讲：

解法一：HashMap 计数（通用但空间 O(n)）

计数每个元素，找到次数 > n/2 的

解法二：摩尔投票（最优，空间 O(1)）

类比：就像打仗，两军对垒，一换一。多数派人数超过一半，所以无论怎么对冲，最后剩下的兵一定是多数派的。

核心思路（摩尔投票）：

初始化 candidate = 0, count = 0
遍历数组：
- 如果 count == 0，当前元素成为新的 candidate
- 如果当前元素 == candidate，count++
- 如果当前元素 != candidate，count—（一换一）
最后剩下的 candidate 就是多数元素

为什么正确：多数元素超过 n/2，意味着即使所有其他元素都和它对冲，它至少还剩 1 个人。

✅ 完整 Java 实现

// 解法一：HashMap 计数（面试先写这个，展现基本功）
public int majorityElement_HashMap(int[] nums) {
    Map<Integer, Integer> countMap = new HashMap<>();
    int majority = nums[0];

    for (int num : nums) {
        countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        if (countMap.get(num) > nums.length / 2) {
            majority = num;
            break;
        }
    }
    return majority;
}

// 解法二：摩尔投票（展现深度理解）
public int majorityElement(int[] nums) {
    int candidate = 0;  // 当前候选人
    int count = 0;      // 候选人当前票数

    for (int num : nums) {
        // 弹尽粮绝，换候选人
        if (count == 0) {
            candidate = num;
        }
        // 是自己人就加一，是敌人就同归于尽一个
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

⏱ 复杂度分析

时间复杂度：O(n)
空间复杂度：HashMap O(n) / 摩尔投票 O(1)

💡 记忆口诀

“两军对垒一换一，人数过半必胜利”

🔜 下一章：02-双指针

算法手册 01 哈希表

算法面试突击手册 —— 哈希表

一、概念与特点

大白话 + 类比

核心特征（什么时候该想到用它）

识别信号词

二、应用场景

五大套路模板

Java 常用操作速查

三、Hot 100 精讲题目

1. Two Sum 两数之和

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

49. Group Anagrams 字母异位词分组

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

128. Longest Consecutive Sequence 最长连续序列

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

136. Single Number 只出现一次的数字

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀

169. Majority Element 多数元素

🔍 解题分析

✅ 完整 Java 实现

⏱ 复杂度分析

💡 记忆口诀