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

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

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

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

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

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

把“快”拆成不同保证

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

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

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

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

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

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

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

小测

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

字典最基本的接口是 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$ 个内部节点时高度不超过

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

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

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

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

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

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

小测

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

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

若规则是按到达顺序处理，普通先进先出队列的入队和出队都可做到 $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$ 个键时，高度满足

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

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

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

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

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

小测

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

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

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

三个接口维护集合归属

并查集提供：

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

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

朴素连接可能形成长链。按秩合并让秩较小的根指向秩较大的根，秩相同才任选一方并把新根的秩加一。路径压缩则在查找根返回时，让查找路径上的节点直接指向根。两种策略合用时，$m$ 次操作在 $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 是“邻接表或矩阵 + 优先队列 + 顶点位置句柄”。算法名称相同，底层表示不同，实际成本也会不同。

小测

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

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

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

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

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

有向无环图按拓扑序松弛

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

非负权图用 Dijkstra

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

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

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

允许负权边时用 Bellman–Ford

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

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

小测

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

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

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

用可证伪的指标验证选型

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

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

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

一份可复用的决策顺序

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

小测