A.2 数据结构基础 数组、链表、树、图与哈希

1.数据结构到底是什么

说起来，前面这几十篇我们一直在和神经网络打交道，张量、矩阵、计算图这些词翻来覆去地用。可这些东西再往底层看，其实就是数据结构。数据结构说白了，就是数据在内存里怎么摆放、怎么组织的一套规矩。同一批数据，组织方式不同，读写起来的快慢和开销能差出好几个数量级。我们在 1.7 节专门讲过算法复杂度和大 O 记号，$O(N)$、$O(N^2)$ 这类记号刻画的是随输入规模 $N$（比如元素个数）增长时开销增长的大致量级，$O(N^2)$ 就是规模翻倍时开销变成原来的四倍。这些复杂度从哪里来呢，很大程度上就来自所选的数据结构。

我们今天就从头梳理一遍最基础的几类数据结构，看看它们各自擅长什么、又在哪里吃亏。掌握这些之后，再去看PyTorch、TensorFlow那边的源码，会发现里头到处都是它们的影子。

2.数组与链表：最朴素的两种线性结构

最简单的数据结构是线性表，也就是把一组元素一个挨一个地排成一列。线性表有两种最经典的实现方式，一种叫数组，一种叫链表。

数组说的是在内存里划出一段连续的空间，把元素一个挨一个地放进去。每个元素占据同样大小的格子，下标从 $0$ 开始编号（$0$ 表示第一个元素的位置），下标 $i$ 表示第 $i+1$ 个元素，$i$ 只是个整数编号。因为内存连续，只要知道数组开头的地址，再算一下偏移，就能一步跳到任意一个下标的位置。所以数组的随机访问特别快，复杂度是 $O(1)$，$O(1)$ 表示开销不随输入规模变化、是个常数。小明在课上写过一段找出数组里第几万个元素的代码，几乎眨眼就返回，靠的就是这个特性。

数组也有它难受的地方。要在中间插一个元素，后面所有元素都得往后挪一格，删除也同理，这种挪动平均要动一半左右的元素，复杂度是 $O(N)$。打个比方，数组像戏院里一排连号座位，你想找5号位直接走过去就行，可要是中间突然有人要插队坐下，后面所有人都得起身挪一位，麻烦得很。

链表就完全是另一套思路。链表里的元素在内存里是零散放的，每个元素（叫节点）里除了存数据，还存着一个指向下一个节点的指针。指针说白了就是一个地址，告诉程序下一个节点放在内存的什么地方。这样要插入或删除一个节点，只要改一改前后两个指针的指向就行，不用大动干戈地挪数据，复杂度是 $O(1)$。代价是访问第 $i$ 个节点不能直接跳过去，得从头一个一个顺着指针找，复杂度是 $O(N)$。链表有点像寻宝游戏里那种线索套线索的玩法，每张纸条告诉你下一张藏在哪里，你想直接跳到第十张是没办法的，得一张一张找下去。

这两种结构各有各的场子。需要频繁按下标读取、很少改动的地方，用数组最划算。需要频繁在中间插入删除的，链表更合适。工程里前者更常见，因为CPU缓存对连续内存特别友好，数组的实际访问速度往往比理论复杂度还占便宜。

3.栈和队列：两种受限的线性表

在数组或链表的基础上加点限制，就得到两种特别有用的结构。

一种叫栈，规矩是后进先出。可以往里放元素（这动作叫入栈），也可以从里面取出来（叫出栈），但只能从同一端操作，放进去的最后一个最先被取出来。栈有点像食堂里叠盘子，你只能往顶上放，也只能从顶上拿，最底下那块盘子想拿出来得先把上面的全搬走。栈在算法里出场频率极高，比如深度优先搜索（DFS），DFS在A.3 节里我们详细用过，它就是顺着一条路走到底、走不通了再退回来换条路，这种退回来的动作正好是后进先出，所以DFS通常就用一个栈来实现。

另一种叫队列，规矩是先进先出。一头进、另一头出，先放进去的先被取出来。队列就像超市排队结账，先排队的先付钱走人。广度优先搜索（BFS）就靠队列来组织，一层一层地往外扩展，先把距离起点近的节点都处理完，再处理下一圈。BFS在A.3 节里我们也提到过，那篇讲搜索算法的朋友不妨回头对照一下。

栈和队列看着简单，却是很多复杂算法的骨架。我自己刚学算法的时候，总觉得这俩东西过于平凡没什么意思，后来动手写了一遍表达式求值（用栈处理括号匹配和运算符优先级），才慢慢体会到它们的妙处。一个小小的栈，就能把嵌套结构理得服服帖帖。

