数据结构

你有 100 万个用户 ID，要反复回答”这个 ID 在不在里面”。存成 Python 列表，每次 x in lst 平均要比较 50 万次；存成 set，一次查询几乎是常数时间。数据是一样的，只是摆放方式不同，速度差了五个数量级。数据结构研究的就是这件事：为你最常做的操作，选择最合适的摆放方式。

前置：数据抽象与对象；复杂度记号见离散数学。

抽象与实现：先说清要什么操作

CS61B 的第一课是把”接口”和”实现”分开。抽象数据类型（ADT）只规定有哪些操作：一个 Set 要支持 add、contains、remove；一个优先队列要支持 insert 和 removeMin。至于底下用数组、链表、树还是哈希表，是实现的选择，不同的选择对应不同的性能。

Java 把这件事写进了语言：List<Integer> xs = new ArrayList<>(); 左边是接口，右边是实现，换成 LinkedList 其余代码不用改。（下面是 Java 示意，不运行）

// 示意：同一个接口，两种实现，性能特征完全不同
List<Integer> a = new ArrayList<>();   // get(i) O(1)，头部插入 O(n)
List<Integer> b = new LinkedList<>();  // get(i) O(n)，头部插入 O(1)

Java 还有一个初学者常踩的坑，与后面所有结构都有关：引用语义。除了 int、double 这 8 种基本类型，Java 变量里存的都是对象的地址。Node b = a; 不复制节点，只复制地址，于是 b.next = null 也改了 a 看到的节点。链表和树就是由这些地址串起来的。Python 的名字和对象也是同一种模型（见 Python 对象模型），下面的代码用 Python 写，概念完全通用。

数组与链表：两种最基本的摆放

数组把元素放在一段连续内存里。知道起始地址和下标，第 i 个元素的地址是 base + i * size，所以随机访问是 $O (1)$ 。代价是插入和删除：在中间插一个元素，后面的元素都要往后挪， $O (n)$ 。

链表让每个节点保存一个值和指向下一个节点的引用。在已知位置插入或删除只要改几个引用， $O (1)$ ；但想找第 i 个元素只能从头一个个走， $O (n)$ 。CS61B 用哨兵节点（sentinel）简化链表代码：在链表头放一个永远存在的假节点，空表和非空表就不用分情况处理。双向链表再加一个尾哨兵，两端的插入删除都是 $O (1)$ 。

数组有一个更根本的问题：长度固定。动态数组（Python list、Java ArrayList）的做法是：满了就申请一块更大的内存，把旧元素拷过去。关键在于扩多大。

如果每次只扩 1 格，插入 $n$ 个元素要拷贝 $1 + 2 + \dots + n = Θ (n^{2})$ 次。如果每次翻倍，拷贝次数是 $1 + 2 + 4 + \dots + n < 2 n$ ，平均到每次插入只有常数次。这叫均摊 $O (1)$ ：个别插入很贵，但贵的操作足够稀少，摊下来每次都便宜。

import sys
xs, last = [], sys.getsizeof([])
# 观察 CPython list 什么时候真正重新分配内存
for i in range(40):
    xs.append(i)
    size = sys.getsizeof(xs)
    if size != last:
        print(f"len={len(xs):3d}  bytes={size}")
        last = size

输出：

len=  1  bytes=88
len=  5  bytes=120
len=  9  bytes=184
len= 17  bytes=248
len= 25  bytes=312
len= 33  bytes=376

每次 bytes 跳变就是一次重新分配（每个槽 8 字节）。CPython 的规则大约是新容量 = n + n/8 + 小常数，小规模时看起来像每次多给 8 个槽，规模大了才接近 1.125 倍，比翻倍保守，但道理一样：只要按比例增长，均摊代价就是常数；按固定量增长，均摊代价就是线性的。

在数组和链表之上，栈（后进先出）和队列（先进先出）只是限制了操作的位置。栈用动态数组的尾部实现最自然，append 和 pop 都是均摊 $O (1)$ ；函数调用栈、括号匹配、DFS 都用它。队列在数组上需要环形缓冲区，或者用双向链表；Python 的 collections.deque 就是分块双向链表，BFS 用它。用 list.pop(0) 实现队列是常见的性能错误，那是 $O (n)$ 。

