真实世界中的数据结构 | 自在学

真实系统里的数据结构选择

一个功能慢下来时，我们很容易先问：“该换成哪种更快的数据结构？”这个问题通常问早了。结构没有脱离操作的快慢。哈希表擅长按键定位，却不能自然回答“下一个更大的键”；堆能快速给出最小项，却不能高效查找任意元素；邻接矩阵查一条边很直接，面对稀疏大图时却会为大量不存在的边预留位置。

真正的选型顺序是：先写清要支持的操作，再估算数据规模与访问分布，然后决定需要最坏保证、期望保证还是摊还保证，最后把内存占用、页面读写和结构维护成本一起算进去。复杂系统也很少只靠一种结构。常见做法是让多个结构各守一份契约，并用稳定标识把它们连接起来。

从操作契约、数据规模、性能保证到组合结构的选型路线

本文用四类持续出现的工程问题串起这套方法：按键检索、按优先级处理、维护连接关系，以及在图上求可达性和低成本路径。读完后，你应该能把“选一个熟悉的结构”改成一份可以检查、测量和迭代的设计说明。

先写操作契约，再谈结构名称

数据结构的接口描述“允许做什么”，不变式描述“为什么这些操作可以快而且正确”。选型时，先把需求改写成操作频率表。下面这张表不是结论，而是提问模板：

需求	需要写清的操作	容易遗漏的条件
按编号找对象	查询、插入、删除	键空间多大，是否允许重复键
总取最紧急任务	插入、查看最小项、取出最小项、降低键值	优先级会不会修改，是否需要稳定处理同优先级任务
查前驱、后继或范围	查询、插入、删除、前驱、后继、区间输出	是否要求有序，最坏延迟能否退化
维护动态分组	建立单元素集合、合并、判断是否同组	边是只增加，还是还会删除
遍历依赖关系	枚举邻接点、判断边、遍历全部可达点	图是稀疏还是稠密，是否有方向和权重

把“快”拆成不同保证

同样写成 $O(1)$ 或 $O(\lg n)$ ，含义可能完全不同。

最坏时间约束单次请求的上界，适合不能接受长尾停顿的路径。
期望时间依赖随机化或输入分布。哈希表在合理散列假设下查找很快，但碰撞极端集中时仍可能线性退化。
摊还时间把偶发昂贵操作分摊到一串操作上。它说明长序列的总成本，却不保证每次操作都便宜。
I/O 成本按读写页面计数。数据放不进主存时，少一次页面访问往往比少做几十次比较更有价值。

还要区分“查询不存在”和“查询成功”。链接法哈希表在均匀散列假设下，两者的期望成本都是 $\Theta(1+\alpha)$ ，其中装载因子

\alpha=\frac{n}{m}

表示 $n$ 个元素分布在 $m$ 个槽中的平均链长。若设计文档只写“哈希查询是常数时间”，却不记录装载因子、散列策略与扩容阈值，这个结论就无法验证。

把空间模型放到同一张账上

结构空间不只包括元素本身，还包括空槽、指针、颜色或秩等元数据，以及为了互相定位而保存的句柄。图的规模最好同时写成 $|V|$ 和 $|E|$ ；只写一个模糊的 $n$ ，会把稀疏图与稠密图的差别藏起来。

当数据跨入外部存储后，还要记录页面大小、每页能放多少键和指针、根或热点页面是否常驻内存。此时“树高”实际是在估计一次查询要经过多少页。

选型文档至少应有五列：操作、频率、规模、所需保证、主要成本单位。先填这五列，再讨论哈希表、红黑树、B 树或图算法，争论会具体得多。

小测

一个服务要求按键精确查询，键没有顺序输出需求，允许基于合理散列假设给出期望保证。第一候选是什么？

评估一个外存索引时，哪些量应该进入成本模型？

字典选型要在哈希、搜索树与增强结构之间划线

字典最基本的接口是 INSERT、SEARCH 和 DELETE。如果键来自很小且连续的全集，可以直接把键当数组下标，三个操作都有最坏 $O(1)$ 时间。问题在于，真实键空间经常远大于实际元素数；为每个潜在键保留一个槽会浪费大量内存。

