dict 是 Python 里最重要的数据结构之一，没有它很多代码写起来会非常痛苦。在算法竞赛中，dict 的本质是哈希表， 插入、 查找，配上 get、defaultdict、Counter 三个变体，覆盖了竞赛中至少 30% 的数据结构需求。
0. dict 基础回顾
1d = {}
2d["key"] = value # 插入 / 修改
3d.get("key", default) # 安全取值，不存在返回 default
4"key" in d # 判存在
5d.keys() # 所有 key
6d.values() # 所有 value
7list(d) # key 列表
1. 计数器（频次统计）
最最常见的用法，统计每个元素出现了多少次。
1arr = [1, 3, 2, 1, 3, 1]
2
3cnt = {}
4for x in arr:
5 cnt[x] = cnt.get(x, 0) + 1
6
7print(cnt) # {1: 3, 3: 2, 2: 1}
等价于一行
Counterfrom collections import Counter 然后 cnt = Counter(arr) 直接得到同样的结果。
2. 映射 / 替换规则
把一种值映射到另一种值，常用于编码转换。
1mp = {"石头": 0, "剪刀": 1, "布": 2}
2code = mp["石头"] # 0
3. 记忆化 / DP 缓存
当状态不是简单的整数下标（比如 (mask, last) 这样的元组）时，用 dict 做手动 cache。
1cache = {}
2
3def dfs(mask, last):
4 key = (mask, last)
5 if key in cache:
6 return cache[key]
7 # ... 计算 ...
8 cache[key] = ans
9 return ans
其实就是 @cache 底层做的事，只是这里你可以手动控制何时清空缓存。
4. 邻接表（图）
当节点编号不连续或不是整数（如字符串名称）时，dict 比 list 更适合做邻接表。
1g = {}
2for u, v in edges:
3 if u not in g: g[u] = []
4 if v not in g: g[v] = []
5 g[u].append(v)
6 g[v].append(u)
当然，配合下一节的 defaultdict 写起来更干净。
5. defaultdict：省掉判存在
defaultdict 是 dict 的增强版——访问不存在的 key 时，自动调用工厂函数生成默认值，不会抛 KeyError。
1from collections import defaultdict
5.1 统计频次
1arr = [1, 3, 2, 1, 3, 1]
2cnt = defaultdict(int) # 默认值是 0
3
4for x in arr:
5 cnt[x] += 1 # 首次 cnt[x] 自动 = 0
6
7print(cnt) # {1: 3, 3: 2, 2: 1}
5.2 分组聚合
把元素按某个 key 分组，value 存成列表。
1items = [("苹果", 5), ("香蕉", 3), ("苹果", 2), ("香蕉", 7)]
2
3groups = defaultdict(list)
4for name, val in items:
5 groups[name].append(val)
6
7print(dict(groups))
8# {'苹果': [5, 2], '香蕉': [3, 7]}
5.3 邻接表建图
1g = defaultdict(list)
2
3for u, v in edges:
4 g[u].append(v)
5 g[v].append(u)
6
7# 直接 g[u] 访问，首次自动是 []
5.4 多层嵌套 defaultdict
比如要建一个 dict 套 dict 的结构：
1d = defaultdict(lambda: defaultdict(int))
2d["Alice"]["数学"] += 1
3d["Alice"]["语文"] += 1
4d["Bob"]["数学"] += 1
6. 去重 + 记录位置
保留每个元素第一次出现的位置。
1arr = [4, 2, 4, 1, 2, 3]
2pos = {}
3
4for i, x in enumerate(arr):
5 if x not in pos:
6 pos[x] = i
7
8print(pos) # {4: 0, 2: 1, 1: 3, 3: 5}
7. 两数之和（查找表）
经典 解法，用 dict 存“值→下标”。
1arr = [2, 7, 11, 15]
2target = 9
3
4seen = {}
5for i, x in enumerate(arr):
6 need = target - x
7 if need in seen:
8 print(seen[need], i) # 0 1
9 seen[x] = i
8. 坐标离散化
稀疏坐标映射成连续的整数下标，用于线段树或 BIT。
1xs = sorted(set(raw_xs))
2mp = {v: i for i, v in enumerate(xs)}
9. 合并区间 / 分组聚合
和 5.2 类似，但场景更明确：把一对多的关联关系整理成 dict。
1pairs = [("A", 1), ("B", 2), ("A", 3), ("B", 4)]
2agg = defaultdict(list)
3
4for k, v in pairs:
5 agg[k].append(v)
6
7print(dict(agg)) # {'A': [1, 3], 'B': [2, 4]}
总结
| 场景 | 写法 | 备注 |
|---|---|---|
| 统计频次 | d[x] = d.get(x, 0) + 1 | 或 Counter |
| 分组 | defaultdict(list) | 自动建空列表 |
| 查表 | if key in d: | 判存在 |
| 手动 cache | key = (a,b); d[key] | 状态是复合结构时 |
| 邻接表 | defaultdict(list) | 节点不连续时 |
| 嵌套结构 | defaultdict(lambda: defaultdict(int)) | 二维统计 |
dict + defaultdict + Counter 这三件套，基本覆盖了竞赛中所有哈希表需求。