LeetCode（一）—— 哈希表

哈希表是算法面试和实际系统中投资回报率最高的数据结构之一：通过牺牲少量内存开销换取快速的成员查询和查找操作，可以将"扫描所有元素"的暴力解法优化为接近线性的高效算法。本文通过三个经典 LeetCode 问题——两数之和、最长连续序列和字母异位词分组——系统性地构建可复用的哈希表思维模式，教你如何设计键值、如何存储数据，以及如何避免常见的边界情况错误。我们还将深入探讨高级模式（互补搜索、频率统计、滑动窗口）、性能对比、面试技巧和调试清单。

系列导航

📚 LeetCode 算法精讲系列（共 10 篇）：

1. → 哈希表（两数之和、最长连续序列、字母异位词分组）← 当前文章
2. 双指针技巧（对撞指针、快慢指针、滑动窗口）
3. 链表操作（反转、环检测、合并）
4. 二叉树遍历与递归（中序/前序/后序、最近公共祖先）
5. 动态规划入门（一维/二维 DP 、状态转移）
6. 回溯算法（排列、组合、剪枝）
7. 二分查找进阶（整数/实数二分、答案二分）
8. 栈与队列（单调栈、优先队列、双端队列）
9. 图算法（ BFS/DFS 、拓扑排序、并查集）
10. 贪心与位运算（贪心策略、位操作技巧）

---

哈希表基础回顾

什么是哈希表？

图书馆找书的故事

想象你在一个有10000本书的图书馆找书：

方法1：笨办法（线性查找） - 从第一本书开始，逐个翻看书名 - 运气不好的话，要看10000本才找到 - 时间：很慢！ 时间复杂度

方法2：聪明办法（哈希表） - 图书馆按"首字母+分类"给书编号 - 想找《Python 入门》？ - 计算编号：P（首字母）+ 编程类 = 15号书架 - 直接去15号书架，一次就找到！ - 时间：很快！ 时间复杂度

哈希表就是"方法2"的数学实现！

哈希表的三要素

要素1：键（Key） - 就像书名《Python 入门》 - 你用来查找的东西

要素2：哈希函数（Hash Function） - 就像"首字母+分类→编号"的计算器 - 把键转换成数组位置 - 例如：hash("Python入门") = 15

要素3：数组（Array） - 就像图书馆的一排排书架 - 每个书架有个编号（数组索引） - 直接通过编号就能找到位置

技术定义

哈希表（ Hash Table）是一种根据键（ Key）直接访问内存存储位置的数据结构。通过哈希函数将键映射到数组的某个位置，从而实现平均 时间复杂度的查找、插入和删除操作。

核心优势：

• 快速查找：平均 时间复杂度
• 灵活键类型：不仅限于整数，可以是字符串、元组等
• 动态扩容：可以根据需要自动调整大小

性能特点：

• 插入：平均
• 查找：平均
• 删除：平均 最坏情况下性能可能退化（例如恶意碰撞），但对于面试题和大多数实际应用场景，平均情况才是关键。

不同语言中的实现

Python：

• dict 是哈希映射（键 → 值）
• set 是哈希集合（仅成员关系）

Java：

• HashMap<K,V> 用于键值对
• HashSet<E> 用于唯一元素

C++：

• unordered_map<K,V> 用于键值对
• unordered_set<T> 用于成员关系

---

LeetCode 1: 两数之和

问题分析

核心难点：这道题的核心挑战在于如何在一次遍历中找到两个数，它们的和等于目标值。暴力解法需要 时间检查所有数对，对于大规模数据效率低下。

解题思路：使用哈希表存储"已访问的值 → 索引"映射。当我们遍历数组时，对于每个当前元素 num，需要的配对是 target - num（互补数）。如果这个互补数已经在哈希表中，说明我们找到了答案；否则，将当前值存入哈希表供后续查找。这种"空间换时间"的策略将时间复杂度从 优化到 。

复杂度分析：

• 时间复杂度： - 单次遍历数组，哈希表查找和插入都是平均
• 空间复杂度： - 最坏情况下需要存储 个元素到哈希表

关键洞察：问题的本质是"查找配对"，哈希表提供了 的平均查找时间，完美契合这个需求。核心是"互补搜索"模式：不是查找 num 本身，而是查找 target - num。

问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

示例：

• 输入：nums = [2,7,11,15], target = 9
• 输出：[0,1]（因为 nums[0] + nums[1] = 2 + 7 = 9）

约束条件：

• 只会存在一个有效答案

暴力解法（用于对比）

朴素思路：检查所有可能的数对

def twoSum_bruteforce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

复杂度分析：

• 时间复杂度：，需要检查所有 个数对
• 空间复杂度：，只使用了常数额外空间

为什么效率低：当 nums.length = 10,000 时，需要执行约 5000 万次操作！

哈希表解法：互补模式

核心洞察：从左到右扫描数组时，维护一个映射关系：

值 → 索引

当你看到 num 时，需要的配对是 target - num（即互补数）。如果它已经在映射中，问题解决；否则，存储当前值和索引。

Python 实现

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 哈希表：存储 值 → 索引 的映射关系
        # 这样可以在 O(1) 时间内查找某个值是否出现过
        seen = {}  # 值 → 索引
        
        # 遍历数组，一次遍历即可找到答案
        for i, num in enumerate(nums):
            # 计算当前元素需要的互补数
            # 如果 num + complement = target，则 complement = target - num
            complement = target - num
            
            # 检查互补数是否已经在哈希表中
            # 如果在，说明找到了配对，立即返回
            if complement in seen:
                # 返回 [较早的索引, 当前索引]
                # seen[complement] 是互补数第一次出现的索引
                return [seen[complement], i]
            
            # 如果互补数不在哈希表中，将当前值存入哈希表
            # 注意：这里在检查之后才存储，避免使用同一个元素两次
            seen[num] = i
        
        # 根据约束条件，应该总是有解，这里返回空列表作为防御性编程
        return []  # 无解（根据约束条件不应该发生）

Java 实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{};
    }
}

为什么这样可行？

一次遍历逻辑：

1. 在索引 处，检查 target - nums[i] 是否之前见过
2. 如果是，立即找到配对
3. 如果不是，存储 nums[i] → i 供后续查找

时间演化过程（对于 nums = [2, 7, 11, 15], target = 9）：

步骤	i	num	complement	seen	操作
1	0	2	7	{}	未找到，存储 {2: 0}
2	1	7	2	{2: 0}	找到！ 返回 [0, 1]

复杂度分析

• 时间复杂度：（单次遍历）
• 空间复杂度：（哈希表最多存储 个条目）

时空权衡：我们牺牲 的内存空间，将时间复杂度从 降低到 。

深入解读

算法原理：为什么这个算法能 work？

哈希表解法的核心在于互补搜索模式。当我们看到元素 nums[i] 时，我们不是查找它本身，而是查找它的"另一半"——target - nums[i]。如果这个互补数之前出现过（存储在哈希表中），我们就找到了完整的配对。

数学证明：假设存在解 (i, j) 使得 nums[i] + nums[j] = target，且 i < j。当算法遍历到索引 j 时： - 此时 nums[i] 已经被处理过，存储在 seen[nums[i]] = i - 当前元素是 nums[j]，计算互补数 complement = target - nums[j] - 因为 nums[i] + nums[j] = target，所以 complement = nums[i] - nums[i] 在 seen 中，算法返回 [i, j] ✅

时间复杂度证明：为什么是 O(n)？