哈希表用顺序能力换取短访问路径

哈希函数把大键空间映射到 $m$ 个槽。因为不同键可能落在同一槽，碰撞不是异常，而是必须设计的常态。

链接法让每个槽指向一条冲突链。若插入对象时已知它不存在，把节点放到链头可在 $O(1)$ 完成；若删除接口拿到对象句柄，双向链也能常数时间拆除。若删除只给键，仍要先在链中找到对象。这里可以看出：同样叫“删除”，参数形式不同，复杂度也不同。

开放寻址把所有元素放在数组内部，冲突时按探查序列继续找槽。它减少外部节点指针，却要求装载因子严格小于 1；删除还需要“已删除”标记，不能直接改回“从未使用”，否则查找会在探查链中途错误停止。

哈希表的边界很明确：它不保留键序。要找最小键、前驱、后继，或者输出区间 $[a,b]$ ，往往只能扫描全表或再加一个有序索引。静态键集合若建立后不变，并且查询需要最坏 $O(1)$ ，可以采用两级散列：一级分桶，含 $n_j$ 个键的桶分配 $n_j^2$ 大小的二级表并重新选函数，直到桶内无碰撞。它用构建期工作换取查询期保证。

二叉搜索树的成本取决于高度

二叉搜索树维持左子树键不大于当前键、右子树键不小于当前键的次序。查询、最小值、最大值、前驱、后继、插入和删除都沿树高 $h$ 走一条路径，成本是 $O(h)$ 。

这既是优势，也是风险。若插入顺序让树接近链， $h$ 可增长到 $n-1$ ，操作随之退化为线性时间。红黑树用颜色与黑高约束限制形状：根到叶的最长简单路径不超过最短路径的两倍，含 $n$ 个内部节点时高度不超过

2\lg(n+1)

于是基本动态集合操作都有最坏 $O(\lg n)$ 保证。插入和删除先按搜索树规则修改，再用重新着色和少量旋转恢复约束。工程上的交换是：每次写入多做维护，换来稳定的单次查找上界和有序能力。

增强树把新查询压缩成局部摘要

平衡树的价值不止“存有序键”。如果某个附加字段可以由节点自身和左右孩子的信息合成，那么一次修改只需沿祖先链更新，并在旋转涉及的局部节点上重算，通常不会改变 $O(\lg n)$ 的渐近写入成本。

顺序统计树在每个节点保存子树大小：

size(x)=size(x.left)+size(x.right)+1

比较目标名次 $i$ 与 $size(x.left)+1$ ，就能决定返回当前节点、进入左子树，还是把名次减去左侧规模后进入右子树。选择第 $i$ 小和查询某节点排名都只走一条根到叶或叶到根路径。

区间树保存闭区间，并按左端点建立红黑树；每个节点再维护子树中最大的右端点 max。查询区间与当前节点不重叠时，若左孩子的 max 仍不小于查询左端点，左子树可能有答案；否则整棵左子树都能安全剪掉。这个结构展示了增强设计的四步：选底层结构、定义摘要、证明修改可维护、再设计新查询。

哈希表、红黑树、顺序统计树与区间树的操作边界

不要同时把同一批对象完整复制到哈希表和有序树。更稳妥的做法是保存一份对象，由两个索引持有稳定标识；插入、删除和回滚必须以同一事务边界更新两个索引。

小测

只要使用二叉搜索树，查询就一定有最坏 O(log n) 时间。

哪些需求会让有序或增强搜索树比单独的哈希表更自然？

调度接口决定该用普通队列还是优先队列

调度不是某个具体系统的专有问题。只要有一批待处理对象，并且每次都要选出“下一项”，就必须先定义选择规则。

若规则是按到达顺序处理，普通先进先出队列的入队和出队都可做到 $O(1)$ 。若规则是按数值最小或最大处理，就需要优先队列。最大优先队列通常支持插入、查看最大项、取出最大项和增大键值；最小优先队列对称地支持插入、查看最小项、取出最小项和减小键值。

二叉堆不维护完整排序

