深入理解 Python dict 与 set：从哈希表底层到高性能实战

一、从一个实际场景出发

假设你要根据同学的名字查找对应的成绩。最朴素的做法是用两个列表，下标一一对应：

names  = ["A", "B", "C"]
scores = [59, 89, 90]

# 查找 B 的成绩
idx = names.index("B")   # O(n) 遍历
print(scores[idx])        # 89

这样做的坏处显而易见：每次查找都要把整个列表从上到下捋一遍。如果有 100 万个名字，最坏情况下就得比对着看 100 万次——这就是 O(n) 的代价。

但 Python 里有个神器叫 dict（字典），它能把这个操作直接变成 O(1)：

d = {"D": 100, "E": 99, "F": 99}
print(d["D"])   # 100 —— 一步到位！

这就像字典前面的偏旁索引——你不用从第一页翻到最后一页，而是直接定位到目标。这个“一步到位”的能力，背后站着的就是哈希表（Hash Table）。

二、什么是哈希表

2.1 核心流程

哈希表是一种基于键值对（key-value）存储数据的结构。它的工作流可以想象成一条流水线：

key  ──→  哈希函数  ──→  索引  ──→  存储位置（value）

1. key 必须唯一
2. 对 key 执行哈希运算，得到一个整数（哈希值）
3. 用这个哈希值计算出数组索引
4. 索引指向的内存位置，存着对应的 value
5. 查找时，直接拿 key 算出同一个索引，O(1) 取出 value

2.2 哈希冲突

不同的 key 有可能算出相同的索引——冲突就这样产生了。比如 "abc" 和 "cba" 经过哈希后，恰好定位到同一个槽位。

对于这个难题，业内主要有两种解法：

CPython 选的是开放寻址法 + 伪随机探测。这也是为什么 dict 总要预留大量空位——表一旦塞得太满，探测路径就会变长，O(1) 的承诺就会打折扣。

2.3 负载因子与扩容

• 负载因子 = 已用槽位 / 总槽位
• 当负载因子超过阈值（Python dict 大约在 2/3），就会触发扩容（rehash）
• 扩容时分配更大的数组，所有 key 的位置都要重新算一遍

这就揭示了一个核心特征：哈希表天生就是“空间换时间”的——占据内存多，但查找极快。

三、Python dict 详解

3.1 基本操作

d = {"D": 100, "E": 99, "F": 99}

# 取值
d["D"]            # 100（key 不存在则 KeyError）

# 安全取值
d.get("Thomas")     # None（不报错）
d.get("Thomas", -1) # -1（自定义默认值）

# 新增 / 修改
d["Adam"] = 67      # 新增
d["Adam"] = 90      # 修改（key 相同，覆盖原值）

# 判断 key 是否存在
"Thomas" in d       # False

# 删除
d.pop("Adam")       # 返回 90，key 不存在则 KeyError

3.2 常用方法速查

3.3 插入顺序

从 Python 3.7 开始，dict 保证按插入顺序遍历（3.6 只是 CPython 的实现细节，3.7 变成了语言规范）。

d = {}
d["a"] = 1
d["c"] = 3
d["b"] = 2
print(list(d.keys()))   # ['a', 'c', 'b'] —— 严格按插入顺序

3.4 字典推导式

# 将列表转为 {元素: 索引} 的映射
items = ["apple", "banana", "cherry"]
d = {v: i for i, v in enumerate(items)}
# {"apple": 0, "banana": 1, "cherry": 2}

# 基于条件过滤
squares = {x: x**2 for x in range(10) if x % 2 == 0}
# {0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

3.5 collections 扩展

Python 标准库 collections 提供了几个常用的 dict 变体，可以说是日常开发的利器：

from collections import defaultdict, Counter, OrderedDict

# defaultdict —— 访问不存在的 key 时自动生成默认值
dd = defaultdict(list)
dd["fruits"].append("apple")    # 无需先初始化 []
print(dd["fruits"])             # ['apple']

dd = defaultdict(int)
words = ["a", "b", "a", "c", "b", "a"]
for w in words:
    dd[w] += 1                  # 无需判断 key 是否存在