• 外层循环：遍历数组一次，
• 哈希表操作：每次 in 检查和 = 赋值都是平均
• 总时间： 最坏情况：如果所有元素哈希到同一桶（恶意输入），哈希表操作退化为 ，总时间变为 。但这种情况在实际应用中极其罕见，平均情况才是关键。

空间优化：有没有更省空间的方法？

对于这个问题，没有。原因： 1. 需要返回索引：不能排序（会破坏索引），必须存储索引信息 2. 未排序数组：无法使用双指针（需要排序） 3. 一次遍历要求：必须存储已访问元素的信息

变体扩展：如果问题改为"返回两个数的值"（不需要索引），可以： - 先排序，然后使用双指针：时间，空间 - 或者仍然使用哈希表：时间，空间

常见错误分析

错误类型	错误代码	问题	正确做法
插入前检查	seen[num] = i; if complement in seen	可能使用同一元素两次	先检查，后插入
返回顺序	return [i, seen[complement]]	索引顺序错误	return [seen[complement], i]
排序破坏索引	先排序再双指针	丢失原始索引	使用哈希表或存储 (值, 索引) 元组

变体扩展

1. 三数之和：固定第一个数，对剩余部分使用两数之和
2. 四数之和：固定前两个数，对剩余部分使用两数之和
3. 两数之和 II（有序数组）：可以使用双指针，空间
4. 两数之和（ BST）：使用中序遍历 + 双指针

常见陷阱与边界情况

陷阱一：重复值处理

情况：nums = [3, 3], target = 6

问题：如果值重复，存储 值 → 索引 是否仍然有效？

答案：是的，因为我们在覆盖之前先检查：

# 第一次迭代： i=0, num=3
complement = 6 - 3 = 3  # 尚未在 seen 中
seen[3] = 0  # 存储 {3: 0}

# 第二次迭代： i=1, num=3
complement = 6 - 3 = 3  # 在 seen 中找到！
return [seen[3], 1]  # [0, 1]

陷阱二：对"不能使用同一元素两次"的误解

约束说明："你不能重复使用同一个元素"

困惑：这是指相同的值还是相同的索引？

澄清：指的是相同的索引。所以 [3, 3] 且 target = 6 是有效的（不同索引）。

陷阱三：不要排序！

诱惑："让我先排序，然后使用双指针"

问题：排序会破坏原始索引，但题目要求返回原始索引！

解决方案：如果必须使用双指针方法，存储 (值, 原始索引) 元组并按值排序。

陷阱四：返回顺序的差一错误

错误：

return [i, seen[complement]]  # 顺序错误！

正确：

return [seen[complement], i]  # 较早的索引在前

实际应用类比

• 电商："我有 100 元。这两件商品能符合我的预算吗？"
• 交易："这个流中的任何两个订单能否抵消到目标风险敞口？"
• 化学："哪两种反应物结合得到这个分子量？"

---

LeetCode 128: 最长连续序列

问题分析

核心难点：这道题的关键挑战在于如何在 时间内找到最长连续序列，而不使用排序（排序需要 ）。序列元素不需要在原数组中连续，这提示需要快速判断某个数是否存在。

解题思路：使用哈希集合存储所有数字，实现 的成员查询。关键洞察是：只从序列的起点开始计数。一个数字 是序列起点当且仅当 不在集合中。对于每个序列起点，我们向右扩展计数连续数字，这样每个数字最多被访问两次（一次作为起点候选，一次作为序列的一部分），保证了 时间复杂度。

复杂度分析： - 时间复杂度： - 虽然内层有 while 循环，但每个数字最多被访问两次 - 空间复杂度： - 哈希集合存储所有数字

关键洞察：避免重复计算是优化的核心。如果我们从每个数字开始计数，会多次计算同一个序列。通过只从起点开始计数，每个序列只被计算一次。

问题描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 的算法解决此问题。

示例：

• 输入：nums = [100, 4, 200, 1, 3, 2]
• 输出：4（序列是 [1, 2, 3, 4]）

约束条件：

为什么不直接排序？

朴素方法：排序后扫描连续段

def longestConsecutive_sort(nums):
    if not nums:
        return 0
    nums.sort()
    longest = 1
    current = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            continue
        elif nums[i] == nums[i-1] + 1:
            current += 1
        else:
            longest = max(longest, current)
            current = 1
    return max(longest, current)

复杂度：（排序占主导）

问题：违反了 的约束！

哈希集合解法：从序列起点开始

关键洞察：一个数字 是序列起点当且仅当 不在集合中。只从序列起点开始计数；否则，你会多次计算同一个序列。

算法步骤

1. 将所有数字放入集合中，以便 成员查询

2. 对于每个数字 ：

   • 如果 在集合中，跳过（不是起点）
   • 如果 不在集合中，计数连续数字

Python 实现

def longestConsecutive(nums):
    # 边界情况：空数组返回 0
    if not nums:
        return 0
  
    # 将数组转换为集合，实现 O(1) 的成员查询
    # 集合会自动去重，但这对算法没有影响
    num_set = set(nums)
    longest = 0  # 记录最长序列长度
  
    # 遍历集合中的每个数字
    for num in num_set:
        # 关键优化：只从序列起点开始计数
        # 一个数字是序列起点当且仅当 num-1 不在集合中
        # 这样可以避免重复计算同一个序列
        if num - 1 not in num_set:
            current_num = num      # 当前序列的起始数字
            current_length = 1    # 当前序列长度（至少包含 num 本身）
        
            # 向右扩展，计数连续数字
            # 只要 current_num + 1 在集合中，就继续扩展
            while current_num + 1 in num_set:
                current_num += 1      # 移动到下一个数字
                current_length += 1   # 序列长度加 1
        
            # 更新最长序列长度
            longest = max(longest, current_length)
  
    return longest

算法过程可视化：下面的动画展示了算法如何识别序列起点并向右扩展计数的完整过程：

为什么这是 ？

误解："内层 while 循环使其成为 ！"

实际情况：每个数字最多被访问两次：

1. 一次在外层循环中
2. 一次作为序列的一部分（内层循环）

证明：内层 while 只在 num - 1 不在集合中时运行。所以每个序列 恰好被扫描一次（从 开始）。

总操作数：（外层）+ （所有序列的内层）=

复杂度分析

• 时间复杂度：（见上述证明）
• 空间复杂度：（哈希集合）

深入解读

算法原理：为什么只从起点计数？

关键洞察：如果我们从每个数字开始计数，会重复计算同一个序列。例如，对于序列 [1, 2, 3, 4]： - 如果从 1 开始：计数 1, 2, 3, 4 → 长度 4 - 如果从 2 开始：计数 2, 3, 4 → 长度 3（重复计算） - 如果从 3 开始：计数 3, 4 → 长度 2（重复计算） - 如果从 4 开始：计数 4 → 长度 1（重复计算）

通过只从起点（num-1 不在集合中）开始计数，每个序列只被计算一次。

时间复杂度证明：为什么是 O(n)？

误解："内层 while 循环使算法变成 "

实际情况：每个数字最多被访问两次： 1. 一次在外层循环：作为 num 被检查是否是起点 2. 一次在内层循环：作为某个序列的一部分被计数

证明： - 外层循环遍历所有 $ nO(n)$ - 内层 while 只在 num-1 不在集合中时运行 - 每个序列 恰好被扫描一次（从 开始） - 所有序列的总长度不超过 $ nO(n)$ 总复杂度：✅

空间优化：有没有更省空间的方法？

