#️⃣ 哈希表 — O(1)查找的魔法

📖 哈希表的核心概念

哈希表（Hash Table）是通过哈希函数将键映射到数组下标，实现 O(1) 平均时间的查找、插入和删除。它是算法面试中最重要的数据结构之一——几乎任何"查找配对"、"统计频率"、"去重"的问题都可以用哈希表优化。理解哈希冲突的解决方式（链地址法、开放寻址法）是深入理解的关键。

1. 哈希表的面试应用模式

2. Python 哈希操作速查

# dict（哈希字典）
d = {'a': 1, 'b': 2}
d['c'] = 3          # 插入/更新
x = d.get('d', 0)   # 查找，不存在返回0
del d['a']           # 删除
'a' in d             # 判断key存在

# set（哈希集合）
s = {1, 2, 3}
s.add(4)             # 添加
s.discard(5)         # 删除（不存在不报错）
4 in s               # 判断存在
s1 & s2              # 交集
s1 | s2              # 并集

# Counter（频率统计）
from collections import Counter
c = Counter('aabccc')
# Counter({'c': 3, 'a': 2, 'b': 1})
c.most_common(2)     # Top2: [('c',3), ('a',2)]

🎯 题目一：两数之和 (LC 1)

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

思路分析

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hash_map:
                return [hash_map[complement], i]
            hash_map[num] = i
        return []

复杂度分析

时间复杂度：O(n) — 一次遍历

空间复杂度：O(n) — 哈希表

变体练习

• LC 167 两数之和 II（有序数组，双指针 O(1) 空间）
• LC 454 四数相加 II（分组哈希）

🎯 题目二：字母异位词分组 (LC 49)

题目描述：给你一个字符串数组，请你将字母异位词组合在一起。字母异位词是由相同字母重新排列形成的字符串。

思路分析

代码实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        from collections import defaultdict
        groups = defaultdict(list)
        for s in strs:
            key = tuple(sorted(s))
            groups[key].append(s)
        return list(groups.values())

复杂度分析

时间复杂度：O(n · k log k) — n 个字符串，每个排序 O(k log k)

空间复杂度：O(n · k) — 存储所有字符串

变体练习

• LC 242 有效的字母异位词（简单版，判断两个字符串是否为异位词）
• LC 49 进阶：不用排序，用计数法

🎯 题目三：两个数组的交集 (LC 349)

题目描述：给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素必须是唯一的。

思路分析

代码实现

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

复杂度分析

时间复杂度：O(n+m)

空间复杂度：O(n+m)

变体练习

• LC 350 两个数组的交集 II（保留重复，频率取最小）
• LC 202 快乐数（集合检测循环）

📝 课后练习

1. LC 242 有效的字母异位词
2. LC 202 快乐数（Floyd 或集合检测循环）
3. LC 205 同构字符串（双向映射）
4. LC 219 存在重复元素 II（滑动窗口+集合）
5. LC 454 四数相加 II（分组哈希）

🔑 本课要点回顾

• 哈希表：O(1) 平均查找，用空间换时间
• 查找配对：complement = target - num，一遍哈希
• 字母异位词分组：排序后的字符串作为 key
• 集合操作：交集 &、并集 |、差集 -
• Counter：频率统计神器，most_common() 找 TopK
• 哈希冲突：链地址法最常见，好的哈希函数减少冲突

📚 扩展阅读

• 《算法导论》第11章 哈希表
• 哈希表专题：LeetCode 哈希表标签
• Python dict 实现原理：开放寻址法

🔬 哈希表与LRU缓存

哈希表 + 双向链表是 LRU 缓存的经典实现，这是系统设计面试的高频题，也是哈希表应用的重要进阶。

LRU 缓存结合了哈希表 O(1) 查找和双向链表 O(1) 插入/删除的优势。哈希表存 key → 链表节点的映射，链表维护访问顺序。