还有一个数组胜出的理由在复杂度里看不出来：缓存。数组连续存放，读一个元素时 CPU 会把附近的元素一起装进 cache line；链表的节点散落在堆上，每走一步都可能是一次 cache miss。实际测量中，遍历数组往往比遍历同样长度的链表快好几倍（见内存层次与缓存）。

停一下，检查理解单选

动态数组每次满了就把容量扩大为原来的 1.5 倍。连续 append n 个元素，总的拷贝次数是什么量级？

Θ(n^2)，因为每次扩容都要拷贝所有元素Θ(n)，均摊到每次 append 是常数Θ(n log n)，因为扩容发生了 log n 次Θ(1)，因为大部分 append 不需要扩容

哈希表：用计算代替查找

回到开头的问题：怎么让 contains 变成 $O (1)$ ？

一个荒唐但有启发的想法：如果 ID 都是 0 到 999999 之间的整数，开一个长度为 100 万的布尔数组，present[id] = True，查询就是一次数组访问。问题是键的范围可能极大（任意字符串），根本开不出这么大的数组。

哈希表的修正是：用一个哈希函数把任意键映射成一个小范围内的整数 h(key) % m，作为桶的下标。不同的键可能落进同一个桶（鸽巢原理保证这一定会发生，见离散数学），处理冲突有两种主流办法：

拉链法（separate chaining）：每个桶是一个链表，冲突的键都挂在上面。Java 的 HashMap 用它，桶里元素太多时还会把链表换成红黑树。
开放寻址：冲突了就按某种规则找下一个空位。CPython 的 dict 和 set 用它，元素连续存放对缓存更友好。

性能取决于负载因子 $α = n / m$ （元素数除以桶数）。哈希函数足够均匀时，拉链法每次操作期望 $O (1 + α)$ 。只要在 $α$ 超过阈值（比如 0.75）时把桶数翻倍并重新哈希所有元素， $α$ 始终有界，操作就是均摊期望 $O (1)$ ，和动态数组的论证是同一个套路。

import random, time
class ChainedHashSet:
    def __init__(self, m=8):
        self.buckets = [[] for _ in range(m)]; self.n = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def add(self, key):
        b = self._bucket(key)
        if key in b: return
        b.append(key); self.n += 1
        if self.n / len(self.buckets) > 0.75:  # 负载因子有界才能保证 O(1)
            old = [k for b in self.buckets for k in b]
            self.buckets = [[] for _ in range(2 * len(self.buckets))]
            for k in old: self._bucket(k).append(k)
    def __contains__(self, key):
        return key in self._bucket(key)
 
random.seed(0)
ids = random.sample(range(10**9), 100_000)
hs, lst = ChainedHashSet(), list(ids)
for x in ids: hs.add(x)
queries = random.sample(ids, 200)
t = time.perf_counter(); r1 = sum(q in hs for q in queries); t1 = time.perf_counter() - t
t = time.perf_counter(); r2 = sum(q in lst for q in queries); t2 = time.perf_counter() - t
print("桶数:", len(hs.buckets), " 最长的桶:", max(map(len, hs.buckets)))
print(f"hash set: {t1*1e3:.2f} ms   list: {t2*1e3:.1f} ms   结果一致: {r1 == r2}")

输出：

桶数: 262144  最长的桶: 6
hash set: 0.20 ms   list: 99.3 ms   结果一致: True

10 万个元素，最长的桶也只有个位数长度，哈希查询比线性扫描快了几个数量级。

哈希表有两条使用规则，违反了就会出诡异的 bug。第一，相等的对象必须有相同的哈希值。在 Java 里重写了 equals 却忘了重写 hashCode，两个”相等”的对象会落进不同的桶，contains 找不到。第二，键不能在放进去之后被修改，否则它的哈希值变了，却还待在旧桶里。这就是 Python 不允许 list 当字典键、只允许 tuple 这类不可变对象的原因。