方法一：使用数组作为哈希表（仅适用于小范围） 如果数字范围已知且较小（如 [0, 1000]），可以使用布尔数组：

# 仅适用于数字范围较小的情况
max_num = max(nums)
min_num = min(nums)
present = [False] * (max_num - min_num + 1)
# 空间： O(范围大小)，可能比 O(n) 大或小

方法二：原地标记（需要修改输入数组） 如果允许修改输入数组，可以使用符号标记：

# 将已访问的数字标记为负数（需要额外处理）
# 空间： O(1) 额外空间，但破坏输入

权衡：对于一般情况，哈希集合的 空间是最优的，因为： - 数字范围可能很大（到 ） - 不能修改输入数组 - 需要快速查询（）

常见错误分析

错误类型	错误代码	问题	正确做法
从每个数字计数	for num in nums: while num+1 in set	重复计算，	只从起点计数
使用列表而非集合	num_list = list(nums)	查找是	使用 set()
忘记去重	直接遍历 nums	重复元素导致重复计算	遍历 set(nums)

变体扩展

1. 最长连续递增序列（要求在原数组中连续）：使用动态规划
2. 最长连续序列（允许重复）：需要统计频率
3. 最长连续序列（二维）：扩展到二维数组

示例逐步解析

输入：nums = [100, 4, 200, 1, 3, 2]

步骤 1：构建集合 {100, 4, 200, 1, 3, 2}

步骤 2：遍历集合

num	num-1 在集合中？	操作	current_length
100	否（ 99 不在集合中）	开始序列	计数 100 → 长度 1
4	是（ 3 在集合中）	跳过	-
200	否（ 199 不在集合中）	开始序列	计数 200 → 长度 1
1	否（ 0 不在集合中）	开始序列	计数 1,2,3,4 → 长度 4
3	是（ 2 在集合中）	跳过	-
2	是（ 1 在集合中）	跳过	-

输出：4

常见边界情况

边界情况一：空数组

nums = []
# 输出： 0

边界情况二：全部重复

nums = [1, 1, 1, 1]
# 集合变为 {1}，输出： 1

边界情况三：无连续数字

nums = [1, 3, 5, 7, 9]
# 每个数字都是自己的序列，输出： 1

边界情况四：整个数组连续

nums = [5, 1, 3, 4, 2]
# 序列 [1,2,3,4,5]，输出： 5

边界情况五：负数

nums = [-1, -2, 0, 1, 2]
# 序列 [-2,-1,0,1,2]，输出： 5

实际应用

• 版本控制：查找连续提交的最长序列
• 游戏：检测最长连胜记录
• 时间序列：查找没有缺失数据的最长时期

---

LeetCode 49: 字母异位词分组

问题分析

核心难点：如何设计一个哈希键，使得所有字母异位词映射到同一个键，而非字母异位词映射到不同的键。字母异位词的特点是字符相同但顺序不同，因此需要一个规范形式（ canonical form）来统一表示。

解题思路：有三种主要方法设计哈希键： 1. 排序字符串：将字符串排序后作为键（"eat" → "aet"） 2. 字符计数元组：统计每个字符的频率，转换为元组作为键 3. 固定大小数组：对于小写英文字母（ 26 个），使用长度为 26 的计数数组

复杂度分析： - 方法一（排序）：时间，空间 - 方法二（计数+排序）：时间，空间 - 方法三（固定数组）：时间，空间（最快）

关键洞察：选择哈希键是这类分组问题的核心。排序方法简单通用，但字符计数方法更快，因为计数是 而排序是 。

问题描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例：

• 输入：strs = ["eat","tea","tan","ate","nat","bat"]
• 输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

约束条件：

• strs[i] 由小写英文字母组成

关键洞察：什么是好的哈希键？

字母异位词具有相同的字符但顺序不同。需要一个规范形式，对所有字母异位词都相同。

方法一：排序字符串作为键

from collections import defaultdict

def groupAnagrams(strs):
    # 使用 defaultdict 避免手动初始化空列表
    groups = defaultdict(list)
    
    # 遍历每个字符串
    for s in strs:
        # 将字符串排序后作为哈希键
        # 字母异位词排序后得到相同的字符串
        # 例如："eat" → "aet", "tea" → "aet", "ate" → "aet"
        key = ''.join(sorted(s))  # 规范形式
        
        # 将当前字符串添加到对应分组
        groups[key].append(s)
    
    # 返回所有分组（列表的列表）
    return list(groups.values())

示例：

• "eat" → 排序 → "aet"
• "tea" → 排序 → "aet"
• "ate" → 排序 → "aet"

全部映射到同一个键！

复杂度：

• 时间复杂度：，其中 $ n = k = $
• 空间复杂度：

方法二：字符计数作为键（更快！）

不排序，而是统计字符频率：

from collections import defaultdict, Counter

def groupAnagrams_optimized(strs):
    groups = defaultdict(list)
    for s in strs:
        # 统计字符：{'e':1, 'a':1, 't':1}
        count = Counter(s)
        # 转换为元组（可哈希）：(('a',1), ('e',1), ('t',1))
        key = tuple(sorted(count.items()))
        groups[key].append(s)
    return list(groups.values())

复杂度：

• 时间复杂度：（计数是 ，排序 26 个字母是 ）
• 空间复杂度： 为什么更快：计数 个字符是 ，但排序是 。

方法三：固定大小数组作为键（小写英文字母最佳）

对于小写英文字母（共 26 个），使用固定大小的计数数组：

def groupAnagrams_fastest(strs):
    groups = defaultdict(list)
    
    for s in strs:
        # 创建长度为 26 的计数数组
        # 索引 0 对应 'a'，索引 25 对应 'z'
        count = [0] * 26
        
        # 统计字符串中每个字符的出现次数
        for c in s:
            # ord(c) - ord('a') 将字符转换为 0-25 的索引
            # 例如：'a' → 0, 'b' → 1, 'z' → 25
            count[ord(c) - ord('a')] += 1
        
        # 将列表转换为元组作为哈希键（列表不可哈希）
        # 字母异位词会有相同的计数数组
        key = tuple(count)
        
        # 将字符串添加到对应分组
        groups[key].append(s)
    
    return list(groups.values())

复杂度：

• 时间复杂度：
• 空间复杂度： 为什么最快：完全不需要排序，只需遍历每个字符串一次。

深入解读

算法原理：为什么这些方法能 work？

核心思想：字母异位词的本质是字符频率相同但顺序不同。因此，需要一个不依赖于顺序的表示作为哈希键。

方法一（排序）： - 排序后，所有字母异位词变成相同的字符串 - "eat", "tea", "ate" 都排序为 "aet" - 时间复杂度：排序每个字符串需要 方法二（字符计数）： - 统计每个字符的频率，字母异位词有相同的频率分布 - "eat" → {'e':1, 'a':1, 't':1} → (('a',1), ('e',1), ('t',1)) - 时间复杂度：计数是 ，排序 26 个字母是 （常数）

方法三（固定数组）： - 使用固定大小的数组，索引对应字符位置 - "eat" → [1,0,0,...,1,0,1]（ a=1, e=1, t=1） - 时间复杂度：只需一次遍历，

时间复杂度证明：为什么方法三最快？

方法一： - 对每个字符串排序： - $ nO(n k k)$ 方法二： - 计数： - 排序计数项（最多 26 个）： - $ nO(n k)$ 方法三： - 计数：（一次遍历） - 无排序： - $ nO(n k)$ 结论：方法三最快，因为避免了排序开销。

