12. 数据结构选型指南

0. 本章先解决什么问题

学完一堆结构后,真正难的是实际问题里怎么选。

不要问:

哪个数据结构最好?

要问:

我的数据是什么?
我最频繁的操作是什么?
我必须保证什么?
我可以牺牲什么?

本章把前面的结构收束成一套选型方法。

这张图怎么读

这张图的用法很简单:不要从“我想用哪个结构”开始,而是从“我最频繁的操作是什么”开始。一个真实需求通常不只对应一个结构,而是多个结构一起维护同一批数据的不同视图。

1. 先列操作,不要先选结构

面对需求,先写操作表。

例子:

维护一批记录
按 id 查询
按时间排序输出
删除过期记录
统计数量

操作:

这时单个结构可能不够。

可能组合:

哈希表按 id 查
有序结构按时间维护
两者存同一记录引用或 id

2. 是否需要按下标访问

如果需要:

快速访问第 i 个元素

优先考虑:

• 数组。
• 动态数组。
• 分块数组。

不适合:

• 链表。
• 普通树。
• 哈希表。

按下标访问依赖连续存储和地址计算。

3. 是否需要按 key 精确查找

如果主要操作是:

给 key 找 value
判断 key 是否存在

优先考虑:

• 哈希表。
• 位图。
• 布隆过滤器。
• 有序映射。

选择规则:

4. 是否需要有序和范围

如果需要:

按顺序遍历
范围查询
找前驱后继
找大于某值的最小元素

考虑:

• 排序数组。
• 平衡树。
• 跳表。
• B+ 树。

哈希表不适合范围查询。

5. 是否需要频繁插入删除

插入删除要分位置。

注意:

链表删除 O(1) 的前提是已知节点或前驱。

如果还要查找位置,不能忽略查找成本。

6. 是否需要快速取最大/最小

如果要反复:

取当前最小
取当前最大

考虑:

• 堆。
• 优先队列。
• 平衡树。

堆不擅长查找任意元素和范围查询。

7. 是否是关系问题

如果问题里出现:

依赖
连接
路径
可达
最短
环
拓扑顺序

考虑图。

建模问题:

1. 顶点是什么?
2. 边是什么?
3. 是否有方向?
4. 是否有权重?
5. 图是稀疏还是稠密?
6. 需要 BFS、DFS、拓扑、最短路还是连通性?

图问题的第一步永远是建模。

8. 是否是字符串问题

如果问题涉及:

• 前缀查询。
• 自动补全。
• 子串搜索。
• 多关键词匹配。
• 路径匹配。

考虑:

同时确认字符编码和大小写规则。

9. 是否可以接受误判

如果你只需要过滤不存在项,并且能接受少量“可能存在”的误判:

布隆过滤器

如果不能接受误判:

使用精确结构

布隆过滤器适合做第一道门:

它说不存在 -> 直接拒绝
它说可能存在 -> 查真实数据

不要把它当最终存储。

10. 是否有内存和缓存压力

如果数据量很大,内存布局非常重要。

如果热数据放不进 Cache,程序会慢。

优化方向:

• 使用连续结构。
• 压缩字段。
• 分离冷热数据。
• 减少指针。
• 批量处理。

11. 是否需要组合结构

真实系统经常组合多个结构。

例子:LRU 缓存。

需求:

按 key 快速查找
按最近使用顺序淘汰

组合:

哈希表 -> key 定位节点
双链表 -> 维护最近使用顺序

例子:任务调度。

堆 -> 按优先级取任务
哈希表 -> 按 id 查任务状态
队列 -> 等待执行

组合结构的关键是同步不变量:

一个结构更新时,另一个结构也要保持一致。

机制深挖:组合结构的本质是维护多份索引

单个数据结构通常只优化一种视图。真实需求经常需要多种视图:

按 id 查
按时间扫
按优先级取
按状态过滤

这时系统会维护“真实数据 + 多份索引”:

record store
-> id index
-> time index
-> priority index
-> status buckets

难点从“某个操作快不快”变成“所有索引是否一致”。

一个组合结构的正确性不变量通常是:

索引能找到的 id,真实数据必须存在
真实数据中满足条件的记录,相关索引必须能找到
同一个记录在每个索引里的 key 必须来自同一版本

