4. 数据结构选型的工程决策
数据结构选型不是“背复杂度表”，而是把业务访问模式翻译成对结构的硬约束。工程上真正决定成败的，往往不是平均复杂度，而是访问模式分布、数据规模、内存局部性、是否需要有序性、并发读写比例这五个因素。下面先建立一套可操作的判断框架，再逐类结构给出适用边界与代价。
一、先问四个问题，再谈选型
- 主操作是什么？是按键查找、按范围扫描、按优先级取极值，还是维护实体间多对多关系？主操作决定候选结构集合。
- 数据规模与增长方式？万级以内，数组线性扫描可能比哈希表更快；千万级以上，哈希冲突与树高成为主导成本。
- 是否要求有序？需要按 key 排序输出、范围查询、前驱后继，就必须用有序结构（平衡树、跳表、有序数组），哈希表无法胜任。
- 读写比例与并发模型？读多写少可偏向有序数组+二分；写多读少偏向链表或哈希；高并发下还要考虑锁粒度与无锁结构。
把这四个问题落到具体场景，就得到下面的选型决策图。图中按“主操作”分流，标注了各结构在该操作下的典型代价与关键限制条件。
二、数组与链表：局部性与指针的取舍
数组的核心优势是连续内存带来的缓存局部性。顺序遍历时，CPU 预取器能高效加载相邻元素，实际吞吐常比链表高数倍。代价是中间插入/删除需要搬移后续元素，复杂度 O(n)。因此数组适合“读多写少、以遍历和随机访问为主”的场景，例如配置表、静态字典、批量计算输入。
链表把插入删除降到 O(1)（前提是已持有目标节点引用），但每次访问都要解引用指针，缓存命中率低。工程中纯链表很少单独使用，更常见的是哈希桶内挂链表（拉链法解决冲突）或LRU 缓存中的双向链表+哈希表组合。判断依据：若操作集中在两端或已知节点位置，链表占优；若需要按下标随机访问，数组不可替代。
三、哈希表：均摊 O(1) 背后的隐藏成本
哈希表的均摊 O(1) 建立在两个前提上：哈希函数分布均匀、负载因子受控。工程中必须关注：
- 扩容代价：负载因子超过阈值（如 Java HashMap 默认 0.75）触发 rehash，单次插入退化为 O(n)。对延迟敏感的服务，应预估容量并预留空间，或使用渐进式 rehash。
- 哈希碰撞攻击：若 key 可被外部构造，需使用带随机种子的哈希（如 SipHash），否则最坏情况退化为 O(n)。
- 无序性：需要按 key 排序输出、范围查询、找前驱后继时，哈希表无法直接支持，必须换用有序结构或额外维护有序索引。
典型适用：缓存映射、去重集合、词频统计、路由表精确匹配。不适用：排行榜范围查询、时间窗口聚合、需要稳定遍历顺序的场景。
四、树与堆：有序性与优先级的分工
平衡二叉搜索树（红黑树、AVL）提供 O(log n) 的查找、插入、删除，并天然支持有序遍历和范围查询。数据库索引、内存有序映射、区间查询都依赖这一特性。代价是实现复杂、常数因子大、每个节点额外存储平衡信息。若数据基本静态且读多写少，有序数组+二分查找往往比平衡树更快，因为缓存友好且无指针开销。
堆只维护偏序：堆顶是极值，但其余元素无序。它适合“只关心最大/最小”的场景，如 Top-K 统计、任务调度、Dijkstra 最短路中的优先队列。注意：堆不支持高效查找任意元素，也不支持有序遍历；若需要同时取极值和范围查询，应选平衡树而非堆。
五、图：关系建模的专用结构
图用于表达实体间的多对多关系，如社交网络、依赖拓扑、路网。选型时先确定存储表示：
- 邻接矩阵：O(V²) 空间，判断两点是否相邻 O(1)，适合稠密图。
- 邻接表：O(V+E) 空间，遍历某点邻居高效，适合稀疏图，是绝大多数工程场景的默认选择。
- 边集数组：适合 Kruskal 等按边处理的算法。
图算法的代价高度依赖表示方式与图密度。例如 BFS/DFS 在邻接表下为 O(V+E)，在邻接矩阵下为 O(V²)。选型时必须同时确定“图结构 + 算法 + 存储表示”三者，不能只看算法复杂度。
六、组合结构：工程中的常态
真实系统很少只用一种结构。常见组合模式：
| 场景 | 组合方式 | 关键收益 |
|---|---|---|
| LRU 缓存 | 哈希表 + 双向链表 | 查找 O(1)，淘汰 O(1) |
| 有序映射 + 快速查找 | 哈希表 + 跳表/平衡树 | 精确查找与范围查询兼得 |
| Top-K 流式统计 | 哈希表计数 + 小顶堆 | O(n log k) 完成筛选 |
| 路由/依赖分析 | 邻接表 + 优先队列 | 支持带权最短路与拓扑排序 |
总结成一句话：数组赢在局部性与随机访问，链表赢在已知位置的增删，哈希表赢在无序精确查找，树赢在有序与范围，堆赢在极值，图赢在关系建模。工程决策时，先锁定主操作与硬约束，再用组合结构补齐短板，最后用真实数据规模验证最坏情况是否可接受。