dict 与 set 同源于哈希表：以可哈希约束和内存开销为代价，换取平均 O(1) 的查找语义。本文拆解底层结构、键约束、扩容策略、保序性与惯用范式。
哈希表底层
CPython 的 dict 采用开放寻址法（open addressing）：hash(key) 定位槽位，冲突后按扰动探测序列找下一空槽，表内无链表指针。set 是一张只存键、不存值的同类哈希表，二者共享同一套底层设计。
| 操作 | 平均 | 最坏 |
|---|---|---|
d[k] 增删改查 | O(1) | O(n)（碰撞集中） |
x in list | O(n) | — |
x in set | O(1) | O(n) |
哈希碰撞极端时性能退化为线性扫描——3.4 起 str/bytes 哈希加盐随机化，正是针对哈希碰撞 DoS 的防御。
键必须可哈希
可哈希的契约：__hash__ 返回稳定整数，且 a == b 蕴含 hash(a) == hash(b)。标准类型中：
- 可哈希：str、int、float、bool、bytes、frozenset、元素全可哈希的 tuple
- 不可哈希：list、dict、set——可变值哈希会漂移，槽位索引随之失效
d = {}
d[(1, 2)] = "point" # tuple 可作键
d[[1, 2]] = "nope" # TypeError: unhashable type: 'list'自定义类默认按身份哈希（继承 object 的 __hash__）；一旦定义 __eq__，__hash__ 自动置 None、实例不可哈希，需显式实现——协议契约见 特殊方法。
装填因子与扩容
哈希表刻意保持稀疏：条目超过容量 2/3（装填因子阈值）即触发扩容——分配更大的表并整体 rehash 迁移。推论：
- 单次插入偶发 O(n)，摊还仍 O(1)
- 批量构建用字面量、推导式、
dict(zip(ks, vs))，比循环逐项插入快（减少中途扩容与重复探测）
保序性（3.7+）
dict 自 3.7 起按插入顺序迭代是语言规范（3.6 只是实现细节）：条目挂在插入链上，哈希表只管索引。有序 ≠ 排序，按 key 输出仍需 sorted(d.items())。
set 完全无序，永远不要依赖其迭代顺序——整型集合看似有序只是小整数哈希值即自身的巧合。集合运算符及其优先级的坑见 Python 中 set 的符号计算优先级。
set 与 frozenset
a = {1, 2, 3}
b = {3, 4, 5}
a | b # 并 {1, 2, 3, 4, 5}
a & b # 交 {3}
a - b # 差 {1, 2}
a ^ b # 对称差 {1, 2, 4, 5}
a <= b # 子集（< 真子集，>= 超集）frozenset不可变因而可哈希，可作 dict 键或另一集合的元素{}是空 dict，空 set 必须写set()- 去重惯用法：保序
list(dict.fromkeys(xs))，不保序list(set(xs))
missing 与 defaultdict
d[k] 未命中默认抛 KeyError；dict 子类可实现 __missing__ 钩子拦截：
class UpperDict(dict):
def __missing__(self, key):
return key.upper() # 只补值，不写入
UpperDict()["hi"] # 'HI'collections 的 defaultdict 走工厂路线——未命中时调用工厂并把结果写入：
from collections import defaultdict
index = defaultdict(list)
for w in words:
index[w[0]].append(w) # 首次访问自动创建空 list，免去 setdefault三档语义按需选：d.get(k, default) 取值不写入；d.setdefault(k, default) 取值且写入；defaultdict 未命中自动造值并落盘。
字典视图与推导
d.keys() / d.values() / d.items() 返回视图对象——不是拷贝，动态追踪 dict 的后续变更；keys/items 视图还支持集合运算：
common = d1.keys() & d2.keys() # 两个 dict 的公共键
positive = {k: v for k, v in d.items() if v} # 字典推导式过滤
squares = {x: x * x for x in range(6)} # 构造推导dict/set 的本质是拿内存换速度、拿可哈希约束换 O(1)：查找密集、成员测试、分组聚合、去重场景几乎总是正解；键为连续小整数且追求极致紧凑时，list 才有竞争力。