因此,数据结构选型不是“多加几个索引就结束”,而是要设计更新顺序、失败恢复和一致性校验。

设计反例:一个结构满足一个指标,常常牺牲另一个指标

假设要维护一批在线任务:

按 task_id 精确查询
按 deadline 扫描即将超时的任务
按 priority 取下一个最重要任务
取消任务时要立刻不可见

如果只选哈希表:

task_id -> task

按 id 查很快,但 deadline 扫描只能全表遍历,priority 取最大也要全表找。任务数量一大,慢点会固定出现在“扫描”和“取最值”。

如果只选堆:

按 priority 组织任务

取堆顶很快,但按 id 取消任务会很麻烦。没有额外位置索引时,找到任意任务可能要扫完整个堆;如果使用延迟删除,堆顶弹出时还要检查这个任务是否已经取消。

如果只选有序树:

按 deadline 或 priority 排序

范围能力变强,但只能天然服务一个排序维度。你按 deadline 建树,就不能同时用同一棵树快速取 priority 最大;按 priority 建树,又不能自然扫 deadline 区间。

所以真实设计通常长这样:

真实任务表: task_id -> task
deadline index: deadline -> task_id
priority index: priority -> task_id
cancelled / version: 判断索引项是否仍有效

这个反例说明:数据结构选型不是寻找“最强结构”,而是把需求拆成多个访问视图,再判断哪些视图需要独立索引,哪些视图可以延迟计算。

边界条件:多索引结构的失败常发生在半更新

组合结构最危险的时刻是更新了一半:

1. 真实任务表写入 task_7
2. priority index 写入 task_7
3. deadline index 写入失败

这时系统出现裂缝:

按 id 能找到 task_7
按优先级能取到 task_7
按 deadline 扫不到 task_7

读路径越多,这种裂缝越隐蔽。一个用户从优先级视图看到任务,另一个维护流程从 deadline 视图看不到任务,最后就会出现“任务存在但不会被清理”“任务被取消但仍被调度”这类问题。

设计多索引结构时,要明确三件事:

多索引结构真正的难点是:每个索引都在加速一种读法,同时也在增加一种不一致入口。

12. 选型速查表

13. 联系实际:从需求到结构

需求:

做一个排行榜,支持更新用户分数、查询某用户分数、取前 100 名、按排名范围查看。

分析:

• 按用户查询:需要 key -> score。
• 排名有序:需要按 score 有序。
• 更新频繁:有序结构要支持删除旧分数、插入新分数。
• Top 100 和范围:需要顺序能力。

可能组合:

映射表: user_id -> score
有序结构: score -> users

如果只取 Top 100,不需要范围,可能用堆加映射。
如果要完整排名和范围,平衡树或跳表更合适。

这就是选型:先需求,后结构。

13.1 选型案例:一个任务池怎么设计

需求:

按 id 查任务
按优先级取下一个任务
按创建时间清理过期任务
能快速判断某任务是否存在

单个结构很难同时满足:

这时更像是在维护多份索引:

任务真实数据
-> id 索引
-> 优先级索引
-> 时间索引

难点不在“会不会写某个结构”,而在一致性:

插入任务时,所有索引都要更新。
删除任务时,所有索引都要删除。
任务状态变化时,相关索引也要调整。

所以数据结构选型最终会回到不变量:每个索引必须和真实数据保持一致。

设计卡:为一个需求写结构选择说明

结构选型不要只写“使用某结构,因为快”。更完整的说明至少包含五句:

练习:为“按优先级处理任务,同时能取消指定任务”写一段选型说明。你可能需要组合优先队列和一个按 ID 定位的索引结构。这个练习的重点是承认现实需求经常不是单一结构能优雅完成,而是需要组合并维护一致性。

14. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 面对需求时如何先列操作和频率?
2. 按下标、按 key、有序范围、最值、关系、字符串分别该考虑哪些结构?
3. 为什么哈希表和树不是互相替代,而是能力不同?
4. 为什么真实系统经常组合多个结构?
5. 如何把误判、内存、缓存、更新频率纳入选型?
6. 如何从排行榜、缓存、任务调度这类真实需求推导结构组合?

数据结构选型的核心不是背答案,而是把需求拆成操作、约束和不变量,再选择最合适的成本模型。

延伸阅读

• from - zero · data-structures