第 12 讲：容器类型实现——list、dict、set 的 C 实现

大家好，我是正在实战各种 AI 项目的程序员晚枫。

列表的动态数组、字典的哈希表、集合的实现原理。这一讲，让你彻底理解 Python 容器类型的性能秘密。

---

📖 开篇：为什么列表可以用索引访问？

lst = [10, 20, 30, 40]
print(lst[2])  # 30，O(1) 时间复杂度

C 语言的数组可以用索引 O(1) 访问，Python 的列表也是——因为它底层就是动态数组！

---

📋 PyListObject（列表）

// Include/listobject.h
typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;     // 元素指针数组（PyObject* 的数组）
    Py_ssize_t allocated;   // 已分配的槽位数
} PyListObject;

动态数组原理

allocated = 8  (已分配空间)
ob_item   →  [None, None, None, None, None, None, None, None]  # 8个槽位

当我们 append 新元素：
len = 4  →  ob_item = [10, 20, 30, 40]
          allocated = 8  # 空间够，不用扩容

再 append 3 个：
len = 7  →  allocated = 8  # 刚好够

再 append 1 个：
len = 8  →  allocated = 8  # 满了！扩容！

扩容策略

// 当元素数量达到 allocated 时，触发扩容
// 新 allocated = (newsize + (newsize >> 3) + 6) & ~3

# 即：按 12.5% + 6 的增量增长
# list.append() 平均是 O(1)  amortized（摊销常数时间）

性能真相

import time

# 在列表头部插入（慢！O(n)）
lst = list(range(100000))
start = time.perf_counter()
lst.insert(0, 999)
end = time.perf_counter()
print(f"头部插入: {end - start:.6f}s")

# 在列表尾部插入（快！O(1) amortized）
lst = list(range(100000))
start = time.perf_counter()
lst.append(999)
end = time.perf_counter()
print(f"尾部插入: {end - start:.6f}s")

---

🗂️ PyDictObject（字典）

Python 3.6+ 的字典发生了革命性变化——从「哈希表 + 开放寻址」变成「紧凑数组」：

旧版实现（Python 2.7 / 3.5 之前）

哈希表：[slot0, slot1, slot2, slot3, ...]
          [None,  [key,val], None, [key,val], ...]
          
问题：哈希冲突、空间浪费、顺序不确定

新版实现（Python 3.6+，DictProtocol）

d = {}          # 空字典
d['a'] = 1      # 插入
d['b'] = 2      # 按插入顺序存储
d['c'] = 3

# keys() 现在是按插入顺序的！
print(list(d.keys()))  # ['a', 'b', 'c']

新结构：

• keys 数组：存储哈希值 + 键索引（类似稀疏数组）
• values 数组：按插入顺序存储值（紧凑数组）
• key 数组：按插入顺序存储键（紧凑数组）

// Objects/dictobject.c
typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;        // 已使用的槽位
    int64_t version_tag;        // 快速检测修改
    PyDictKeysObject *ma_keys;  // 键数组
    PyObject **ma_values;       // 值数组（NULL 表示未使用）
} PyDictObject;

哈希冲突解决

# 字典查找过程：
# 1. 计算 key 的哈希值
# 2. 定位 keys 数组中的位置
# 3. 检查是否匹配（比较哈希值 + 键对象）

d = {}
d[1] = 'one'
d[1.0] = 'one point zero'  # 1 和 1.0 哈希相同！

print(d)  # {1: 'one point zero'}，后者覆盖前者

---

🔮 set（集合）

set 底层和字典的 keys 数组几乎一样，只是没有 values：

s = {1, 2, 3, 4, 5}
print(len(s))  # 5

# 集合元素必须是可哈希的
try:
    s.add([6])  # TypeError! 列表不可哈希
except TypeError as e:
    print(f"错误：{e}")

set 的性能特点

操作	平均复杂度	说明
添加/删除	O(1)	哈希查找
成员检查	O(1)	x in s
交集/并集	O(min(len(s1), len(s2)))	遍历较小的集合
遍历	O(n)	按哈希顺序

# 集合的高效操作
a = {1, 2, 3, 4, 5}
b = {4, 5, 6, 7, 8}

print(a & b)   # {4, 5} 交集
print(a | b)   # {1,2,3,4,5,6,7,8} 并集
print(a - b)   # {1, 2, 3} 差集
print(a ^ b)   # {1, 2, 3, 6, 7, 8} 对称差集

---

💡 本节作业

1. 用 timeit 比较列表 append 和 insert(0, x) 的性能差异
2. 验证字典的插入顺序：d = {}; d['b']=1; d['a']=2; d['c']=3; print(list(d.keys()))
3. 写一个程序：用 set 对两个列表去重并找交集

---

🎯 本讲总结

PyListObject：动态数组，over-allocate 扩容策略，append 均摊 O(1)。

PyDictObject：3.6+ 使用紧凑数组，keys + values 分离，保持插入顺序。

PySetObject：类似字典的 keys 数组，无 values，必须可哈希。

性能关键：在列表尾部操作，避免头部插入。

---

📚 推荐教材

《Python 编程从入门到实践（第 3 版）》 | 《流畅的 Python（第 2 版）》 | 《CPython 设计与实现》

---

🔗 课程导航

← 上一讲：字符串类型实现 | 下一讲：函数与类实现 →

---

💬 联系我

平台	账号/链接
微信	扫码加好友
B 站	Python 自动化办公社区

主营业务：AI 编程培训、企业内训、技术咨询

进群

嗨，扫码 进群

微信