空间优化：有没有更省空间的方法？

优化一：使用字符串作为键（方法一） - 空间：（存储排序后的字符串） - 优点：键可读性好，便于调试

优化二：使用元组作为键（方法二、三） - 空间：（存储元组） - 优点：更紧凑，但可读性差

权衡：对于小写英文字母，方法三最优： - 固定 26 个整数，空间开销小 - 无需排序，时间最快 - 代码简洁

常见错误分析

错误类型	错误代码	问题	正确做法
使用列表作为键	groups[count].append(s)	列表不可哈希	使用 tuple(count)
忘记排序计数项	key = tuple(count.items())	顺序可能不同	tuple(sorted(count.items()))
索引计算错误	count[ord(c)]	索引超出范围	count[ord(c) - ord('a')]

变体扩展

1. 字母异位词检测：判断两个字符串是否是字母异位词

   # 方法：比较排序后的字符串或字符计数
   return sorted(s1) == sorted(s2)

2. 找到所有字母异位词：在字符串中查找模式的所有字母异位词

   • 使用滑动窗口 + 字符计数
   • 时间复杂度：3. 字母异位词分组（大小写敏感）：
   • 需要区分大小写，扩展字符集到 52 个

复杂度对比

方法	时间复杂度	空间复杂度	备注
排序字符串			简单，通用
Counter + 排序			更快，适用于任何字符集
固定数组			最快，仅限小写英文字母

示例逐步解析

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

使用排序字符串键：

字符串	排序键	分组
"eat"	"aet"	组 A
"tea"	"aet"	组 A
"tan"	"ant"	组 B
"ate"	"aet"	组 A
"nat"	"ant"	组 B
"bat"	"abt"	组 C

输出：[["eat","tea","ate"], ["tan","nat"], ["bat"]]

边界情况

边界情况一：空字符串

strs = [""]
# 输出：[[""]]

边界情况二：单字符

strs = ["a"]
# 输出：[["a"]]

边界情况三：无字母异位词

strs = ["abc", "def", "ghi"]
# 输出：[["abc"], ["def"], ["ghi"]]

边界情况四：全部是字母异位词

strs = ["abc", "bca", "cab"]
# 输出：[["abc", "bca", "cab"]]

实际应用

• 拼写检查：按字母组成对拼写错误分组
• 基因组学：聚类具有相同核苷酸计数的 DNA 序列
• 数据去重：查找具有相同属性（顺序不同）的记录

---

高级哈希表模式

模式一：互补搜索（两数之和变体）

使用时机：需要找到满足条件的数对

示例：

• 三数之和（扩展到三元组）
• 四数之和
• 统计具有给定差值的数对

模式二：频率统计

使用时机：需要跟踪出现次数

示例：

• 前 K 个高频元素
• 第一个唯一字符
• 有效的字母异位词（比排序更简单）

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

模式三：滑动窗口 + 哈希映射

使用时机：固定大小窗口的跟踪

示例：最多包含 K 个不同字符的最长子串

def lengthOfLongestSubstringKDistinct(s, k):
    from collections import defaultdict
    left = 0
    char_count = defaultdict(int)
    max_len = 0
  
    for right in range(len(s)):
        char_count[s[right]] += 1
    
        # 如果不同字符太多，缩小窗口
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
    
        max_len = max(max_len, right - left + 1)
  
    return max_len

模式四：前缀和与哈希映射

使用时机：需要子数组和

示例：和为 K 的子数组

def subarraySum(nums, k):
    from collections import defaultdict
    prefix_sum = 0
    count = 0
    sum_count = defaultdict(int)
    sum_count[0] = 1  # 基本情况
  
    for num in nums:
        prefix_sum += num
        # 检查是否存在 (prefix_sum - k)
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]
        sum_count[prefix_sum] += 1
  
    return count

---

哈希表内部机制（进阶知识）

Python dict 的工作原理

底层实现：

1. 哈希函数：将键转换为整数 hash(key)
2. 桶选择：index = hash(key) % table_size
3. 碰撞处理： Python 使用开放寻址和探测

负载因子：当 num_entries / table_size > 2/3 时， Python 调整大小（加倍大小）。

碰撞解决

开放寻址（ Python）

当桶被占用时，探测下一个槽位：

• 线性探测：尝试 index+1, index+2, ...
• 二次探测：尝试 index+1^2, index+2^2, ...

链式法（ Java HashMap）

每个桶存储一个链表（如果太长则使用树）来存储碰撞的条目。

哈希函数质量

好的哈希函数：

• 确定性（相同键 → 相同哈希）
• 均匀分布（避免聚集）
• 计算快速

Python 的 hash()：

• 整数：hash(x) = x（对于小的 ）
• 字符串：使用 SipHash（密码学质量）
• 自定义对象：重写 __hash__ 和 __eq__

---

常见错误与调试清单

错误一：插入前忘记检查

错误：

seen[num] = i
if target - num in seen:
    return [seen[target - num], i]

正确：在插入之前检查（避免自配对）

if target - num in seen:
    return [seen[target - num], i]
seen[num] = i

错误二：使用不可哈希的键

错误：

key = [1, 2, 3]  # 列表不可哈希！
groups[key].append(value)  # TypeError

修复：转换为元组

key = tuple([1, 2, 3])

错误三：修改哈希键

危险：

key = [1, 2]
groups[tuple(key)] = "value"
key.append(3)  # 哈希后不要修改！

规则：将哈希键视为不可变。

错误四：索引计算中的差一错误

仔细检查：

• 返回的是 [i, j] 还是 [j, i]？
• 题目要求的是 0 索引还是 1 索引输出？

调试清单

✅ 编码前：

1. 键应该是什么？（值、计数、排序形式？）
2. 值应该是什么？（索引、列表、计数？）
3. 需要 dict 还是 set？

✅ 编码后：

1. 测试空输入
2. 测试单个元素
3. 测试重复值
4. 测试全部唯一元素
5. 打印每一步的哈希表内容（对于小输入）

---

面试技巧

技巧一：表达你的思考过程

模板：

"我注意到我们在寻找数对/分组/匹配，这提示使用哈希表。我将存储 [X] 作为键，[Y] 作为值。查找将是 [Z]。"

技巧二：从暴力解法开始

即使你知道哈希表解法，也要说：

"暴力解法是 ，使用嵌套循环。可以使用哈希映射优化到 。"

技巧三：澄清约束条件

询问：

• 数组可以有重复值吗？
• 数组是否已排序？
• 预期大小是多少？（影响空间复杂度考虑）
• 有负数吗？

技巧四：分析权衡

在你的解法之后，提及：

"这用 空间换取 时间。如果内存紧张，可以回退到 的排序方法。"

技巧五：大声处理边界情况

逐步说明：

• 空数组
• 单个元素
• 全部重复
• 全部唯一

---

时间节省技巧

技巧一：使用 collections.Counter

而不是：

freq = {}
for x in nums:
    freq[x] = freq.get(x, 0) + 1

写：

from collections import Counter
freq = Counter(nums)

技巧二：使用 collections.defaultdict

而不是：

groups = {}
for item in items:
    if key not in groups:
        groups[key] = []
    groups[key].append(item)

写：

from collections import defaultdict
groups = defaultdict(list)
for item in items:
    groups[key].append(item)

技巧三：使用 enumerate 获取索引+值

而不是：

for i in range(len(nums)):
    num = nums[i]

写：

for i, num in enumerate(nums):

---

性能对比：哈希表 vs 替代方案