4.树：层层分叉的结构

线性结构讲完了，我们再往上一层，说说树。

树是一种分叉的结构。一棵树有一个根节点（最顶上的那个节点），根节点下面连着若干个子节点，每个子节点又可以有自己的子节点，这样层层往下分叉，直到没有子节点的节点，叫叶子节点。我们用层来描述从根到某节点的距离，根节点在第 $0$ 层（也有的书从 $1$ 算起，全文统一即可），它的子节点在第 $1$ 层，整个层数的取大值叫树的高度。树天然适合表达有层级关系的东西，公司的组织架构、文件的目录结构，都是树。

最常用的是二叉树，每个节点最多有两个子节点。二叉树里又有一种叫二叉搜索树（BST），BST的规矩是：对任意一个节点，它左子树里所有节点的值都比它小，右子树里所有节点的值都比它大。这么一来，查找一个值的时候每次比较都能排除掉一半左右，平均复杂度是 $O(\log N)$，$\log N$ 表示以 $2$ 为底 $N$ 的对数，大致意味着每翻一倍才多走一步。我们之前在2.8 节讲决策树的时候，决策树也是一种树，只是它分叉的依据是特征阈值的切分，而不是数值大小比较，可底层结构是一回事。

二叉搜索树只有在平衡的时候才有 $O(\log N)$ 的查找效率。要是不加约束地往里塞数据，它可能退化成一条链，查找就回到 $O(N)$ 了。所以工程里常用自平衡的二叉搜索树（比如AVL树、红黑树），它们在插入删除时会自动调整形状，把树的高度压在 $O(\log N)$ 附近。C++标准库的map底层是红黑树，而Redis里的有序集合底层是跳表加哈希表。

树还有几个常用的变体。堆是一种特殊的二叉树，常用来实现优先队列，堆顶总是当前最大的（或最小的）元素，我们做top-k问题、做任务调度的时候用得很多。再比如字典树（Trie），把字符串按公共前缀组织成一棵树，做自动补全和词频统计都靠它。我记得之前看过一本讲搜索引擎的书，里头花了一整章讲怎么用Trie做搜索词提示，那个章节读完之后我对树的认识一下子就立体起来了。

5.图：节点加边

再放开一些，就是图了。图由一组节点（也叫顶点）和一组边组成，边连接两个节点，表示它们之间有关系。A.1 节我们刚详细聊过图，这里只从数据结构的角度说一句：图到底怎么在内存里存下来。

最常用的两种存法是邻接矩阵和邻接表。邻接矩阵是一个 $V \times V$ 的二维数组，$V$ 表示图里节点的个数，矩阵第 $i$ 行第 $j$ 列的值表示节点 $i$ 到节点 $j$ 之间有没有边（或者边的权重是多少）。邻接矩阵的好处是查两个节点之间有没有直接连接一步到位，复杂度是 $O(1)$，可坏处也明显，占用空间是 $O(V^2)$，节点一多就吃不消，尤其是稀疏图（边数远少于 $V^2$ 的图）浪费得厉害。

邻接表就省多了。它给每个节点配一个列表，列表里存这个节点直接连到的所有邻居。整体占用空间是 $O(V+E)$，$E$ 表示边的条数。对于稀疏图，邻接表几乎是不二之选。代价是查两个节点之间有没有直接连边，平均得在邻居列表里找一遍，复杂度是 $O(d)$，$d$ 表示相关节点的度数（某节点的度数就是与它相连的边的条数）。

工程里大多数图算法都基于邻接表来实现，A.1 节讲图算法的时候用的就是这种结构。社交网络里上亿用户的好友关系、网页之间的链接图，如果硬上邻接矩阵，内存当场就爆了，邻接表才能撑得住。

6.哈希表：工程里出镜率最高的结构

最后说一个特别顶用的结构，哈希表。

哈希表的核心思想是用一个哈希函数 $h$，$h$ 是一个把键映射到整数下标的函数，把任意一个键（字符串、数字、对象都行）经过 $h$ 算成一个整数，再落到一段连续数组里的某个位置。理想情况下，查找一个键只要算一次哈希、再访问一次数组，平均复杂度接近 $O(1)$，比树还快。

这听起来美好，可麻烦出在冲突上。不同的键有可能被 $h$ 算到同一个位置，这就叫哈希冲突。冲突不可避免（键的可能取值无穷多，位置总数有限），只能想办法处理。最常用的两种处理办法，一种叫链地址法，每个位置挂一个链表，冲突的键都追加到链表里。另一种叫开放地址法，冲突了就按某种规则另找一个空位置放进去。