以最小堆为例，父节点的键不大于孩子。最小值固定在根，所以查看最小项是 $O(1)$ ；取出根后把最后一个元素移到根，再向下恢复堆序，成本 $O(\lg n)$ ；插入先放到末尾再向上移动，也是 $O(\lg n)$ 。降低某个元素的键值时，它只可能违反与父节点的关系，因此沿父链上移即可。

这套接口适合事件调度：事件以发生时间为键，每次取出时间最早的事件；处理事件时产生的新事件再插入队列。它也适合维护图算法的前沿，因为某个顶点的候选代价改善后，可以执行降低键值。

句柄是实现里不能省掉的一层

堆元素在数组中会交换位置。若调用方只保存“任务编号”，却要取消任务或修改其优先级，就必须从编号定位当前堆下标。常见组合是：

堆数组保存 (键值, 稳定编号)；
哈希表或位置数组保存 稳定编号 → 堆下标；
每次交换堆元素时，同时更新两个编号对应的位置。

这样，按编号定位是期望 $O(1)$ 或最坏 $O(1)$ ，随后调整堆是 $O(\lg n)$ 。若漏掉位置更新，结构表面仍满足堆序，却会让后续修改落在错误对象上。这类错误说明“组合结构的不变式”比单个结构的不变式更多。

同优先级的稳定顺序也要显式设计。可以把键写成 (优先级, 到达序号) 的字典序，先比较优先级，再比较递增序号。仅依赖堆的数组位置，不会自然得到稳定性。

最小堆、稳定编号与位置表组成可修改的调度队列

小测

一个事件模拟器总要处理时间最早的事件，并允许处理时加入未来事件，最合适的主结构是什么？

若要按稳定任务编号修改堆中任意任务的优先级，通常还要维护“任务编号 → ____”的映射。

数据放不进主存时，B 树按页面组织搜索

内存搜索树把每个节点访问近似看作一次常数成本。外部存储的读取单位却是页面：为了取得一个键而调入页面时，与它同页的数据也会一起进入内存。此时设计目标从“少比较几次”变为“少访问几个页面，并让每个页面带回足够多的信息”。

高扇出压低页面路径

B 树的一个节点包含多个有序键和多个孩子指针。若节点有 $q$ 个键，就有 $q+1$ 个孩子，这些键把值域切成多个区间。节点通常设计得接近一个页面大小；读入一页后，在主存中找到目标键所在区间，再只读取对应孩子页。

设最小度数为 $t\ge 2$ 。除根以外，每个节点至少有 $t-1$ 个键，至多有 $2t-1$ 个键；内部节点至少有 $t$ 个孩子，至多有 $2t$ 个孩子；所有叶子位于同一深度。含 $n$ 个键时，高度满足

h\le \log_t\frac{n+1}{2}

扇出越大，对数的底越大，根到叶经过的页数越少。若根页常驻内存，一次查询的外存读取还可以再少一次。

写入和删除维护“下降前安全”

查找每层只读一个孩子页，因此访问 $O(h)$ 个页面。插入也可以保持单向下行：准备进入一个满孩子前，先把它围绕中位键分裂，中位键提升到父节点，左右两半各保留 $t-1$ 个键，然后再决定进入哪一半。这样不会下降到满节点，抵达叶子时一定有位置可写。

删除采用对称思路：准备下降到只有 $t-1$ 个键的孩子前，先从有余量的相邻兄弟借键，或者把孩子、父分隔键和兄弟合并。这样递归进入的节点通常至少有 $t$ 个键，可以承受一次删除。若内部根最终没有键，让唯一孩子成为新根，树高减一。

页内搜索可以线性扫描，也可以二分查找。前者的 CPU 成本随 $t$ 增长，后者减少比较；但两者的页面访问路径相同。选页大小与节点容量时，要同时考虑键宽、指针宽、页面读取固定开销和页内处理成本，不能只追求最大扇出。

B 树把节点对齐页面并用高扇出减少外存读写

B 树解决的是页面局部性与最坏高度问题。把数据留在主存时，它未必胜过更简单的平衡二叉树；是否采用它，取决于成本单位是不是页面 I/O。

小测

B 树节点包含大量键和孩子指针，最直接的工程目的是什么？

自顶向下插入在进入满孩子前先分裂它，可以让插入过程保持单向下行。

