Python 内置数据结构与性能特征
更新时间：2026-08-30。本文回答：为什么
x in my_list在大列表上慢，换成set就快了？dict 为什么能 O(1) 查找？tuple 和 list 到底差在哪？ 选对结构是 Python 性能优化的第一道关。
一、list：动态数组，不是链表
list 底层是连续内存的动态数组（类似 C++ 的 std::vector）。它存的是对象的引用，不是对象本身。
python
lst = [1, 2, 3]
lst.append(4) # 平均 O(1)；容量不够时整体扩容（通常 1.125 倍）| 操作 | 复杂度 | 说明 |
|---|---|---|
按下标访问 lst[i] | O(1) | 数组随机访问 |
尾部追加 append | O(1) 均摊 | 偶尔扩容复制 |
中间插入 insert(0,x) | O(n) | 后续元素整体后移 |
成员判断 x in lst | O(n) | 线性扫描，大列表慎用 |
删除 pop() 尾部 | O(1) | 头部 pop(0) 是 O(n) |
坑：在头部反复 insert(0, x) 或 pop(0) 是 O(n²) 行为。需要双端队列用 collections.deque。
二、dict：哈希表，O(1) 查找的基石
dict 用开放寻址的哈希表实现。键必须是可哈希的（不可变对象，见对象模型入门）。
python
d = {"a": 1, "b": 2}
print(d["a"]) # O(1) 平均
"a" in d # O(1) 平均| 操作 | 复杂度 |
|---|---|
按键取值 d[k] | O(1) 平均 |
插入/更新 d[k]=v | O(1) 均摊 |
成员判断 k in d | O(1) 平均 |
| 遍历所有 key/value | O(n) |
性能视角：dict 的 O(1) 来自哈希——把 key 算出一个桶位置直接定位。但哈希表有内存开销（要预留空桶防冲突），且 key 的哈希要稳定。这和本站的缓存与哈希同源：都是"用空间换时间"。
三、set：只存键的 dict，去重与集合运算
set 底层和 dict 几乎一样，只是不存 value。它天生去重，成员判断也是 O(1)。
python
s = set([1, 1, 2, 3, 3]) # {1, 2, 3} 自动去重
print(2 in s) # O(1)
a = {1, 2, 3}; b = {2, 3, 4}
print(a & b) # {2, 3} 交集
print(a | b) # {1, 2, 3, 4} 并集最经典的优化：把 list 的成员判断换成 set。
python
# 慢：O(n*m)
hits = [x for x in big_list if x in allowed_list]
# 快：allowed 转 set 后 O(n)
allowed_set = set(allowed_list)
hits = [x for x in big_list if x in allowed_set]四、tuple：不可变的轻量序列
tuple 和 list 用法像，但不可变（见对象模型入门）。
python
t = (1, 2, 3)
# t[0] = 9 # TypeError: 'tuple' object does not support item assignment| 维度 | tuple | list |
|---|---|---|
| 可变性 | 不可变 | 可变 |
| 内存 | 略小（无扩容字段） | 略大 |
| 当 dict key | 可以 | 不可以 |
| 创建速度 | 略快 | 略慢 |
选型建议：数据不该被改、或要当字典 key、或作函数返回多值时，用 tuple/namedtuple（后者可读性更好）。
五、怎么选：一张决策表
| 你要什么 | 用 |
|---|---|
| 有序、可改、下标访问 | list |
| 有序、不可改、轻量/当 key | tuple |
| 键值映射、快速查 | dict |
| 去重、集合交并差 | set |
| 双端频繁增删 | collections.deque |
| 有序字典、首屏保序 | dict（3.7+ 已保序）/ OrderedDict |
| 计数 | collections.Counter |
| 按 key 排序的映射 | collections.defaultdict |
六、与本站性能主线的衔接
| 数据结构选择 | 本站对应 | 衔接文档 |
|---|---|---|
list 线性扫描 O(n) | 算法与复杂度 | 把成员判断换成 set 降维 |
dict/set 哈希 O(1) | 缓存与哈希 | 空间换时间的通用套路 |
deque 双端 | L2 数据结构 | 队列模型 |
| 内存开销差异 | L3 内存子系统 | 对象引用导致额外开销 |
七、常见坑
- 大列表做
in判断：O(n) 扫描，数据量大时换成set，复杂度直接掉到 O(1)。 - dict 键用可变对象：
list不能当 key，要先用tuple包一层。 - dict 遍历中删除：会抛
RuntimeError；应遍历list(d.keys())副本或推导式重建。 set元素不可哈希：set 里不能放 list/dict，需要包成 tuple。
一句话总结
list 是动态数组（下标快、查找慢），dict/set 是哈希表（查找 O(1)、吃内存），tuple 是不可变轻量序列；把成员判断从 list 换 set，是 Python 里性价比最高的一波优化。
继续：生成器、迭代器与装饰器 → GIL、多进程与 asyncio。