问题	暴力解法	排序	哈希表	胜者
两数之和				哈希表
最长连续序列				哈希表
字母异位词分组				哈希表
查找重复				哈希表

排序胜出的情况：

• 需要排序输出
• 空间极度受限（需要 ）
• 数据已经部分排序

---

练习题目（ 10 道推荐）

简单

1. 存在重复元素（ LeetCode 217）
2. 有效的字母异位词（ LeetCode 242）
3. 两个数组的交集（ LeetCode 349）

中等

4. 字母异位词分组（ LeetCode 49）← 本文已覆盖
5. 前 K 个高频元素（ LeetCode 347）
6. 和为 K 的子数组（ LeetCode 560）
7. 无重复字符的最长子串（ LeetCode 3）

困难

8. 最长连续序列（ LeetCode 128）← 本文已覆盖
9. 串联所有单词的子串（ LeetCode 30）
10. 缺失的第一个正数（ LeetCode 41）← 技巧：使用数组作为哈希表！

---

总结：一页纸掌握哈希表

何时使用：

• 需要快速查找（平均 ）
• 寻找数对/互补数
• 按键分组
• 频率统计
• 检查成员关系

常见模式：

1. 互补搜索：存储已见值，检查 target - current
2. 规范形式：按排序/规范化键分组
3. 频率映射：使用 Counter 或 defaultdict(int) 统计出现次数
4. 滑动窗口：在固定大小窗口中跟踪状态

要避免的陷阱：

• 插入前检查（避免自配对）
• 使用不可变键（元组，不是列表）
• 正确处理重复值
• 不要忘记边界情况（空、单个元素）

面试模板：

1. 识别快速查找的需求
2. 决定键和值的类型
3. 用示例逐步说明
4. 使用 dict/set 编码
5. 分析复杂度
6. 测试边界情况

记忆口诀：

哈希表用空间换时间：内存换取 查找。完美适用于"查找数对/分组/匹配"问题。

---

下一步是什么？

在第二部分（双指针技巧）中，我们将探索：

• 对撞指针：从两端挤压（盛最多水的容器）
• 快慢指针：检测环（ Floyd 算法）
• 滑动窗口：动态窗口大小调整（最长子串）
• 何时使用哈希表 vs 双指针

预览问题：如何在不使用 空间的情况下解决三数之和？第二部分见！

---

❓ Q&A：哈希表常见问题

Q1：什么时候应该使用哈希表而不是数组进行查找？

答案：当需要非顺序键访问或键是稀疏的（不是从 0 开始的连续整数）时，使用哈希表。

数组优势：

• 直接索引：arr[i] 保证
• 更好的缓存局部性（连续内存）
• 更低的内存开销（无哈希函数，无碰撞处理）
• 可预测的性能（无最坏情况退化）

哈希表优势：

• 灵活的键（字符串、元组、自定义对象）
• 稀疏键不浪费内存
• 动态调整大小无需重新索引

对比表：

场景	数组	哈希表	胜者
连续整数键 [0..n-1]	直接访问	平均	数组（更简单，更快）
稀疏整数键 [1, 100, 1000]	但浪费内存	平均	哈希表（空间高效）
字符串键	不可能	平均	哈希表（唯一选择）
固定大小，已知范围	保证	平均	数组（可预测）
未知/动态键	不实用	平均	哈希表（灵活）

示例：

# 数组：完美适用于连续索引
scores = [85, 90, 78, 92]  # 学生 0, 1, 2, 3
print(scores[2])  # O(1)，直接访问

# 哈希表：完美适用于稀疏/非整数键
student_scores = {"Alice": 85, "Bob": 90, "Charlie": 78}
print(student_scores["Bob"])  # O(1) 平均，灵活键

面试提示：如果问题提到"索引"或"位置"，首先考虑数组。如果提到"值"或"标识符"，哈希表可能更好。

---

Q2：不同的碰撞处理策略有哪些，什么时候应该使用每种？

答案：主要有两种方法：链式法和开放寻址。每种都有权衡。

链式法（ Separate Chaining）：

• 每个桶存储一个链表（或树，如果太长）来存储碰撞的条目
• 使用于： Java HashMap、 C++ std::unordered_map（默认）
• 优点：简单，能很好地处理高负载因子，无聚集
• 缺点：指针的额外内存，链表的缓存未命中

# 概念表示
buckets = [
    [("key1", value1), ("key2", value2)],  # 桶 0：碰撞链
    [("key3", value3)],                    # 桶 1：单个条目
    [],                                     # 桶 2：空
]

开放寻址：

• 当发生碰撞时，探测下一个可用槽位
• 使用于： Python dict、 Go map
• 探测方法：
  • 线性探测：(hash(key) + i) % size，其中 - 二次探测：(hash(key) + i^2) % size
  • 双重哈希：(hash1(key) + i * hash2(key)) % size
• 优点：更好的缓存局部性，无额外指针
• 缺点：高负载因子时性能退化，聚集问题

对比：

方面	链式法	开放寻址
负载因子容忍度	高（ 0.8-1.0）	较低（ 0.5-0.7）
内存开销	更高（指针）	更低（无指针）
缓存性能	更差（分散）	更好（连续）
删除复杂度	简单	复杂（墓碑）
最坏情况保证	每次操作	每次操作

何时使用：

• 链式法：预期高负载因子，许多删除操作，简单实现
• 开放寻址：内存受限，缓存性能关键，很少删除

面试注意：你很少自己实现碰撞处理。理解权衡有助于解释为什么哈希表性能可能退化以及何时考虑替代方案。

---

Q3：在 Python 中什么时候应该使用 dict vs set？

答案：当需要键值对时使用 dict，当只需要成员测试时使用 set。

dict（字典）：

• 存储键值映射：{key: value}
• 用例：统计频率、存储元数据、映射关系

# 统计频率
freq = {}
for num in [1, 2, 2, 3, 3, 3]:
    freq[num] = freq.get(num, 0) + 1
# 结果：{1: 1, 2: 2, 3: 3}

# 存储索引
index_map = {}
for i, val in enumerate([10, 20, 30]):
    index_map[val] = i
# 结果：{10: 0, 20: 1, 30: 2}

set（哈希集合）：

• 仅存储唯一键：{key1, key2, key3}
• 用例：去重、成员测试、集合操作

# 去重
unique_nums = set([1, 2, 2, 3, 3, 3])
# 结果：{1, 2, 3}

# 快速成员测试
seen = set()
for num in nums:
    if num in seen:  # O(1) 平均
        print("重复！")
    seen.add(num)

# 集合操作
set1 = {1, 2, 3}
set2 = {2, 3, 4}
intersection = set1 & set2  # {2, 3}
union = set1 | set2         # {1, 2, 3, 4}

决策树：

需要存储带键的值吗？
├─ 是 → 使用 dict
│  └─ 示例：频率统计、索引映射、缓存
│
└─ 否 → 使用 set
   └─ 示例：去重、成员测试、集合操作

性能对比：

操作	dict	set	备注
插入			相似性能
查找			相似性能
内存	更高（存储值）	更低（仅键）	set 节省约 30-40% 内存
用例	键值映射	成员测试	不同目的

常见错误：当只需要 set 时使用 dict：

# ❌ 低效：存储虚拟值
seen = {}
for num in nums:
    if num not in seen:
        seen[num] = True  # 浪费！

# ✅ 高效：使用 set
seen = set()
for num in nums:
    if num not in seen:
        seen.add(num)

---

Q4：什么是好的哈希函数，常见的陷阱是什么？