动态连通性适合并查集，静态全图适合一次遍历

“甲和乙现在是否属于同一组？”看起来像图搜索问题，但关系的变化方式会改变最合适的结构。

若无向图固定不变，一次深度优先搜索或广度优先搜索就能给每个连通分量编号，预处理成本 $\Theta(|V|+|E|)$ ，之后同分量查询只需比较编号。若边持续增加，并且每增加一条边后都要回答同组查询，重复遍历全图会浪费已经得到的信息。并查集正是为这种操作序列设计的。

三个接口维护集合归属

并查集提供：

MAKE-SET(x)：建立只含 x 的集合；
FIND-SET(x)：返回 x 所在集合的代表；
UNION(x,y)：合并 x 与 y 所在的两个集合。

用根树表示集合时，每个节点只保存父指针，根的父指针指向自己。FIND-SET 沿父指针到根；UNION 把一个根接到另一个根上。

朴素连接可能形成长链。按秩合并让秩较小的根指向秩较大的根，秩相同才任选一方并把新根的秩加一。路径压缩则在查找根返回时，让查找路径上的节点直接指向根。两种策略合用时， $m$ 次操作在 $n$ 个元素上的总时间是

O(m\alpha(n))

其中 $\alpha(n)$ 增长极慢，实际规模下可以把它理解成非常接近常数的摊还因子，但严谨地说并不是单次最坏 $O(1)$ 。

能合并不等于能撤销

并查集把两个集合合并后，不保留“删掉某条边会不会拆开分量”所需的完整结构。若需求包含任意删边，普通并查集接口不够。设计说明必须把“关系只增加”写成前置条件；否则上线后才发现需要撤销，会迫使底层结构重做。

并查集也不是图的完整替代品。它能回答是否连通，却不能输出一条具体路径、枚举邻居或计算距离。常见组合是：邻接表保留边，支持遍历和路径重建；并查集额外维护快速连通性判定。

静态图遍历与增量并查集的适用边界

小测

无向关系只会增加，并且每次增加后都要频繁判断两点是否连通，最合适的辅助结构是什么？

普通并查集既能高效合并集合，也能在删除任意一条边后立即拆分集合。

图表示与遍历要一起选择

图算法的复杂度离不开表示。对 $G=(V,E)$ ，邻接表为每个顶点保存它的出边或邻居。无向边在两端各出现一次，有向边只出现在起点列表里，因此总空间是 $\Theta(|V|+|E|)$ 。它适合稀疏图，也让“枚举某点的所有邻居”只付出与实际度数相当的成本。

邻接矩阵使用 $|V|\times|V|$ 表格，空间为 $\Theta(|V|^2)$ ，无论实际有多少边。它的优势是判断边 $(u,v)$ 是否存在只需访问一个单元格。图较小、接近稠密，或查边远多于遍历邻居时，这个交换可能合理。

还可以组合：以邻接表做主表示，再为高频查边的顶点把邻接集合改成哈希表或平衡树。前者给期望快速查边，后者给最坏对数查边与有序邻居，但每条边会承担更多元数据。

广度优先搜索处理单位边距离

广度优先搜索从源点开始，用先进先出队列维护已发现但尚未扫描完邻接表的顶点。距离为 $k$ 的顶点会在距离为 $k+1$ 的顶点之前出队，因此第一次发现某顶点时，就得到按边数计算的最短距离。每个顶点最多入队一次，每条边只按表示扫描常数次，邻接表下总时间为 $\Theta(|V|+|E|)$ 。

前驱字段把发现关系保存成广度优先树，可以从目标沿前驱回到源点，再反转得到一条最少边数路径。邻接表中的邻居顺序可能改变具体选中哪棵前驱树，但不会改变最短距离。

深度优先搜索揭示嵌套关系

深度优先搜索沿一条尚未探索完的路径继续深入，结束后再回退。它可以用递归调用栈，也可以显式维护栈。每个顶点记录发现时间和完成时间，祖先与后代的时间区间彼此嵌套；不同深度优先树的区间互不相交。

在有向图中，探索到灰色祖先的边是后向边。存在后向边等价于存在有向环，这给依赖校验提供了直接判据。深度优先搜索同样在邻接表下运行 $\Theta(|V|+|E|)$ 。