print(dd)   # {'a': 3, 'b': 2, 'c': 1}

# Counter —— 专门用于计数的字典
c = Counter(words)
print(c.most_common(2))   # [('a', 3), ('b', 2)]

3.6 时间复杂度一览

四、dict 与 list 对比

选择建议：

• 需要按 key 快速查找 → dict
• 只需有序存储/遍历 → list
• 需要去重或集合运算 → set

五、不可变对象与 hashable

5.1 dict 的 key 必须是可哈希的

# ✅ 不可变类型 — 可作 key
d = {}
d["name"] = "Alice"      # str 可哈希
d[42]      = "answer"    # int 可哈希
d[(1, 2)]  = "point"     # tuple（元素全不可变）可哈希

# ❌ 可变类型 — 不可作 key
d[[1, 2, 3]] = "list"    # TypeError: unhashable type: 'list'

为什么？ dict 靠 key 的哈希值来决定 value 的存放位置。如果 key 是可变的（比如 list 能 append），它的哈希值就会跟着变，dict 就再也找不到原来的数据了——整个结构会陷入混乱。

5.2 可变 vs 不可变对象

# list 是可变对象 — 方法修改对象本身
a = ['c', 'b', 'a']
a.sort()                # sort() 原地修改，返回 None
print(a)                # ['a', 'b', 'c'] — 同一个对象，内容变了

# str 是不可变对象 — 方法返回新对象
s = "abc"
print(s.replace("a", "A"))  # "Abc" — 新字符串
print(s)                    # "abc" — 原字符串未变！

六、Python set 详解

6.1 set 是什么

set 和 dict 本质上是同一类东西——都是一组 key 的集合。唯一的区别是 set 不存储对应的 value。因为 key 不能重复，set 天生就保证了元素唯一。

6.2 创建与基本操作

# 两种创建方式
s = {1, 2, 3}                # 字面量
s = set([1, 2, 3, 4, 2])    # 从可迭代对象构建，自动去重 → {1, 2, 3, 4}

# 基本操作
s.add(5)        # 添加元素
s.remove(1)     # 删除元素（元素不存在则 KeyError）
s.discard(1)    # 删除元素（元素不存在也不报错）

6.3 集合运算

s1 = {1, 2, 3}
s2 = {2, 3, 4}

# 交集
s1 & s2           # {2, 3}
s1.intersection(s2)

# 并集
s1 | s2           # {1, 2, 3, 4}
s1.union(s2)

# 差集
s1 - s2           # {1}  —— 在 s1 但不在 s2
s1.difference(s2)

# 对称差集（并集 - 交集）
s1 ^ s2           # {1, 4}  —— 在 s1 或 s2 但不同时在两者
s1.symmetric_difference(s2)

6.4 集合推导式

# 找出列表中所有出现过的字符
words = ["hello", "world", "python"]
unique_chars = {c for w in words for c in w}
# {'h', 'e', 'l', 'o', 'w', 'r', 'd', 'p', 'y', 't', 'n'}

6.5 判断关系

a = {1, 2}
b = {1, 2, 3, 4}

a.issubset(b)       # True  — a 是 b 的子集
b.issuperset(a)     # True  — b 是 a 的超集
a.isdisjoint({5})   # True  — 没有交集

6.6 frozenset——不可变集合

fs = frozenset([1, 2, 3])
# fs.add(4)              # AttributeError —— 不可修改
d = {fs: "valid"}        # ✅ frozenset 可作 dict 的 key（因为不可变）

6.7 set 时间复杂度

七、实战场景总结

八、小结

1. 哈希表 = 哈希函数 + 数组，key → 索引 → value，O(1) 查找
2. dict = 带 value 的哈希表，空间换时间
3. set = 只有 key 的哈希表，天然去重 + 集合运算
4. 可变对象不可哈希（list/set/dict 不能作 key），不可变对象可哈希（str/int/tuple/frozenset）
5. Python 3.7+ dict 保持插入顺序，collections 提供 defaultdict、Counter 等实用扩展