字典与集合

1. 一句话定义

dict 是哈希表实现的键值映射（3.7+ 保证插入序），set 是哈希表实现的无重复集合；两者的键/元素都必须可哈希。

2. 为什么重要

dict 是 Python 的地基数据结构：模块命名空间、对象属性（__dict__）、关键字参数，底层全是 dict。掌握它等于掌握半个 Python；set 则是去重与成员判断 O(1) 的标配。

3. 前置知识

kp-004（可哈希 = 不可变）、kp-009。

4. 核心概念

• dict 操作：d[k]（缺失则 KeyError）、d.get(k, default)、d[k] = v（新增/覆盖）、del d[k]、d.pop(k, default)、d.items()/keys()/values()、d.setdefault(k, default)。
• set 操作：| & - ^（并交差对称差）、add/discard/remove、frozenset（不可变版，可作键）。
• 合并：{**a, **b} 与 3.9+ 的 a | b。

5. 原理与机制

哈希表：插入时计算 hash(key) 定位桶。副作用规则：

• 键必须可哈希（不可变且 __hash__ 稳定），所以 list/set/dict 不能作键。
• dict 的大小是键值对，set 是元素；都通过哈希实现 O(1) 平均查找。
• 3.7+ dict 保持插入顺序（实现收敛带来的保证），set 无顺序。

from collections import defaultdict, Counter

counts = defaultdict(int)
for ch in "abracadabra":
    counts[ch] += 1               # 缺键自动置 0，省 get 判断

Counter("abracadabra").most_common(2)   # [('a', 5), ('b', 2)]

prices = {"apple": 3, "pear": 2}
{ k: v * 2 for k, v in prices.items() }    # dict 推导式（kp-011）

6. 关键事实（模型/图示）

        hash(key) ──► 桶位置 ──► 值
查找平均 O(1)；最坏 O(n)（哈希碰撞极端情形）
dict 键 → 必须可哈希；dict 值 → 任意
set  → 只有键一半的哈希表

7. 直观类比

dict 像酒店前台：报房间号（键）取钥匙（值），不管你是谁、顺序如何，报对号就能秒取；set 像进场验票：只记"来过没来过"，不记第几个来的。

8. 实例与案例

# 去重且保序（list → set 丢顺序，用 dict 键保序）
items = ["b", "a", "b", "c", "a"]
list(dict.fromkeys(items))            # ['b', 'a', 'c']

# 两个 JSON 配置合并，后者的键覆盖前者
merged = {**defaults, **overrides}

9. 常见误区

1. 遍历时增删 dict 键 —— RuntimeError；先收集 list(d) 再改。
2. 用 d.get(k) 的返回值区分"不存在"与"值是 None" —— 两者返回相同；需要区分用 k in d 或哨兵 d.get(k, _MISSING)。
3. 以为 set 有顺序 —— 没有；需要有序去重见上例。
4. d[k] 直接取不存在的键 —— KeyError；读时不确定存在就用 get，写时直接 d[k]=v。

10. 自测题

1. 为什么 list 不能作 dict 键？
2. list(dict.fromkeys(x)) 实现了什么效果？与 list(set(x)) 差异？
3. defaultdict(list) 常用于什么场景？

11. 与其他知识点的关系

• kp-011 推导式：dict/set 推导式。
• kp-019 魔术方法：__hash__ 与 __eq__ 的联动规则。
• kp-022 标准库：defaultdict/Counter/deque 所在。

12. 延伸阅读

• Fluent Python 第 3 章 Dictionaries and Sets
• Python 官方教程 §5.3（推导式与字典）