拓扑顺序与强连通分解服务不同问题

有向无环图的拓扑顺序要求每条边 $u\to v$ 中， $u$ 出现在 $v$ 之前。可以在深度优先搜索完成一个顶点时把它放到列表头部，最终得到按完成时间递减的顺序；若搜索发现后向边，就不能把结果当作合法拓扑序。

强连通分量处理含环有向图：同一分量内任意两点互相可达。线性时间做法先在原图上做深度优先搜索记录完成时间，再构造所有边反向的转置图，最后按第一次完成时间递减的顶点顺序在转置图上搜索。第二次搜索得到的每棵树就是一个强连通分量。把每个分量压缩成一个点后，分量图一定无环，后续便可在这个较小的有向无环图上继续处理依赖。

邻接表上的广度优先、深度优先、拓扑排序与强连通分解

小测

关于图表示与遍历，哪些说法正确？

要把含环的有向依赖图压缩成无环分量图，首先应计算什么？

最小生成树展示了结构怎样决定算法实现

给定连通、无向、带权图，若目标是用总权重最小的一组边连接全部顶点，求的是最小生成树。结果有 $|V|-1$ 条边且无环。它与“从某个源点到其他点的路径都最短”不是同一个目标，二者可能选择完全不同的边。

最小生成树的核心安全条件是割：把顶点分成两部分，若当前已选边没有跨越这道割，那么跨割的最轻边可以安全加入某棵最小生成树。两种经典实现的差别，主要体现在怎样维护“当前部分”。

Kruskal 用并查集维护一片森林

Kruskal 先把边按权重非递减排列。开始时每个顶点是独立树；依次检查边 $(u,v)$ ，若两端代表不同集合，就选中它并合并两个集合；若已经同集合，加入这条边会成环，因此跳过。

排序成本是 $O(|E|\lg |E|)$ 。并查集处理所有检查和合并的总成本接近线性，因此整体通常写成 $O(|E|\lg |V|)$ 。它很适合边列表已经存在、排序自然，而且图较稀疏的情形。

Prim 用优先队列扩张一棵树

Prim 从任意根开始，始终维护一棵已选树。对每个树外顶点，键值记录“把它接入当前树的最轻边权”，优先队列每次取键最小的顶点；扫描新顶点的邻接边时，若发现更轻的接入方式，就更新父节点并降低键值。

邻接表加二叉最小堆时，每个顶点取出一次，每条边至多触发一次有效的降低键值检查，总成本是 $O(|E|\lg |V|)$ 。若使用邻接矩阵并用数组线性寻找下一个最小键，可以得到简单的 $O(|V|^2)$ 实现；图很稠密时，这个实现未必比堆版本差。

这两个算法把前面几节的结构组合起来了：Kruskal 是“排序边 + 并查集”，Prim 是“邻接表或矩阵 + 优先队列 + 顶点位置句柄”。算法名称相同，底层表示不同，实际成本也会不同。

Kruskal 的森林合并与 Prim 的单树扩张

小测

Kruskal 检查一条边的两个端点是否已在同一棵树中，最自然使用什么结构？

最小生成树保证从选定源点到每个顶点的路径权重都最小。

最短路选型先检查边权与环

单源最短路为每个顶点维护一个候选距离 d 和前驱。松弛边 $(u,v)$ 时，检查经过 $u$ 是否能改进 $v$ ：

\text{若 } d[v]>d[u]+w(u,v),\quad d[v]\leftarrow d[u]+w(u,v)

若更新成功，同时令 pred[v]=u。不同算法的共同核心都是松弛；差别在于边被松弛多少次、按什么顺序松弛，以及何时能确认一个距离不再变化。

单位权图直接用广度优先搜索

所有边成本相同时，路径权重只取决于边数。广度优先搜索按层处理顶点，在 $\Theta(|V|+|E|)$ 时间内得到从源点出发的最少边数距离，不需要优先队列。

有向无环图按拓扑序松弛

