核心 · 算法第 3 课 / 共 8 课免费阅读

哈希表与集合 · 数据结构与算法

怎么做到瞬间找到，而不是一个个搜？

课程目录

为什么需要它

面试和实际代码里最有用的一招：用哈希表（Python 的 dict）或集合，拿一点内存换速度。「我见过它吗？」「每样有几个？」这类问题，从每次 O(n) 变成 O(1)。

直觉理解

哈希表根据键算出一个数（它的哈希值），用它直接跳到对应的格子，就像储物柜编号。不需要逐个扫描。

三个套路覆盖了大多数题目：

见过集合：if x in seen —— 判重、第一个重复。
计数器：counts[x] = counts.get(x, 0) + 1 —— 频率、变位词。
找补数：两数之和问「我见过 target − x 吗？」。

定义

哈希表 Hash map

A key → value store with O(1) average lookup, insert and delete. Python's dict. Keys must be hashable (str, int, tuple; not list).
键 → 值的存储结构，查找、插入、删除平均 O(1)。Python 的 dict。键必须可哈希（str、int、tuple 可以；list 不行）。

集合 Set

A hash map with only keys: fast membership tests, no duplicates, no order.
只有键的哈希表：判断是否存在很快，没有重复，没有顺序。

示例

用字典做两数之和

动手试试

无序列表，只走一遍。对每个数，查一查它需要的搭档。

def two_sum(xs, target):
    where = {}
    for i, x in enumerate(xs):
        need = target - x
        if need in where:
            return (where[need], i)
        where[x] = i
    return None

print(two_sum([8, 3, 11, 5, 2], 7))

逐步执行

L4对 8 来说，搭档应该是 -1。
L7记住每个数的下标。
L6到 2（下标 4）时，需要 5，它在下标 3 出现过。
L10下标 3 和 4：5 + 2 = 7。(3, 4)

计数并比较

动手试试

两个词字母的数量都一样，它们就是变位词。

def counts(word):
    c = {}
    for ch in word:
        c[ch] = c.get(ch, 0) + 1
    return c

print(counts("level"))
print(counts("listen") == counts("silent"))

逐步执行

L4字母第一次出现时，get 返回 0。
L7键按第一次出现的顺序排列。{'l': 2, 'e': 2, 'v': 1}
L8字典里的键值对相同就相等，与顺序无关。True

常见错误

用列表当键

{[1, 2]: 'x'} 会报 TypeError：列表可以修改，所以不能哈希。用元组：{(1, 2): 'x'}。

查不存在的键

counts['z'] 会报 KeyError。用 counts.get('z', 0)，或者先检查 'z' in counts。

小测验

1. 这段代码会输出什么？

words = ["red", "blue", "red", "green", "blue", "red"]
seen = set()
first = None
for w in words:
    if w in seen:
        first = w
        break
    seen.add(w)
print(first, len(seen))

A
```
red 2
```
B
```
blue 3
```
C
```
red 3
```

查看答案

答案：A

red、blue 被加入；第二个 red 是第一个重复。那时 seen 里有 2 个元素。

2. 在遍历 n 个元素的循环里检查 `x in my_list` 是 O(n²)。怎么让整体变成 O(n)？

A把 my_list 换成集合
B先给 my_list 排序
C改用 while 循环

查看答案

答案：A

集合判断成员平均 O(1)，n 次检查就是 O(n)。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出数选票
准确写出这段程序的输出。
改需求更快地找共同元素
common(a, b) 返回 a 里同样出现在 b 里的元素，保持 a 的顺序。x in b 每次都扫描整个列表。先把 b 变成集合，让函数变成 O(len(a) + len(b))。
从零写变位词分组
写函数 group_anagrams(words)，返回一个字典：键是每个词排序后的字母（字符串），值是由这些字母组成的词的列表，按出现顺序排列。比如 "eat" 和 "tea" 都放在 "aet" 下面。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Hash map	哈希表	A key → value store with fast lookup; Python's dict.
Hash	哈希值	A number computed from a key to find its slot quickly.