答案：好的哈希函数应该是确定性的、均匀的和快速的。差的哈希函数会导致碰撞并降低性能。

好的哈希函数的属性：

1. 确定性：相同输入 → 相同输出（总是）
2. 均匀分布：键应该均匀映射到各个桶
3. 快速计算：应该是 或 ，其中 是键大小
4. 雪崩效应：小的输入变化 → 大的哈希变化

示例：字符串哈希：

# ❌ 差：简单求和（许多碰撞）
def bad_hash(s):
    return sum(ord(c) for c in s) % 1000
# 问题："abc" 和 "cba" 哈希到相同值！

# ✅ 好：多项式滚动哈希
def good_hash(s):
    hash_val = 0
    prime = 31
    for c in s:
        hash_val = (hash_val * prime + ord(c)) % (2**31)
    return hash_val
# 更好的分布，更少的碰撞

常见陷阱：

陷阱一：非均匀分布

# ❌ 差：所有键哈希到同一桶
def terrible_hash(key):
    return 0  # 所有都碰撞！

# ✅ 好：使用内置 hash() 或适当算法
hash_val = hash(key)

陷阱二：忽略键特征

# 对于整数：恒等哈希很好
hash(42) == 42  # 工作良好

# 对于字符串：需要考虑所有字符
# Python 的 hash() 使用 SipHash（密码学质量）

陷阱三：哈希函数太慢

# ❌ 差：每次哈希都进行昂贵计算
def slow_hash(s):
    import hashlib
    return int(hashlib.sha256(s.encode()).hexdigest(), 16)
# 对于频繁查找太慢！

# ✅ 好：快速多项式哈希
def fast_hash(s):
    h = 0
    for c in s:
        h = h * 31 + ord(c)
    return h

哈希函数质量指标：

指标	好	差
碰撞率	低（随机键 < 5%）	高（> 20%）
分布	均匀分布到各桶	聚集
速度	，其中 $ kO(k)$
雪崩	小输入变化 → 大哈希变化	小变化 → 小哈希变化

面试提示：你很少实现哈希函数。 Python 的 hash() 处理大多数情况。对于自定义对象，重写 __hash__() 和 __eq__()：

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
  
    def __hash__(self):
        return hash((self.x, self.y))  # 使用元组哈希
  
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

# 现在 Point 可以用作 dict 键
points = {Point(1, 2): "A", Point(3, 4): "B"}

---

Q5：哈希表相比数组的内存开销是什么？

答案：哈希表由于以下原因具有显著的内存开销：

1. 哈希表结构（桶、元数据）
2. 碰撞处理（链式指针或额外槽位）
3. 负载因子（通常 50-70% 满以维持性能）
4. 哈希函数存储（某些实现）

内存分解：

数组：

• 仅存储数据：
• 示例：[1, 2, 3, 4, 5] → 5 个整数 = 20 字节（假设 4 字节整数）

哈希表（ Python dict）：

• 每个条目开销：约 24-48 字节（键、值、哈希、指针）
• 负载因子：约 50-66%（表是条目的 1.5-2 倍大）
• 示例：{1: "a", 2: "b", 3: "c"} → 约 200-300 字节（ vs 数组的 12 字节）

对比表：

数据结构	个整数的内存	开销因子
数组	字节	1x（基准）
哈希集合	约到 字节	6-12x
哈希映射	约到 字节	8-16x

示例计算：

import sys

# 数组：最小开销
arr = [i for i in range(1000)]
print(sys.getsizeof(arr))  # ~8040 字节（ 1000 个整数 + 小开销）

# 集合：显著开销
s = set(range(1000))
print(sys.getsizeof(s))    # ~32968 字节（约 4 倍多！）

# 字典：甚至更多开销
d = {i: i for i in range(1000)}
print(sys.getsizeof(d))    # ~36968 字节（约 4.5 倍多！）

内存重要时：

使用数组当：

• 键是连续整数 [0..n-1]
• 内存极度受限
• 需要可预测的内存使用

使用哈希表当：

• 键是稀疏的或非整数
• 内存开销可接受
• 快速查找关键

空间优化技术：

1. 尽可能使用 set 而不是 dict：

# ❌ 浪费
seen = {num: True for num in nums}

# ✅ 高效
seen = set(nums)

2. 如果已知大小，预分配：

# Python dict 自动调整大小，但可以提示
d = dict.fromkeys(range(1000))  # 预分配大小

3. 对于密集整数键，考虑基于数组的解决方案：

# 对于键 [0..999]，数组更好
arr = [0] * 1000  # 4000 字节
d = {i: 0 for i in range(1000)}  # ~37000 字节

面试提示：总是提及时空权衡。哈希表用内存换取速度。如果内存受限，考虑使用排序数组 + 二分查找（查找）或其他替代方案。

---

Q6： Python 中 OrderedDict 和普通 dict 的区别是什么？

答案：OrderedDict（ Python 3.7+）维护插入顺序，而较旧的 dict 实现不保证顺序。在 Python 3.7+ 中，普通 dict 也维护插入顺序，但 OrderedDict 提供额外功能。

历史背景：

• Python < 3.7：dict 具有任意顺序（实现细节）
• Python 3.7+：dict 维护插入顺序（语言保证）
• OrderedDict：即使在较旧的 Python 版本中也始终维护顺序

当前行为（ Python 3.7+）：

# 普通 dict：维护插入顺序
d = {}
d['first'] = 1
d['second'] = 2
d['third'] = 3
print(list(d.keys()))  # ['first', 'second', 'third']

# OrderedDict：也维护插入顺序
from collections import OrderedDict
od = OrderedDict()
od['first'] = 1
od['second'] = 2
od['third'] = 3
print(list(od.keys()))  # ['first', 'second', 'third']

何时使用 OrderedDict：

当需要时使用 OrderedDict：

1. 重新排序操作：

from collections import OrderedDict

od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# 移到末尾
od.move_to_end('a')
print(list(od.keys()))  # ['b', 'c', 'a']

# 移到开头
od.move_to_end('a', last=False)
print(list(od.keys()))  # ['a', 'b', 'c']

2. 从特定端弹出：

# 弹出最后一项（ LIFO）
last = od.popitem(last=True)  # ('c', 3)

# 弹出第一项（ FIFO）
first = od.popitem(last=False)  # ('a', 1)

3. 基于顺序的相等性：

# OrderedDict 在相等性中考虑顺序
od1 = OrderedDict([('a', 1), ('b', 2)])
od2 = OrderedDict([('b', 2), ('a', 1)])
print(od1 == od2)  # False（不同顺序）

# 普通 dict 不关心顺序（ Python 3.7+）
d1 = {'a': 1, 'b': 2}
d2 = {'b': 2, 'a': 1}
print(d1 == d2)  # True（相同项）

性能对比：

操作	dict	OrderedDict	备注
插入			相似
查找			相似
内存	更低	更高（约多 20%）	OrderedDict 存储额外指针
重新排序	不支持		move_to_end() 仅在 OrderedDict 中

常见用例：

1. LRU 缓存（最近最少使用）：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
  
    def get(self, key):
        if key not in self.cache:
            return -1
        # 移到末尾（最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]
  
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 删除最近最少使用（第一项）
            self.cache.popitem(last=False)

2. 维护插入顺序（虽然 dict 现在也这样做）：

# 两者都有效，但 OrderedDict 更明确
def process_items(items):
    result = OrderedDict()  # 明确意图：顺序重要
    for item in items:
        result[item.id] = item.process()
    return result