若图无环，拓扑顺序保证一条路径上的边按从前到后顺序被处理。按拓扑序扫描每个顶点并松弛其出边，每条边只处理一次，总时间也是 $\Theta(|V|+|E|)$ 。边权可以为负，因为图中根本不存在负权环。

非负权图用 Dijkstra

边权全部非负时，可以每次从最小优先队列取出候选距离最小的树外顶点，并把它的距离确定下来，然后松弛所有出边。非负条件很关键：已经取出的顶点不会再通过尚未处理的路径得到更小距离。

用数组保存候选距离并线性找最小值，成本是 $O(|V|^2)$ ；用邻接表和二叉最小堆，成本是

O((|V|+|E|)\lg |V|)

若源点能到达全部顶点，常简写为 $O(|E|\lg |V|)$ 。这里再次需要位置句柄，因为松弛会触发堆中的降低键值。

允许负权边时用 Bellman–Ford

负权边会破坏 Dijkstra 的“取出即确定”。Bellman–Ford 对全部边进行 $|V|-1$ 轮松弛，因为无可达负环时，总能选择一条不含环、至多含 $|V|-1$ 条边的最短路。随后再扫描一次边；若仍能改进某个距离，说明源点可以到达负权环，有限最短路不存在。

它的时间是 $O(|V||E|)$ ，比前面几种方法高，但处理范围也更广。注意“图里有负环”和“源点可达负环”不同：只有后者会让本次单源问题中的相关距离失去有限下界。

单位权、无环、非负权与负权条件下的最短路选择边界

小测

一个带权有向无环图含负权边，要从单个源点求全部最短距离，优先选择什么方法？

哪些条件会影响单源最短路算法的选择？

组合结构要靠不变式、测量和迁移闭环

真实功能通常同时需要按编号定位、按优先级取任务、按时间范围查询，并保存对象之间的依赖。一个可落地的组合可以是：

职责	主结构	保存内容
对象唯一存储	紧凑对象表	业务字段与稳定编号
编号定位	哈希表	编号到对象位置
下一任务	最小堆	优先级与稳定编号
时间区间查询	增强红黑树	区间、最大右端点与稳定编号
依赖遍历	邻接表	顶点编号与边
只增连通性	并查集	父指针与秩

重点不是结构数量，而是更新协议。插入对象时，先确定对象已经获得稳定编号，再更新需要它的索引；删除时要从所有索引移除；任何一步失败都必须回滚或通过日志重放恢复一致。堆交换要更新位置表，树旋转要重算局部摘要，邻接表加边后才可合并并查集分量。这些都是跨结构不变式。

用可证伪的指标验证选型

上线前不要只比较渐近式。至少测量：

请求分布下的中位数与高分位延迟；
哈希装载因子、最大冲突链或探查长度；
平衡树高度、旋转次数与增强字段校验失败数；
堆大小、降低键值次数和位置表一致性；
B 树每次请求的页面读写、缓存命中与节点占用率；
图的 $|V|$ 、 $|E|$ 、度分布，以及实际扫描边数。

这些指标能触发结构迁移。例如，精确查询仍占绝大多数但范围查询开始增长，可以保留哈希主索引并增建有序辅助索引；数据跨出主存后，再把有序索引迁到按页组织的 B 树。迁移期间应双写、校验两侧结果，完成切流后再移除旧索引。

一份可复用的决策顺序

先列操作与参数形式。特别区分“按键删除”和“拿到对象句柄删除”、“只看最小项”和“还要修改任意项”。

再记录规模与变化方式：键空间与实际键数、顶点数与边数、数据是否跨页、关系是静态、只增加还是允许撤销。

选择保证类型。不能接受长尾就优先最坏界；允许随机假设可用期望界；只关心长序列吞吐才采用摊还界。

组合最少数量的索引，并逐条写出跨结构不变式、失败回滚和重建方式。

最终，好的选型不是列出“某结构更快”，而是能完整回答：快的是哪个操作，在什么规模和假设下快，最坏会发生什么，为此付出多少空间与维护成本，以及条件变化后怎样迁移。

小测

一个对象同时进入哈希索引、最小堆和区间树时，哪些属于必须维护的跨结构不变式？

压测发现哈希表高分位延迟升高，第一批最有诊断价值的内部指标是什么？