Python 与数据结构

约 2974 字大约 10 分钟

Python 与数据结构

数据结构课讲抽象数据类型；Python 把它们做成了内置对象。会用 list、dict 只是第一步，知道它们背后分别是动态数组、紧凑哈希表、块状链表和二叉堆，才能解释「为什么尾部追加快、头部插入慢」「为什么 dict 有序」「为什么 set 去重快」。

1. 一张总表

抽象数据结构	Python 载体	底层实现	关键复杂度	典型场景
动态数组	`list`	`PyListObject` + 连续的 `PyObject*` 数组	索引 O(1)，尾部追加均摊 O(1)，中间插入/删除 O(n)	结果集、栈、DP 数组
定长序列	`tuple`、`namedtuple`	`PyTupleObject`，创建后长度固定	索引 O(1)，不可变	坐标、返回值、字典键
哈希表	`dict`	紧凑哈希表：稀疏 `indices` + 密集 `entries`	查找/插入/删除平均 O(1)	配置、缓存、计数
哈希集合	`set`、`frozenset`	开放寻址哈希表，只存键	成员判断平均 O(1)	去重、集合运算
双端队列	`collections.deque`	固定大小块组成的双向链表	两端增删 O(1)，中间索引 O(n)	BFS、滑动窗口
优先队列	`heapq` + `list`	0-based 二叉堆（数组存储）	堆顶 O(1)，push/pop O(log n)，heapify O(n)	Top K、Dijkstra
链表	自定义 `Node`	对象 + `next` 引用	已知位置插入 O(1)，查找 O(n)	LRU、链表类题目
树 / 图	自定义 `Node`、`dict[list]`	对象引用 / 邻接表	取决于遍历方式	文件树、依赖图
并查集	`list` / `dict` 存 parent	数组 + 路径压缩 + 按秩合并	近似 O(1)	连通性、账户合并

两个常被忽略的事实：

Python 没有内置链表和树，因为「对象 + 引用」就能拼出来；但 deque 内部确实是链式结构，只是它按块组织，不是教科书里的单节点链表。
dict、set 的 O(1) 是平均复杂度，遇到严重哈希冲突会退化；list 的 O(1) 索引则依赖「连续存放引用」这个前提。

2. `list`：动态数组

2.1 内存布局

CPython 的 list 不是「一串元素」，而是「一个对象头 + 一个指向指针数组的入口」：

PyListObject
  ob_refcnt        引用计数
  ob_type          类型指针
  ob_size = 3      实际元素个数
  allocated = 4    已分配的槽位数
  ob_item ────────► [ PyObject* ][ PyObject* ][ PyObject* ][ 空闲 ]
                        │            │            │
                        ▼            ▼            ▼
                      int 1        int 2        int 3

每个槽位放的是 PyObject*，不是元素本身。所以 [1, "a", [2]] 合法：三个槽位指向三个类型完全不同的对象。连续的是引用，不是对象。

import sys

a = [1, 2, 3]
print(sys.getsizeof(a))   # 本机 3.13：88 = 40 字节 PyListObject + 16 字节 GC 头 + 4 槽 × 8 字节
print(id(a))              # 140...，就是 PyListObject 的地址
a.append(4)
print(id(a))              # 不变：原地扩容，对象没有搬家

2.2 为什么尾部快、头部慢

append() 发现容量够，就直接写下一个槽位；容量不够，才按比例申请更大的数组，把旧引用搬过去。按比例扩容让 n 次追加的总搬移量保持在 O(n)，所以均摊 O(1)，但单次触发扩容仍可能是 O(n)。

pop(0)、insert(0, x) 则不同：它们要把后面所有引用依次左移或右移，n 个元素就是 O(n)。这就是「用 list 当队列」会慢的原因。

# 栈：尾部进、尾部出，都是 O(1)
stack = []
stack.append(1)
stack.pop()

# 队列：不要这样写，pop(0) 是 O(n)
queue = []
queue.append(1)
queue.pop(0)          # 后面所有元素都要往前挪

2.3 切片与浅拷贝

切片 a[:] 会创建一个新的外层 list，但只复制引用，不复制引用指向的对象：

a = [[1], [2]]
b = a[:]
b.append([3])         # 只影响 b
b[0].append(99)       # a[0] 也变了：b[0] 和 a[0] 是同一个列表

二维列表初始化是同一个坑：

# 错误：三行指向同一个内层列表
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix)         # [[1,0,0], [1,0,0], [1,0,0]]

# 正确：每一行独立创建
matrix = [[0] * 3 for _ in range(3)]

3. `dict` 与 `set`：哈希表

3.1 `dict` 的紧凑布局