哈希表的代价是无序：它回答不了”比 x 大的最小元素是什么”或”按顺序列出所有元素”。需要顺序，就需要树。

停一下，检查理解多选

一个 Java 类重写了 equals（按 id 字段比较），但没有重写 hashCode。把两个 id 相同的对象依次放入 HashSet，可能发生什么？

集合里出现两个"相等"的元素用一个新建的、id 相同的对象调用 contains，返回 false编译报错，因为 equals 和 hashCode 必须同时重写程序一定抛出异常

二叉搜索树：有序地快速查找

想要既快又有序，最自然的想法来自二分查找：有序数组上查找是 $O (lo g n)$ ，但插入要挪元素， $O (n)$ 。能不能把”二分”的结构直接用指针搭出来？

二叉搜索树（BST）的每个节点满足：左子树所有键都比它小，右子树所有键都比它大。查找从根出发，比当前节点小就往左，大就往右，每一步排除一棵子树。插入就是查找到空位后挂上新节点。中序遍历（左、根、右）按从小到大的顺序输出所有键，于是”有序”免费得到；求后继、范围查询也都沿着树走一条路径。

所有操作的代价都是树高 $h$ 。随机顺序插入时，期望高度是 $O (lo g n)$ 。但如果按已排序的顺序插入，每个新节点都挂在最右边，树退化成一条链， $h = n$ 。

import random
def insert(root, key):
    # 用 [key, left, right] 列表代替类，保持示例短小
    if root is None: return [key, None, None]
    i = 1 if key < root[0] else 2
    root[i] = insert(root[i], key)
    return root
def height(t):
    return 0 if t is None else 1 + max(height(t[1]), height(t[2]))
 
import sys; sys.setrecursionlimit(10000)
n = 2000
keys = list(range(n)); random.seed(1); random.shuffle(keys)
t_random = None
for k in keys: t_random = insert(t_random, k)
t_sorted = None
for k in range(n): t_sorted = insert(t_sorted, k)
print("随机顺序插入，高度:", height(t_random))
print("有序插入，高度:", height(t_sorted))

输出：

随机顺序插入，高度: 24
有序插入，高度: 2000

现实数据经常是有序或接近有序的（时间戳、自增 ID），所以普通 BST 不可靠。需要一种能自己保持平衡的树。

2-3 树的想法是让节点变”胖”：一个节点可以放 1 个键（2 个孩子）或 2 个键（3 个孩子）。插入时新键总是先放进叶子；如果叶子变成 3 个键，就把中间的键往上推给父节点，自己分裂成两个。分裂可能一路传到根，根分裂时树高加 1。注意树只会从根长高，所以所有叶子永远在同一深度，树高被严格控制在 $O (lo g n)$ 。

2-3 树概念清晰但实现繁琐（节点类型不统一）。左倾红黑树（LLRB）是它的二叉编码：把 3-节点拆成两个普通节点，中间用一条”红色”的左链接相连。红黑树和 2-3 树一一对应，于是所有操作只需要普通 BST 的代码，加上三种局部修正：左旋、右旋、颜色翻转。Java 的 TreeMap、C++ 的 std::map 都是红黑树。

把”胖节点”的想法推到极致，让一个节点装几百个键，就得到 B 树：树高只有三四层，每层一次磁盘读，这是数据库索引的基础（见数据库系统）。

停一下，检查理解单选

依次向一棵空的普通 BST 插入 1, 2, 3, ..., 1000，然后查找 1000。需要比较多少次？

约 10 次，因为 BST 的查找是 O(log n)约 1000 次，因为树退化成了一条链约 500 次，平均情况1 次，因为最后插入的元素在根上

堆：只关心最小的那个

有些场景不需要完整的顺序，只需要反复取出”当前最小（最紧急）的那个”：操作系统调度进程，Dijkstra 算法取下一个最近的顶点，合并 k 个有序列表，推理服务按优先级取请求。这就是优先队列 ADT：insert 和 removeMin。

用有序数组实现，removeMin 是 $O (1)$ 但 insert 是 $O (n)$ ；用平衡树两者都是 $O (lo g n)$ ，但杀鸡用了牛刀。二叉堆用更弱的约束换来更简单的实现：每个节点比它的孩子小（堆序），树是完全二叉树（除最后一层外全满，最后一层从左往右排）。