面试提示：在 Python 3.7+ 中，普通 dict 通常足够。仅在需要 move_to_end() 或 popitem(last=False) 时使用 OrderedDict，或需要支持保证顺序的较旧 Python 版本时使用。

---

Q7：哈希表在多线程环境中的行为如何？

答案：大多数哈希表实现默认不是线程安全的。并发修改可能导致数据损坏、无限循环或崩溃。使用同步原语或线程安全的替代方案。

问题：

竞态条件示例：

import threading

# 共享哈希表
counter = {}

def increment(key):
    if key not in counter:
        counter[key] = 0
    counter[key] += 1  # 不是原子的！

# 多个线程同时修改
threads = []
for i in range(10):
    t = threading.Thread(target=increment, args=('count',))
    threads.append(t)
    t.start()

for t in threads:
    t.join()

print(counter['count'])  # 可能不是 10！可能是 5, 7 等

可能出错的情况：

1. 丢失更新：两个线程读取，都递增，都写入 → 一个更新丢失
2. 不一致状态：并发访问期间哈希表调整大小 → 损坏
3. 无限循环：迭代时另一个线程修改 → 未定义行为

解决方案：

选项一：锁（同步）：

import threading

counter = {}
lock = threading.Lock()

def increment(key):
    with lock:  # 获取锁
        if key not in counter:
            counter[key] = 0
        counter[key] += 1
    # 自动释放锁

选项二：线程安全数据结构：

Python：使用 collections.Queue 或外部库：

# 对于简单情况，使用队列
from queue import Queue
q = Queue()  # 线程安全

# 对于类似 dict 的结构，使用线程安全包装器
from threading import Lock

class ThreadSafeDict:
    def __init__(self):
        self._dict = {}
        self._lock = Lock()
  
    def __getitem__(self, key):
        with self._lock:
            return self._dict[key]
  
    def __setitem__(self, key, value):
        with self._lock:
            self._dict[key] = value

Java：使用 ConcurrentHashMap：

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// 线程安全操作
map.put("key", 1);
map.get("key");

C++：使用 std::shared_mutex 或外部库：

#include <shared_mutex>
#include <unordered_map>

std::unordered_map<std::string, int> map;
std::shared_mutex mtx;

// 读锁（允许多个读者）
{
    std::shared_lock<std::shared_mutex> lock(mtx);
    int value = map["key"];
}

// 写锁（独占）
{
    std::unique_lock<std::shared_mutex> lock(mtx);
    map["key"] = value;
}

性能权衡：

方法	线程安全	性能	复杂度
无同步	❌ 不安全	⚡ 最快	✅ 简单
粗粒度锁	✅ 安全	🐌 慢（串行化）	✅ 简单
细粒度锁	✅ 安全	⚡ 更快（并行读取）	❌ 复杂
无锁结构	✅ 安全	⚡⚡ 最快	❌❌ 非常复杂

最佳实践：

1. 尽可能避免共享可变状态：

# ✅ 好：每个线程有自己的 dict
def process_chunk(chunk):
    local_dict = {}  # 线程本地
    for item in chunk:
        local_dict[item] = process(item)
    return local_dict

# ❌ 差：共享 dict
shared_dict = {}
def process_chunk(chunk):
    for item in chunk:
        shared_dict[item] = process(item)  # 竞态条件！

2. 使用不可变数据结构：

# 不修改共享 dict，而是返回新 dict
def merge_results(results):
    # 合并线程结果（无并发修改）
    final = {}
    for result in results:
        final.update(result)
    return final

3. 只读访问通常是安全的（但验证实现）：

# 多个线程读取通常是安全的
def lookup(key):
    return shared_dict.get(key)  # 只读，通常安全

面试提示：提及哈希表默认不是线程安全的。如果被问及并发访问，讨论锁、线程安全替代方案或架构解决方案（避免共享状态）。

---

Q8：解决哈希表问题后常见的面试后续问题有哪些？

答案：面试官经常深入探讨你的理解。以下是常见的后续问题和处理方法：

后续问题一："你能优化空间复杂度吗？"

示例：用 空间解决两数之和后：

# 原始： O(n) 空间
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

优化：如果数组已排序，使用双指针（空间）：

# 优化： O(1) 空间（但需要排序数组）
def twoSum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1

后续问题二："如果需要返回所有数对，而不是只有一个呢？"

示例：返回所有和为目标值的数对：

def twoSum_all_pairs(nums, target):
    seen = {}
    result = []
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            # 添加所有之前的索引
            for prev_idx in seen[complement]:
                result.append([prev_idx, i])
        # 存储当前索引
        if num not in seen:
            seen[num] = []
        seen[num].append(i)
    return result

后续问题三："如果数组可以有重复值怎么办？"

答案：哈希表解法正确处理重复值（如两数之和问题所示）。解释你在插入之前检查以避免自配对。

后续问题四："如何处理无法放入内存的非常大的数据集？"

答案：使用外部哈希或流式算法：

# 流式方法：分块处理
def twoSum_streaming(stream, target):
    seen = {}
    chunk_size = 10000
  
    for chunk in read_in_chunks(stream, chunk_size):
        for i, num in enumerate(chunk):
            complement = target - num
            if complement in seen:
                return [seen[complement], current_index]
            seen[num] = current_index
            current_index += 1
        # 可选：如果内存受限，驱逐旧条目

后续问题五："最坏情况时间复杂度是什么？"

答案：哈希表操作是 平均情况，但由于以下原因，最坏情况是 ：

• 所有键哈希到同一桶（恶意输入）
• 哈希表调整大小（摊销 ）

后续问题六："你能在不使用额外空间的情况下解决这个问题吗？"

答案：有时可以（如果数组已排序或有约束）：

• 排序数组：双指针（空间）
• 有约束的数组：使用数组本身作为哈希表（缺失的第一个正数模式）
• 否则：通常需要 空间来实现 时间

后续问题七："你会如何测试这个解决方案？"

答案：覆盖这些情况：

test_cases = [
    ([2, 7, 11, 15], 9, [0, 1]),           # 正常情况
    ([3, 3], 6, [0, 1]),                    # 重复
    ([3, 2, 4], 6, [1, 2]),                 # 不在开头
    ([-1, -2, -3, -4, -5], -8, [2, 4]),    # 负数
    ([1, 2], 3, [0, 1]),                    # 边界：两个元素
]

后续问题八："如果需要找到三个数之和为目标值怎么办？"

答案：扩展模式：

def threeSum(nums, target):
    nums.sort()  # O(n log n)
    result = []
  
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # 跳过重复
    
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == target:
                result.append([nums[i], nums[left], nums[right]])
                # 跳过重复
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1
  
    return result

面试策略：

1. 承认权衡："哈希表解法使用 空间换取 时间。如果空间受限..."
2. 展示替代方案："可以使用排序 + 双指针实现 空间但 时间。"
3. 询问澄清问题："我们优化时间还是空间？数组是否已排序？"

---

Q9：哈希表时间复杂度分析中的边界情况有哪些？

答案：哈希表操作是摊销 ，但有几个因素可能影响实际性能：

边界情况一：哈希碰撞（最坏情况 ）

场景：所有键哈希到同一桶：

# 恶意输入：所有键碰撞
class BadHash:
    def __hash__(self):
        return 42  # 总是相同哈希！

bad_keys = [BadHash() for _ in range(1000)]
d = {key: i for i, key in enumerate(bad_keys)}