Python 3.6 起，dict 把「索引」和「真正的键值条目」分开存：

dk_indices（稀疏）: [ 1, -1, 0, -1, 2, -1, -1, -1 ]
                       │            │
                       ▼            ▼
dk_entries（密集）:  [ (hash, key, value), (hash, key, value), ... ]

indices 只存「槽位 → entries 下标」，空槽是 -1。
entries 按插入顺序追加，所以遍历 dict 得到的就是插入顺序。
删除只把 indices 标记为 DUMMY、把 entry 的 key/value 置空；entry 槽位不会立刻复用，删除也不会自动收缩。只有扩容或显式重建 dict 时才压缩。

这解释了三个常见现象：

dict 在 3.7+ 保证插入顺序，但它不是排序，只是记住你插入的先后。
dict 的内存比「每个键值对单独一个节点」的链表实现更紧凑。
频繁删除大量键后，表可能变得稀疏，重新构建一个 dict 有时反而更省内存。

set 的布局和 dict 不同。 set 不是「去掉 value 的紧凑 dict」；CPython 的 PySetObject 用一张 setentry 表，每项存 key + hash，配合 used/fill/mask 做开放寻址，没有 dict 的 indices + entries 分离。它只存键，迭代顺序由哈希决定，不保证顺序；frozenset 不可变、可哈希，可以做 dict 的键。

3.2 哈希与相等

dict/set 的键必须满足：

可哈希：hash(obj) 在生命周期内稳定；
可比较：__eq__ 能判断两个键是否相等；
二者一致：a == b 时必须有 hash(a) == hash(b)。

print(hash(1) == hash(1.0) == hash(True))   # True
d = {1: "a", 1.0: "b", True: "c"}
print(d)                                    # {1: 'c'}，三个键被当成同一个

list、dict、set 本身不可哈希，不能做 dict 的键；tuple 只有在所有元素都可哈希时才可哈希。自定义对象默认按 id() 哈希，一旦重写 __eq__ 而没有重写 __hash__，就会变成不可哈希。

3.3 冲突与退化

哈希冲突用开放寻址处理：算出一个槽位，被占了就按扰动序列继续找。装载因子过高时扩容并重新散列。平均 O(1) 的前提是哈希函数把键分散得足够均匀；如果所有键都落到同一个槽，查找就退化成 O(n)。

3.4 遍历时不要改容器

d = {"a": 1, "b": 2}
for k in d:
    del d[k]          # RuntimeError: dictionary changed size during iteration

需要删除时先复制一份键：

for k in list(d):
    if k == "a":
        del d[k]

3.5 应用开发中的高频用法

from collections import Counter, defaultdict

# 计数
cnt = Counter("abracadabra")
print(cnt.most_common(2))          # [('a', 5), ('b', 2)]

# 分组
groups = defaultdict(list)
for word in ["apple", "avocado", "banana"]:
    groups[word[0]].append(word)

# 去重且保序
seen = set()
unique = [x for x in [3, 1, 3, 2, 1] if not (x in seen or seen.add(x))]

# LRU：OrderedDict 的 move_to_end + popitem(last=False)
from collections import OrderedDict
cache = OrderedDict()
cache["a"] = 1
cache.move_to_end("a")
cache.popitem(last=False)          # 淘汰最久未使用

4. `deque`：块状双向链表

deque 不是「每个元素一个节点」的纯链表，而是「固定大小的块 + 块之间双向链接」：

block <──> block <──> block
[64 个槽]  [64 个槽]  [64 个槽]

两端 append/appendleft/pop/popleft 都是 O(1)；
中间插入、按下标访问是 O(n)，因为要先走到对应块；
maxlen 让它在满时自动从另一端淘汰；底层仍是块状双向链表，不是环形缓冲区。

from collections import deque

q = deque([1, 2, 3], maxlen=3)
q.append(4)            # 1 被自动挤掉
print(q)               # deque([2, 3, 4], maxlen=3)

q.popleft()            # O(1)

应用：

BFS 的待访问队列；
滑动窗口最大值（单调递减 deque）；
单机生产者-消费者（多线程用 queue.Queue，它内部就是 deque + 条件变量）。

注意：deque 不支持切片；d[500] 这种中间索引是 O(n)；转成 list 会复制一份。

5. `heapq`：数组里的二叉堆

heapq 不提供独立的堆对象，而是直接操作一个 list，把它维护成 0-based 的完全二叉树：

索引:      0
         /   \
        1     2
       / \   / \
      3   4 5   6

父 → 子：left = 2*i + 1, right = 2*i + 2
子 → 父：parent = (i - 1) // 2

