第 7 章 字典¶
本章配套 1 道例题，见 §例题。
dict 是 Python 的哈希表，对应 C++ 的 std::unordered_map。
它是语言内置、C 实现、高度优化的——在 Python 里手写哈希表永远打不过它。
竞赛中 dict 承担三件事：
- 计数（词频、桶统计、出现次数）
- 记忆化（把递归搜索变成 DP）
- 映射 / 离散化（把稀疏的大值域压到小下标）
本章还有一个 C++ 选手必须调整的认知：Python 的 dict 保持插入顺序，
但它不是有序表——它没有 std::map 的按键有序遍历和 lower_bound。
1 创建字典¶
d = {} # 空字典（注意 {} 是字典不是集合！）
d = {"a": 1, "b": 2} # 字面量
d = dict(a=1, b=2) # 关键字参数（键只能是合法标识符）
d = dict([("a", 1), ("b", 2)]) # 从键值对序列
d = dict(zip(keys, values)) # 两个列表压成字典 —— 高频
d = dict.fromkeys("abc", 0) # {'a': 0, 'b': 0, 'c': 0}
d = {x: x * x for x in range(5)} # 字典推导式
dict.fromkeys(seq, [])是个陷阱：所有键会共享同一个列表对象， 和 列表 里的[[0]*m]*n是同一个病。 值是可变对象时请用推导式{k: [] for k in seq}，或者直接用defaultdict(list)。
键的要求¶
键必须可哈希（不可变），值随便：
d[(1, 2)] = "ok" # ✅ 元组可以
d[frozenset({1, 2})] = 1 # ✅
d[[1, 2]] = "no" # ❌ TypeError: unhashable type: 'list'
同一个字面量里键重复时，后写的覆盖先写的：
还有一个容易忽略的点：1、1.0、True 是同一个键，因为它们 == 且 hash 相同：
混用
int和str键时要小心：d[1]和d["1"]是两个不同的键。 从sys.stdin.buffer读进来的 token 是bytes，d[b"1"]又是第三个键。 类型不统一是这类 bug 的唯一来源，读进来立刻决定用什么类型做键。
2 增删改查¶
查¶
d["a"] # 取值，键不存在抛 KeyError
d.get("a") # 取值，不存在返回 None
d.get("a", 0) # 取值，不存在返回 0 ← 计数的标配
"a" in d # 判断键是否存在，O(1)
"a" not in d
in判断的是「键」，不是「值」。想判值要写x in d.values()，那是 \(O(n)\)。
d.get(k, 0) 和 d[k] 的选择：
改与增¶
d["a"] = 1 # 存在则改，不存在则增，O(1)
d.update({"b": 2}) # 批量更新
d.update(b=2, c=3)
d.update(zip(keys, vals))
# 三种合并写法，设此处 d = {"a": 1, "b": 2}。重名的键一律**右边赢**
d2 = {**d, "b": 9} # {'a': 1, 'b': 9} 新字典，d 不变（3.5+）
d3 = d | {"b": 9} # {'a': 1, 'b': 9} 同上，写法更短（3.9+）
d |= {"b": 9} # d 自己变成 {'a': 1, 'b': 9}，不产生新字典（3.9+）
删¶
del d["a"] # 键不存在抛 KeyError
v = d.pop("a") # 删并返回值，不存在抛 KeyError
v = d.pop("a", None) # 不存在时返回默认值 —— 推荐
k, v = d.popitem() # 删除并返回「最后插入」的一对（3.7+ 保证是 LIFO）
d.clear() # 清空
setdefault：查不到就先塞一个¶
它的经典用法是建邻接表 / 分组，一行完成「没有就建空列表，然后追加」：
等价的笨写法要三行：
setdefault的默认值每次调用都会求值，哪怕键已经存在。d.setdefault(k, expensive())会白算一次expensive()。 这种情况用defaultdict更好——它只在缺失时才调用工厂函数。
方法全表¶
| 方法 | 作用 | 复杂度 |
|---|---|---|
d[k] 读 / 写 / del |
基本操作 | 平均 \(O(1)\) |
k in d |
键是否存在 | 平均 \(O(1)\) |
len(d) |
键的个数 | \(O(1)\) |
★ d.get(k[, default]) |
安全取值 | \(O(1)\) |
★ d.setdefault(k[, default]) |
缺失则插入并返回 | \(O(1)\) |
★ d.pop(k[, default]) |
删并返回 | \(O(1)\) |
d.popitem() |
删并返回最后一对 | \(O(1)\) |
d.update(other) |
批量更新 | \(O(\|other\|)\) |
★ d.keys() / d.values() / d.items() |
视图对象 | \(O(1)\) 创建 |
d.copy() |
浅拷贝 | \(O(n)\) |
d.clear() |
清空 | \(O(n)\) |
dict.fromkeys(seq[, v]) |
由键序列建字典 | \(O(n)\) |
3 视图对象¶
keys() / values() / items() 返回的不是列表，而是「视图」：
d = {"a": 1, "b": 2}
ks = d.keys()
print(ks) # dict_keys(['a', 'b'])
d["c"] = 3
print(ks) # dict_keys(['a', 'b', 'c']) ← 自动跟着变了！
视图的三个特点：
- 动态：字典变了，视图跟着变。
- 不占额外内存：\(O(1)\) 创建，不复制。
- 不能索引：
d.keys()[0]报TypeError，要先list(d)。
list(d) # ['a', 'b', 'c'] 等价于 list(d.keys())，更短
list(d.values())
list(d.items()) # [('a', 1), ('b', 2), ('c', 3)]
keys() 和 items() 支持集合运算¶
因为键唯一，keys() 表现得像 set：
d1 = {"a": 1, "b": 2}
d2 = {"b": 9, "c": 3}
d1.keys() & d2.keys() # {'b'} 共同的键
d1.keys() - d2.keys() # {'a'} 只在 d1 里的键
d1.keys() | d2.keys() # {'a','b','c'}
values() 不支持（值可以重复，不构成集合）。
遍历时不能改结构¶
正确写法是先把键固化成列表：
for k in list(d): # list(d) 是一份快照
if d[k] == 0:
del d[k]
# 或者重建
d = {k: v for k, v in d.items() if v != 0}
只改值不改结构是允许的：
for k in d: d[k] += 1没问题。 出问题的是增删键（会触发 rehash）。
4 插入有序性（3.7+）¶
从 Python 3.7 起，dict 保证按插入顺序迭代（3.6 已经是实现细节，3.7 写进语言规范）。
这带来两个能力：
但必须分清「插入有序」和「按键有序」：
Python dict |
C++ std::map |
C++ std::unordered_map |
|
|---|---|---|---|
| 底层 | 哈希表 | 红黑树 | 哈希表 |
| 迭代顺序 | 插入顺序 | 键升序 | 无序 |
| 单次查找 | \(O(1)\) 平均 | \(O(\log n)\) | \(O(1)\) 平均 |
找最小键 / lower_bound |
不支持 | \(O(\log n)\) | 不支持 |
Python 没有
std::map。 需要「按键有序遍历」就自己sorted(d)（\(O(n \log n)\)）； 需要动态的lower_bound就得上树状数组 / 有序列表，见 平衡树与有序集合。另外永远不要依赖字典顺序来产生题目要求的输出顺序。 题目说「按字典序输出」就老老实实
sorted()， 说「按出现顺序输出」才可以直接迭代dict。
排序输出的三个常用写法：
for k in sorted(d): # 按键排序
...
for k, v in sorted(d.items(), key=lambda kv: -kv[1]): # 按值降序
...
for k, v in sorted(d.items(), key=lambda kv: (-kv[1], kv[0])): # 值降序 + 键升序
...
5 字典推导式¶
{k: v for k, v in pairs}
{x: x * x for x in range(5)} # {0:0, 1:1, 2:4, 3:9, 4:16}
{v: k for k, v in d.items()} # 反转键值
{k: v for k, v in d.items() if v > 0} # 过滤
{x: i for i, x in enumerate(sorted(set(a)))} # ★ 离散化：值 → 排名
最后一行是离散化的标准模板：把任意大小的值映射到 \(0 \dots m-1\)， 之后就能用数组代替字典（更快）。见 桶计数与离散化。
推导式的完整语法（多重循环、条件）见 推导式。
6 dict 作哈希表：三大用法¶
用法一：计数¶
题设统一是「统计序列 a 里每个元素出现了几次」：cnt 是结果字典，
x 是被数的那个元素，来自外层循环——两者不是同一个东西。
五种写法，从慢到快：
cnt = {}
# ① 最笨
for x in a:
if x in cnt:
cnt[x] += 1
else:
cnt[x] = 1
# ② get，一行
for x in a:
cnt[x] = cnt.get(x, 0) + 1
# ③ setdefault
for x in a:
cnt.setdefault(x, 0)
cnt[x] += 1
# ④ defaultdict
from collections import defaultdict
cnt = defaultdict(int)
for x in a:
cnt[x] += 1
# ⑤ Counter，最短——它自己就把这层循环包掉了
from collections import Counter
cnt = Counter(a)
实战选择：
- 一次性统计整个序列 →
Counter(a)，它在 C 层批量计数，最快。 - 边算边计数（键是临时算出来的） →
defaultdict(int)或cnt.get(x, 0) + 1。 - 值域小且是连续整数 → 别用字典，用列表：
cnt = [0] * 26快 3–5 倍。
值域已知且不大时，永远优先用
list而不是dict。 列表索引是一次指针偏移，字典要算哈希、探测、比较。 字母计数写cnt = [0]*26; cnt[ord(c)-97] += 1，别写Counter(s)。
用法二：记忆化¶
下面这段算的是网格路径计数：只能向下或向右走，f(i, j) 是从起点走到格子 \((i, j)\) 的方案数。
不加 memo 时，f(i-1, j) 和 f(i, j-1) 会各自再去算 f(i-1, j-1)——
同一个 \((i, j)\) 被不同的路径反复算到，规模一大就退化成指数级。
memo 做的事只有一件：同一个 \((i, j)\) 只真算一次，把指数级压成 \(O(nm)\)。
memo = {}
def f(i, j):
key = (i, j) # 元组当复合键，见第 6 章
if key in memo:
return memo[key]
if i == 0 or j == 0: # 贴着边走只有一条路
res = 1
else:
res = f(i - 1, j) + f(i, j - 1)
memo[key] = res
return res
标准库有现成的装饰器：
lru_cache 底层就是一个 dict，但它在 C 层实现，比手写 memo 快。
参数必须可哈希（所以不能传 list，要传 tuple）。
详见 记忆化搜索与剪枝。
Python 3.9 新增的
functools.cache等价于lru_cache(maxsize=None)，写起来更短。 3.9 环境下两者都可用。
用法三：映射与判重¶
这一类的共同点是拿值当键、拿下标当值，把「这个值出现过吗、在哪出现的」 从 \(O(n)\) 的扫描变成 \(O(1)\) 的查表。
pos = {x: i for i, x in enumerate(a)} # 值 → 下标（重复值只留最后一个）
seen = {} # 记录「第一次出现的位置」
for i, x in enumerate(a):
if x in seen:
print(seen[x], i) # 两数之和 / 找重复的经典写法
else:
seen[x] = i
两种写法的区别在建表的时机：推导式是一次建好，所以同一个值只剩最后一个下标；
边遍历边写的 seen 只在没见过时才记，留下的是第一次出现的位置。
要「最早的那一对」就得用后者。
7 复杂度与两个陷阱¶
| 操作 | 平均 | 最坏 |
|---|---|---|
d[k] 查 / 改 / in |
\(O(1)\) | \(O(n)\)（全部哈希冲突） |
| 插入 / 删除 | \(O(1)\) 均摊 | \(O(n)\)（触发 rehash） |
| 遍历 | \(O(n)\) | \(O(n)\) |
len |
\(O(1)\) | \(O(1)\) |
陷阱一：内存¶
dict 每个条目要存哈希值、键指针、值指针，加上为了低冲突而保留的空槽，
一个 \(10^6\) 项的 dict 大约要 80–150 MB。同样规模的 list 只要 8 MB。
值域是连续小整数时一律用 list。 这既是速度问题也是内存问题。
陷阱二：被卡哈希¶
CPython 的 dict 用开放寻址：哈希值先对表长取余定位到一个槽，
槽被别人占了就按固定规则再探测下一个，直到找到空槽或目标键。
正常情况下这条探测链只有一两步，所以查找是 \(O(1)\)。
而 CPython 里 hash(int) 基本就是整数本身（小整数时 hash(n) == n）。
出题人只要构造大量哈希值同余于表长的键（比如全是 \(2^{20}\) 的倍数），
这些键就会挤进同一条探测链，\(O(1)\) 退化成 \(O(n)\)，整体变 \(O(n^2)\)。
自保办法是给键加一个随机扰动：
字符串键相对安全：CPython 默认开启哈希随机化（
PYTHONHASHSEED每次运行不同）， 出题人无法离线构造。但整数键没有这层保护， 遇到「明明是 \(O(n)\) 却 TLE」的哈希题就往这上面想。见 哈希表。
8 defaultdict 与 Counter 预告¶
这两个是 collections 里的 dict 子类，竞赛里出场率极高，这里先建立印象，
完整 API 见 标准库速查。
defaultdict¶
访问不存在的键时，自动调用工厂函数创建默认值：
from collections import defaultdict
cnt = defaultdict(int) # 默认 0
cnt[x] += 1 # 不用先判断存在
g = defaultdict(list) # 默认空列表
g[u].append(v) # 邻接表一行搞定
s = defaultdict(set)
s[u].add(v)
遍历过程中这样读会直接引发「遍历时修改字典」的
defaultdict的副作用：读一个不存在的键也会创建它。RuntimeError。 只读判断请用g.get(5)或5 in g。
Counter¶
专门做计数的 dict 子类：
from collections import Counter
c = Counter("abracadabra") # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
c["a"] # 5
c["z"] # 0 ← 不存在返回 0，不抛 KeyError
c.most_common(3) # [('a', 5), ('b', 2), ('r', 2)] 按计数降序
c.most_common() # 全部，按计数降序
sum(c.values()) # 总数
c1 + c2, c1 - c2, c1 & c2, c1 | c2 # 计数的加 / 减 / 取小 / 取大
Counter 可以直接当多重集合（multiset）用，见
集合与多重集合。
most_common的排序规则要小心：计数相同的元素按插入顺序排（3.7+）， 不是按键的字典序。题目要求「频次相同按字典序」时不能直接用most_common， 必须显式sorted。下面的例题正是考这个。
9 例题：BISHI23 小红书推荐系统（简单，哈希 / 排序）¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI23 | 小红书推荐系统 | 简单 | 题解 |
给定一行由小写字母和空格组成的搜索记录（长度 \(\le 10^5\)）。 出现次数 \(\ge 3\) 的单词称为关键词。输出所有关键词， 按频次从高到低；频次相同的按字典序升序。 题面见 原题。
三步：分词 → 计数 → 排序输出。
import sys
def main():
words = sys.stdin.buffer.read().split() # 按任意空白切分，自动处理连续空格
cnt = {}
for w in words:
cnt[w] = cnt.get(w, 0) + 1
# 频次降序 + 字典序升序：把 -频次 放在元组第 0 位，键放第 1 位
keys = sorted((-c, w.decode()) for w, c in cnt.items() if c >= 3)
sys.stdout.write("\n".join(w for _, w in keys) + "\n")
main()
四个要点：
-
split()无参版天然处理连续空格（见 字符串）。 如果写成split(" ")，"a b"会切出一个空串，凭空多一个「空单词」。 -
双关键字排序用元组。
(-c, w)让 Python 先比-c（等价于按c降序）， 再比w（字典序升序）。这就是 元组与序列通论 讲的元组字典序比较。 -
不能用
Counter.most_common()。它在计数相同时按插入顺序排， 而题目要求字典序。样例里game和kou都出现 3 次，kou先出现，most_common会把kou排在前面 —— 直接 WA。 -
bytes要.decode()。这题用的是最快的一档读入（取舍见 输入输出处理）；从buffer.read()读出来的是bytes， 排序用bytes也没问题（ASCII 下字典序一致）， 但"\n".join要求元素是str。这里在建元组时就顺手解码了。
复杂度：设有 \(m\) 个不同单词，\(O(L + m \log m)\)，\(L\) 是总长度。\(10^5\) 规模轻松通过。
用 Counter 写会更短，但排序还是得自己写：
from collections import Counter
import sys
cnt = Counter(sys.stdin.buffer.read().split())
# 排序键是元组 (-c, 单词)：元组按字典序逐项比较，
# 次数取负号就把「次数降序」翻译成了升序排序，第二项再按单词升序，
# 一次 sorted 同时满足「频次高的在前，同频按字典序」两个要求
keys = sorted((-c, w.decode()) for w, c in cnt.items() if c >= 3)
print("\n".join(w for _, w in keys))
举一反三：「按频次降序 + 同频按字典序」是词频题的标准输出要求， 记住
sorted((-c, k) for ...)这个模板，以后照抄。它和速查表里的
sorted(d.items(), key=lambda kv: (-kv[1], kv[0]))是同一件事的两种写法： 后者排的仍是原来的(键, 值)对，靠key现算排序键，排完直接就能用； 前者把排序键本身当成元素，所以排完要for _, k in把键取回来。 需要在建元组时顺手做点加工（这里的.decode()）就用前者，否则用后者更直白。
10 本章速查¶
| 场景 | 写法 |
|---|---|
| 空字典 | d = {}（{} 不是空集合，空集合是 set()） |
| 安全取值 | d.get(k, 0)，别写 if k in d: ... else: ... |
| 计数（整段序列） | Counter(a) |
| 计数（边算边加） | cnt[x] = cnt.get(x, 0) + 1 或 defaultdict(int) |
| 值域小且连续 | 用 list 不用 dict，快 3–5 倍 |
| 邻接表 | g.setdefault(u, []).append(v) 或 defaultdict(list) |
| 两个列表压成字典 | dict(zip(keys, vals)) |
| 反转键值 | {v: k for k, v in d.items()} |
| 离散化 | {x: i for i, x in enumerate(sorted(set(a)))} |
| 保序去重 | list(dict.fromkeys(a)) |
| 记忆化 | @lru_cache(maxsize=None)，参数必须可哈希 |
| 遍历键值 | for k, v in d.items(): |
| 遍历时删键 | 先 for k in list(d): 固化快照 |
| 按键排序输出 | for k in sorted(d): |
| 按值降序 + 键升序 | sorted(d.items(), key=lambda kv: (-kv[1], kv[0]))，排完还是 (k, v) 对 |
| 同上，另一种写法 | sorted((-v, k) for k, v in d.items())，排完要 for _, k in 取回 |
| 键的要求 | 必须可哈希；1/1.0/True 是同一个键 |
| 有序表需求 | Python 没有 std::map，见平衡树与有序集合 |
| 被卡哈希 | 键异或一个随机数 x ^ RND |