完全二叉树可以直接存进数组，不需要指针：下标 i 的孩子在 2i+1 和 2i+2，父亲在 (i-1)//2。

insert：放到数组末尾，然后不断和父亲比较，比父亲小就交换（上浮）， $O (lo g n)$ 。
removeMin：取走根，把最后一个元素移到根，然后不断和较小的孩子比较，比它大就交换（下沉）， $O (lo g n)$ 。

import heapq, random
class MinHeap:
    def __init__(self): self.a = []
    def push(self, x):
        a = self.a; a.append(x); i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:
            a[(i - 1) // 2], a[i] = a[i], a[(i - 1) // 2]; i = (i - 1) // 2
    def pop(self):
        a = self.a; top = a[0]; last = a.pop()
        if a:
            a[0] = last; i = 0
            while True:
                c = 2 * i + 1
                if c >= len(a): break
                if c + 1 < len(a) and a[c + 1] < a[c]: c += 1  # 和较小的孩子换才能保持堆序
                if a[i] <= a[c]: break
                a[i], a[c] = a[c], a[i]; i = c
        return top
 
random.seed(2); data = [random.randint(0, 99) for _ in range(12)]
h = MinHeap()
for x in data: h.push(x)
print("数组布局:", h.a)
print("依次弹出:", [h.pop() for _ in range(len(data))])
print("与 heapq 一致:", heapq.nsmallest(12, data) == sorted(data))

输出：

数组布局: [7, 11, 10, 32, 21, 77, 85, 46, 39, 77, 27, 94]
依次弹出: [7, 10, 11, 21, 27, 32, 39, 46, 77, 77, 85, 94]
与 heapq 一致: True

数组布局看起来并不有序，只保证每个父亲不大于孩子，但依次弹出就是排好序的序列，这就是堆排序。从一个无序数组原地建堆只需 $O (n)$ （从最后一个非叶子往前依次下沉，大部分节点都在底层，下沉距离很短），比逐个插入的 $O (n lo g n)$ 好。Python 的 heapq 就是这样一个数组上的最小堆。

并查集：动态的连通性

另一类问题是关于分组的：网络里不断有新连接加入，随时问”这两台机器连通吗”；Kruskal 算法加边时问”这条边会不会形成环”；图像里把相邻同色像素合成区域。需要两个操作：union(a, b) 合并两组，find(a) 返回 a 所在组的代表。

最朴素的做法是给每个元素记一个组号，union 时把一组的所有元素改号， $O (n)$ 。并查集（disjoint set union）换一种表示：每个元素指向一个父亲，根就是组的代表，find 沿父指针走到根，union 把一棵树的根挂到另一棵的根下。

这样 union 很快了，但树可能长成一条长链，find 变成 $O (n)$ 。两个修正：

按大小合并：总是把小树挂到大树下。一个元素所在的树每次被挂到别人下面，大小至少翻倍，所以深度不超过 $lo g_{2} n$ 。
路径压缩：find 时把沿途所有节点直接指向根，下次就一步到位。

两者结合后， $m$ 次操作的总代价是 $O (m α (n))$ ， $α$ 是反 Ackermann 函数，对任何现实的 $n$ 都不超过 5，实践中可以当作常数。

import random
class DSU:
    def __init__(self, n):
        self.parent = list(range(n)); self.size = [1] * n
    def find(self, x):
        root = x
        while self.parent[root] != root: root = self.parent[root]
        while self.parent[x] != root:  # 路径压缩：把沿途节点直接挂到根上
            self.parent[x], x = root, self.parent[x]
        return root
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.size[ra] < self.size[rb]: ra, rb = rb, ra
        self.parent[rb] = ra; self.size[ra] += self.size[rb]
        return True
 
def max_depth(d):
    def depth(x):
        k = 0
        while d.parent[x] != x: x = d.parent[x]; k += 1
        return k
    return max(depth(x) for x in range(len(d.parent)))
 
n = 100_000; random.seed(3)
d = DSU(n)
for _ in range(n): d.union(random.randrange(n), random.randrange(n))
groups = len({d.find(x) for x in range(n)})
print("连通分量数:", groups, " 压缩后最大深度:", max_depth(d))

输出：

连通分量数: 16128  压缩后最大深度: 1

停一下，检查理解单选

并查集只用"按大小合并"、不用路径压缩时，为什么任意元素的深度不超过 log2 n？

因为每次 union 都会重建整棵树使其平衡因为元素的深度每加 1，它所在树的大小至少翻倍，而树的大小不超过 n因为 find 会顺便把路径压平因为并查集本质上是一棵平衡二叉搜索树

图的表示：选择决定了算法的代价

最后，前面所有的结构在图上汇合。图的概念见离散数学，这里只关心怎么存。

邻接矩阵： $∣ V ∣ \times ∣ V ∣$ 的布尔矩阵，adj[u][v] 表示是否有边。判断两点是否相邻 $O (1)$ ，但空间是 $Θ (V^{2})$ ，遍历一个顶点的邻居也要扫一整行 $Θ (V)$ 。

邻接表：每个顶点存一个邻居列表。空间 $Θ (V + E)$ ，遍历邻居的代价正比于邻居数。现实中的图几乎都是稀疏的：一个社交网络有十亿用户，但每人只有几百个好友，邻接矩阵需要 $1 0^{18}$ 个格子，邻接表只需要千亿级。

操作	邻接矩阵	邻接表
空间	$Θ (V^{2})$	$Θ (V + E)$
判断 `(u, v)` 是否有边	$O (1)$	$O (de g u)$
遍历 `u` 的所有邻居	$Θ (V)$	$Θ (de g u)$
遍历整个图	$Θ (V^{2})$	$Θ (V + E)$

于是 BFS 和 DFS 在邻接表上是 $O (V + E)$ ，在邻接矩阵上是 $O (V^{2})$ 。图算法的复杂度几乎都依赖表示方式。一个算法用到哪些数据结构，也决定了它的速度：BFS 用队列，DFS 用栈（或递归），Dijkstra 用堆，Kruskal 用并查集，Prim 用堆。这些算法本身在算法设计里讲。

from collections import deque
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]
n = 7
adj = [[] for _ in range(n)]
for u, v in edges: adj[u].append(v); adj[v].append(u)
def bfs(s):
    dist = [None] * n; dist[s] = 0; q = deque([s])  # deque 让出队是 O(1)
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] is None: dist[v] = dist[u] + 1; q.append(v)
    return dist