heapify(a)：原地建堆，O(n)；
heappush / heappop：O(log n)；
heappushpop(h, x)：先 push 再 pop，返回最小值；空堆也可用；
heapreplace(h, x)：先 pop 再 push，返回最小值；堆不能为空，否则 IndexError；
nlargest(k, it) / nsmallest(k, it)：O(n log k)。

import heapq

# Top K：比 sorted 全排序更省
nums = [5, 1, 9, 3, 7]
print(heapq.nlargest(2, nums))     # [9, 7]

# 大顶堆：Python 只有小顶堆，取负模拟
max_heap = []
for x in [5, 1, 9]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))    # 9

# 多键排序：元组按元素依次比较
heap = []
heapq.heappush(heap, (2, "b"))
heapq.heappush(heap, (1, "a"))
print(heapq.heappop(heap))         # (1, 'a')

两个坑：

堆只保证堆顶最小，不保证整个列表有序。需要完整顺序时用 sorted。
元组里如果有不可比较的对象，会抛 TypeError；常用「计数器」做第二键，避免比较业务对象。

6. 选型决策

需要按 key 快速查找？           → dict
需要去重 / 交并差？             → set / frozenset
需要两端增删？                  → deque
需要每次取最小 / 最大？          → heapq
需要按下标随机访问、尾部追加？    → list
需要不可变记录 / 字典键？        → tuple / namedtuple
需要紧凑的数值数组？             → array.array / numpy.ndarray
需要已知节点间的前后关系？        → 自定义 Node
需要连通性合并与查询？            → 并查集（list/dict + 路径压缩）

7. 应用开发中的组合

场景	组合	原因
API 请求去重	`set` + `dict`	`set` 判重 O(1)，`dict` 存结果
LRU 缓存	`OrderedDict` 或 `dict` + 双向链表	命中后移到尾部，淘汰头部
任务队列（单机）	`deque`	两端 O(1)，不需要线程安全
任务队列（多线程）	`queue.Queue`	`deque` + 锁 + 条件变量
Top K / 排行榜	`heapq.nlargest`	只维护 k 个元素，O(n log k)
邻接表	`defaultdict(list)`	稀疏图比二维矩阵省内存
账户合并 / 连通分量	并查集	近似 O(1) 合并与查询
时间序列	`array.array` / `numpy.ndarray`	连续数值存储，避免每个元素一个对象

8. 常见坑

可变默认参数：def f(x, acc=[]) 的 acc 只创建一次，多次调用共享同一个列表。
[[0] * n] * m：m 行指向同一个内层列表。
遍历时修改 dict/set：会抛 RuntimeError，先复制键。
用 list 做 dict 的键：不可哈希，直接 TypeError。
在 list 里做成员判断：x in list 是 O(n)；频繁判断先转 set。
浅拷贝当深拷贝：copy()、[:]、list() 都只复制第一层。
deque 当随机访问数组：中间索引 O(n)，需要下标访问就用 list。
大顶堆忘记取负：heapq 只有小顶堆。

9. 动手实验

import sys
import timeit
import heapq

# 1. list 的内存与扩容
a = []
for i in range(5):
    a.append(i)
    print(len(a), sys.getsizeof(a))

# 2. 尾部追加 vs 头部插入
print(timeit.timeit("a.append(0)", setup="a=list(range(10000))", number=10000))
print(timeit.timeit("a.insert(0, 0)", setup="a=list(range(10000))", number=10000))

# 3. list 查找 vs set 查找
setup = "a=list(range(10000)); s=set(a)"
print(timeit.timeit("9999 in a", setup=setup, number=10000))
print(timeit.timeit("9999 in s", setup=setup, number=10000))

# 4. heapify 是 O(n)，逐个 push 是 O(n log n)
nums = list(range(10000))
print(timeit.timeit("heapq.heapify(nums)", setup="import heapq; nums=list(range(10000))", number=100))
print(timeit.timeit(
    "h=[]\nfor x in nums: heapq.heappush(h, x)",
    setup="import heapq; nums=list(range(10000))",
    number=100,
))

本机 3.13 的参考结论：

list 的 append 比 insert(0, ...) 快两三个数量级；
set 的成员判断比 list 快几个数量级；
heapify 比逐个 heappush 建堆快，因为前者是 O(n)。

10. 小结

list 是动态数组：连续的是引用，不是对象；尾部快、头部慢。
dict/set 是哈希表：平均 O(1) 的前提是哈希均匀；dict 记住插入顺序，但不是排序。
deque 是块状双向链表：两端 O(1)，中间 O(n)。
heapq 是数组里的二叉堆：只保证堆顶最小，不保证整体有序。
选型的本质不是背复杂度，而是先问「数据怎么访问、怎么修改」，再找匹配的底层布局。