哈希表的实际性能高度依赖哈希函数的设计和负载因子。负载因子记作 $\alpha$，$\alpha$ 定义为已存元素数除以数组容量，$\alpha$ 越大越容易冲突。一旦冲突严重，平均查找复杂度就从 $O(1)$ 退化到接近 $O(N)$。所以哈希表会在负载因子超过某个阈值（比如 $0.75$）时主动扩容，把所有元素重新哈希到更大的数组里。小张之前写一个缓存模块，哈希函数随便挑了一个分布很差的家伙，结果冲突扎堆，性能曲线掉得跟滑梯似的，调了一周才发现根因在哈希函数身上。

哈希表在工程里出镜率极高。Python里的dict和set、Java里的HashMap、C++里的unordered_map，底层都是哈希表。深度学习框架里，参数表、超参配置、数据集样本索引，绝大多数也都是用哈希表来组织的。

7.回到深度学习

说了这么多数据结构，它们和深度学习到底有什么关系呢，其实关系密切得很。

第一，张量本质上就是多维数组。一维张量是向量，二维张量是矩阵，更高维的张量也只是数组的层层嵌套。我们在PyTorch里写的torch.Tensor，底层就是一段连续内存里的浮点数数组，外加一些形状和步长信息。所以前面讲数组时提到的连续内存、缓存友好，对张量同样适用。GPU之所以能把矩阵乘法跑得飞快，正是因为张量是一段连续的、规则的数据，GPU可以大批量并行地去读它。

第二，深度学习框架用计算图来组织运算。计算图是一个有向无环图（DAG），DAG就是没有环的有向图，节点表示一次运算（比如矩阵乘、激活函数），边表示数据的流动方向。框架在背后做的事，其实就是对这个DAG做拓扑排序（拓扑排序是一种把图中节点按依赖关系排成线性序列的算法，前驱节点必须排在后继节点之前），然后按这个顺序执行计算。我们之前讲反向传播的时候，本质上也是沿着计算图从输出端往输入端走，把每个节点的梯度算出来。

第三，批处理、数据加载、采样都离不开这些结构。DataLoader内部要管理一个数据集索引（通常是数组），按批量大小切片取出一段，再通过一个采样器决定取哪些样本。多进程加载时还要用队列在生产者和消费者之间传递数据。分布式训练里协调各张显卡，又常常用到树形的AllReduce结构，把梯度一层层归约起来。

我之前翻过一本讲程序员成长小说，里头有句话大意是数据结构是程序员的内功，招式可以现学，内功得慢慢练。深度学习这一行虽然看着新，可一旦往下挖，挖到的还是这些老朋友。把这些基础打扎实，再去看论文、去看源码，会有一种豁然开朗的感觉。

练习

Q1. 数组和链表在"随机访问第 $i$ 个元素"和"中间插入/删除"这两种操作上，时间复杂度分别是什么？

数组随机访问第 $i$ 个元素是 $O(1)$（内存连续、算偏移一步跳过去），但中间插入/删除是 $O(N)$（后面所有元素都得挪一格）。链表正好反过来：访问第 $i$ 个元素是 $O(N)$（得从头顺着指针一个个找），但中间插入/删除是 $O(1)$（只要改前后两个指针的指向）。所以按下标频繁读取用数组，频繁中间增删用链表，工程里前者更常见（CPU缓存对连续内存友好）。

Q2. 栈和队列各遵循什么规矩？分别适合实现哪种搜索算法？

栈是"后进先出"（LIFO），只能从同一端入栈出栈，放进去的最后一个最先被取出，适合实现深度优先搜索（DFS）——顺着一条路走到底、走不通再退回来，这种"退回来"正好是后进先出。队列是"先进先出"（FIFO），一头进另一头出，先放进去的先被取出，适合实现广度优先搜索（BFS）——一层一层往外扩，先把离起点近的节点处理完再处理下一圈。

Q3. 易错点：哈希表平均查找是 $O(1)$，那是不是任何情况下都这么快？

不是，$O(1)$ 是平均情况，最坏情况会退化到接近 $O(N)$。哈希表的实际性能高度依赖哈希函数设计和负载因子 $\alpha$（已存元素数除以数组容量）。$\alpha$ 越大越容易冲突，一旦冲突严重（比如哈希函数分布很差、很多键挤到同一个位置），平均查找复杂度就从 $O(1)$ 退化到接近 $O(N)$。所以哈希表会在负载因子超过阈值（如0.75）时主动扩容、把所有元素重新哈希到更大的数组里来保住性能。挑哈希函数也不能随便挑，分布差的家伙会让性能掉得跟滑梯似的。