# 查找变为 O(n) - 通过链线性搜索
value = d[bad_keys[500]]  # O(n) 最坏情况！

缓解：好的哈希函数 + 负载因子管理

边界情况二：哈希表调整大小（摊销分析）

场景：当负载因子超过阈值时，表大小加倍：

# 插入 n 个元素
d = {}
for i in range(1000000):
    d[i] = i  # 在 ~66k, ~133k, ~266k 等触发调整大小

成本分析：

• 单个插入：通常是 ，但调整大小时是
• 摊销成本：每次插入 （调整大小很少发生）

证明概要：如果表在满时加倍，次插入的总成本：

• 插入：次操作
• 调整大小：次，每次成本
• 总计：
• 摊销：... 等等，这不对！

正确分析：

• 在大小 时调整大小
• 在大小 $ kO(k)$（重新哈希所有条目）
• 总调整大小成本：
• 摊销：✅

边界情况三：迭代复杂度

场景：遍历哈希表：

d = {i: i*2 for i in range(1000)}

# 迭代： O(n) 时间， O(n) 空间用于键/项
for key in d:  # O(n)
    print(key, d[key])

复杂度：时间，空间（存储迭代状态）

边界情况四：字符串键（哈希计算成本）

场景：长字符串作为键：

# 哈希计算： O(k)，其中 k 是字符串长度
long_strings = ["a" * 10000 for _ in range(1000)]
d = {s: i for i, s in enumerate(long_strings)}

# 查找： O(1) + O(k) = O(k)，其中 k 是键长度
value = d[long_strings[500]]  # O(10000) 计算哈希！

复杂度：，其中 是键长度（如果键很大，不是 ）

边界情况五：自定义哈希函数

场景：昂贵的哈希计算：

def expensive_hash(obj):
    # 密码学哈希：慢！
    import hashlib
    return int(hashlib.sha256(str(obj).encode()).hexdigest(), 16)

class ExpensiveKey:
    def __hash__(self):
        return expensive_hash(self)

# 每次查找都计算昂贵哈希
d = {ExpensiveKey(): i for i in range(1000)}
value = d[key]  # 由于哈希计算而慢

缓解：缓存哈希值或使用更快的哈希函数

复杂度总结表：

操作	平均	最坏情况	摊销	备注
插入				最坏：所有碰撞
查找			N/A	最坏：所有碰撞
删除			N/A	最坏：所有碰撞
迭代			N/A	总是线性
调整大小	N/A		每次插入	摊销分析

面试提示：总是提及"平均情况 "并承认最坏情况 。解释最坏情况在使用好的哈希函数和适当的负载因子管理时很少发生。

---

Q10：哈希表问题的空间优化技术有哪些？

答案：几种技术可以在保持性能的同时减少内存使用：

技术一：使用数组作为哈希表（当键是密集整数时）

场景：键是已知范围内的整数 [0..n-1]：

# ❌ 浪费： O(n) 额外空间用于哈希表
def find_duplicate_dict(nums):
    seen = {}
    for num in nums:
        if num in seen:
            return num
        seen[num] = True

# ✅ 高效：使用数组作为哈希表
def find_duplicate_array(nums):
    # 数组索引充当哈希键
    seen = [False] * (len(nums) + 1)
    for num in nums:
        if seen[num]:
            return num
        seen[num] = True

空间节省：数组使用 vs 哈希表的 ，但常数因子更低（约 4 倍更少内存）

技术二：布尔标志的位操作

场景：跟踪存在/不存在（布尔值）：

# ❌ 浪费： dict 存储完整整数
seen = {}
for num in nums:
    seen[num] = True  # 存储键 + 值

# ✅ 高效：使用 set（仅键）
seen = set()
for num in nums:
    if num in seen:
        return True
    seen.add(num)

# ✅✅ 最高效：位向量（如果范围小）
def has_duplicate_bitvector(nums):
    # 假设 nums 在范围 [1..32] 内
    bits = 0
    for num in nums:
        bit = 1 << num
        if bits & bit:
            return True
        bits |= bit
    return False

空间对比：

• dict：约每条目 48 字节
• set：约每条目 24 字节
• 位向量：每条目 1 位（ 32 条目 = 4 字节！）

技术三：原地修改（使用输入数组作为哈希表）

场景：缺失的第一个正数（ LeetCode 41）：

# 问题：找到最小的缺失正整数
# 约束： O(1) 额外空间

def firstMissingPositive(nums):
    n = len(nums)
  
    # 步骤 1：将负数/零替换为 n+1
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n + 1
  
    # 步骤 2：使用数组索引作为哈希键
    # 通过使值为负来标记存在
    for i in range(n):
        num = abs(nums[i])
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])
  
    # 步骤 3：找到第一个正索引
    for i in range(n):
        if nums[i] > 0:
            return i + 1
  
    return n + 1

关键洞察：使用数组索引 [0..n-1] 表示数字 [1..n]。通过使值为负来标记存在。

技术四：单次遍历的滑动窗口

场景：无重复字符的最长子串：

# ❌ 浪费：存储所有已见字符
def lengthOfLongestSubstring_bad(s):
    max_len = 0
    for i in range(len(s)):
        seen = set()  # 每个起始位置的新集合
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_len = max(max_len, len(seen))
    return max_len

# ✅ 高效：滑动窗口，重用哈希表
def lengthOfLongestSubstring_good(s):
    char_index = {}  # 跨窗口重用
    left = 0
    max_len = 0
  
    for right in range(len(s)):
        if s[right] in char_index:
            # 将左指针移到上次出现之后
            left = max(left, char_index[s[right]] + 1)
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)
  
    return max_len

空间节省：空间重用 vs 总空间

技术五：使用数组而不是 dict 进行频率统计

场景：统计字符（有限字母表）：

# ❌ 通用但对小字母表浪费
from collections import Counter
freq = Counter(s)  # Dict 开销

# ✅ 对小写英文字母（ 26 个字母）高效
freq = [0] * 26
for c in s:
    freq[ord(c) - ord('a')] += 1

空间对比：

• Counter（ dict）：约 26 × 48 字节 = 约 1248 字节
• 数组： 26 × 4 字节 = 104 字节（约 12 倍更少！）

技术六：两次遍历而不是存储所有数据

场景：找到第一个唯一字符：

# ❌ 存储所有索引
def firstUniqChar_bad(s):
    char_indices = {}
    for i, c in enumerate(s):
        if c not in char_indices:
            char_indices[c] = []
        char_indices[c].append(i)
  
    for c, indices in char_indices.items():
        if len(indices) == 1:
            return indices[0]
    return -1

# ✅ 两次遍历：先计数，然后查找
def firstUniqChar_good(s):
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
  
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

空间节省：存储计数（整数）而不是索引列表

总结表：

技术	何时使用	空间节省	权衡
数组作为哈希	密集整数键 [0..n-1]	4-8 倍更少	需要已知范围
位向量	布尔标志，小范围	8-32 倍更少	限于小范围
原地修改	可以修改输入数组	额外空间	破坏输入
滑动窗口	子串/子数组问题	重用 vs 重新创建	更复杂的逻辑
数组 vs dict	小、固定字母表	10-20 倍更少	灵活性较低
两次遍历	可以避免存储索引	存储计数 vs 列表	额外遍历

面试提示：总是考虑是否可以使用输入数组本身作为哈希表，特别是当问题要求 额外空间时。这是 LeetCode "困难"问题中的常见模式。

---

哈希表不是魔法——它们是战略性的内存分配。掌握模式，你将解锁数十个 解决方案！