第 7 章 字典¶
配套例题：BISHI23 小红书推荐系统 来源：菜鸟教程 Python3 字典、Python3 数据结构
dict 是 Python 的哈希表，对应 C++ 的 std::unordered_map。
它是语言内置、C 实现、高度优化的——在 Python 里手写哈希表永远打不过它。
竞赛中 dict 承担三件事：
- 计数（词频、桶统计、出现次数）
- 记忆化（把递归搜索变成 DP）
- 映射 / 离散化（把稀疏的大值域压到小下标）
本章还有一个 C++ 选手必须调整的认知：Python 的 dict 保持插入顺序，
但它不是有序表——它没有 std::map 的按键有序遍历和 lower_bound。
7.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, [])是个陷阱：所有键会共享同一个列表对象， 和 05-列表 里的[[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 的唯一来源，读进来立刻决定用什么类型做键。
7.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))
d2 = {**d, "b": 9} # 合并成新字典（3.5+）
d3 = d | {"b": 9} # 合并运算符（3.9+）
d |= {"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)\) |
7.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）。
7.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就得上树状数组 / 有序列表，见 116-平衡树与有序集合。另外永远不要依赖字典顺序来产生题目要求的输出顺序。 题目说「按字典序输出」就老老实实
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])): # 值降序 + 键升序
...
7.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\)， 之后就能用数组代替字典（更快）。见 41-桶计数与离散化。
推导式的完整语法（多重循环、条件）见 09-推导式。
7.6 dict 作哈希表：三大用法¶
用法一：计数¶
五种写法，从慢到快：
# ① 最笨
if x in cnt:
cnt[x] += 1
else:
cnt[x] = 1
# ② get，一行
cnt[x] = cnt.get(x, 0) + 1
# ③ setdefault
cnt.setdefault(x, 0)
cnt[x] += 1
# ④ defaultdict
from collections import defaultdict
cnt = defaultdict(int)
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)。
用法二：记忆化¶
把指数级的重复递归压成多项式：
memo = {}
def f(i, j):
key = (i, j) # 元组当复合键，见第 6 章
if key in memo:
return memo[key]
if i == 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）。
详见 62-记忆化搜索与剪枝。
Python 3.9 新增的
functools.cache等价于lru_cache(maxsize=None)，写起来更短。 3.9 环境下两者都可用。
用法三：映射与判重¶
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
7.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」的哈希题就往这上面想。见 36-哈希与字符串哈希。
7.8 defaultdict 与 Counter 预告¶
这两个是 collections 里的 dict 子类，竞赛里出场率极高，这里先建立印象，
完整 API 见 14-标准库速查。
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）用，见
34-集合与多重集合。
most_common的排序规则要小心：计数相同的元素按插入顺序排（3.7+）， 不是按键的字典序。题目要求「频次相同按字典序」时不能直接用most_common， 必须显式sorted。下面的例题正是考这个。
7.9 例题：BISHI23 小红书推荐系统（简单，哈希 / 排序）¶
给定一行由小写字母和空格组成的搜索记录（长度 \(\le 10^5\)）。 出现次数 \(\ge 3\) 的单词称为关键词。输出所有关键词， 按频次从高到低；频次相同的按字典序升序。 题面见 BISHI23 原题（牛客）。
三步：分词 → 计数 → 排序输出。
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()无参版天然处理连续空格（见 04-字符串）。 如果写成split(" ")，"a b"会切出一个空串，凭空多一个「空单词」。 -
双关键字排序用元组。
(-c, w)让 Python 先比-c（等价于按c降序）， 再比w（字典序升序）。这就是 06-元组与序列通论 讲的元组字典序比较。 -
不能用
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 ...)这个模板，以后照抄。
7.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])) |
| 键的要求 | 必须可哈希；1/1.0/True 是同一个键 |
| 有序表需求 | Python 没有 std::map，见第 116 章 |
| 被卡哈希 | 键异或一个随机数 x ^ RND |