print("邻接表:", adj)
print("从 0 出发的 BFS 距离:", bfs(0))

输出：

邻接表: [[1, 2], [0, 3], [0, 3], [1, 2, 4], [3], [6], [5]]
从 0 出发的 BFS 距离: [0, 1, 1, 2, 3, None, None]

顶点 5 和 6 与 0 不连通，距离保持 None。

停一下，检查理解多选

下面哪些选择是合理的？

存一个有 1000 万个顶点、平均度为 20 的道路网，用邻接表实现 Dijkstra 时，用堆维护"当前距离最小的未处理顶点"实现 BFS 时用 Python list 的 pop(0) 作为出队操作判断 Kruskal 算法里新加的边是否成环，用并查集

记住这三件事

先定操作再选结构：数组随机访问快、链表局部插删快、哈希表查找快但无序、平衡树有序且对数时间、堆只管最小值。
按比例扩容带来均摊 $O (1)$ ；负载因子有界才有哈希表的 $O (1)$ ；树高有界才有 BST 的 $O (lo g n)$ 。
图用邻接表还是邻接矩阵，决定了图算法的复杂度；经典图算法就是”图 + 队列/栈/堆/并查集”。

CS 与 LLM 学习知识库

探索

数据结构

抽象与实现：先说清要什么操作

数组与链表：两种最基本的摆放

哈希表：用计算代替查找

二叉搜索树：有序地快速查找

堆：只关心最小的那个

并查集：动态的连通性

图的表示：选择决定了算法的代价

记住这三件事

延伸阅读

目录

反向链接