数据结构篇：从组织数据到工程结构

前面三篇分别把学习路线、内存与引用、历史演进铺了一遍。走到这里，才真正进入一个个具体的数据结构。

我最开始学这一部分时，脑子里是一张“复杂度表”：数组查询 O(1)、链表插入 O(1)、哈希表平均查询 O(1)。表能背下来，题也能做一些，但一回到真实代码，我还是会犹豫：同样是保存一批数据，为什么有时用数组，有时用链表？已经有 HashMap 了，为什么还需要 LinkedHashMap、TreeMap？

后来我才发现，问题不在于记住的结构太少，而在于学习顺序反了。我一直从“这个结构有什么特点”出发，却没有先问“我准备怎样使用这些数据”。

线性结构与散列结构的选择关系

这篇是我给数据结构篇整理的一张总地图。它不会把每种结构一次讲完，而是先把我后来反复使用的两条判断线串起来：访问方式决定结构，不变量保证结构还能正常工作。

我后来先看数据怎么被访问

以前看到需求，我会先从自己熟悉的集合里挑一个。现在我更习惯先把操作写下来：数据主要用来查询、插入、删除还是遍历？查询依赖下标、键、范围还是关系？顺序、扩容、并发、磁盘读写和误判又有没有限制？

这些问题看起来比“选哪个类”慢，实际上能让我少走很多返工。

我关心的操作	我会先想到的结构	它帮我省掉什么	同时付出的代价
按下标快速访问	数组 / 动态数组	可以直接计算元素位置，缓存也更友好	中间插入删除通常需要搬移
已经拿到节点后插入删除	链表	只调整附近节点的连接	找到节点本身通常还要遍历
最近加入的先处理	栈	自然保存“回到上一步”的现场	只能从栈顶进入和离开
最早加入的先处理	队列	自然表达排队和按层推进	访问位置受到限制
按键定位数据	哈希表	平均情况下不必逐条查找	要处理冲突、扩容和哈希质量
持续取得最大值或最小值	堆	不用每次把全部元素重新排序	除堆顶外，其余元素并不完全有序
维护顺序和范围	搜索树 / 平衡树	查询、插入和范围遍历可以兼顾	要维护旋转或其他平衡规则
表达路径、依赖和连接	图	能直接描述复杂关系	存储方式和算法都依赖边的规模
维护不断合并的集合	并查集	合并和连通查询非常快	删除和还原具体路径并不擅长
海量数据的存在性预判	Bloom Filter	用很少空间挡掉“一定不存在”的请求	允许假阳性，也不适合普通删除

我以前最容易忽略“前提”。例如“链表删除是 O(1)”这句话，必须先拿到目标节点；如果还要从头寻找，整体仍然是 O(n)。哈希表的 O(1) 也是平均情况，冲突、扩容和不合适的哈希函数都会改变实际表现。

复杂度不是结构身上的永久标签，它描述的是某个操作在特定前提下的成本。

第一段路：先把线性结构和哈希表学稳

数组、链表、栈、队列和哈希表是我最早接触的一批结构。刚开始我觉得它们太基础，真正写过一些组合结构以后才发现，后面很多东西只是把这些基础能力重新组合。

数组解决连续存储和下标定位。
链表解决节点之间的灵活连接。
栈和队列限制数据进入、离开的顺序。
哈希表建立键到存储位置的映射。

例如 LRU 同时需要“按键快速找到节点”和“维护最近访问顺序”，于是用了哈希表加双向链表；优先队列是在数组上维护堆的不变量；BFS 离不开队列；HashMap 的桶里又会出现链表和红黑树。

这些组合让我意识到，学习基础结构并不是为了手写一遍 API，而是为了看懂高级结构在借用什么能力。

第二段路：从会遍历一棵树，到理解不变量

树结构是我第一次明显感觉到“会写代码”和“理解结构”不是一回事的地方。

二叉搜索树的左小右大很好记，但按有序数据连续插入，它就可能退化成链表。AVL 和红黑树都在控制高度，却选择了不同的平衡强度；B 树和 B+ 树把一个节点扩成多路，是为了减少磁盘访问；堆只维护父子之间的优先级，因为它只关心快速取得极值。

后来我学习树时不再先背插入、删除步骤，而是先找它必须守住的规则：

堆要保证父节点与子节点之间的优先级关系。
BST 要保证左子树、当前节点和右子树之间的顺序。
AVL 要限制左右子树的高度差。
红黑树用颜色规则限制路径长度。
Trie 让从根出发的一条路径代表一个前缀。
并查集让同一集合最终指向同一个代表元。

旋转、染色、分裂和路径压缩以前像几套突然出现的技巧；放回不变量里看，它们其实都在修复刚刚被操作破坏的规则。

第三段路：我为什么把图放在树之后

树至少还有父子层级，图里的连接则自由得多。课程依赖、好友关系、地图导航、服务调用和转账网络，都可以建模成图，但同一个业务换一种边的定义，最后得到的答案可能完全不同。

我写图相关代码时踩过的坑，很多并不在 DFS 或 BFS，而在建模阶段：忘记区分有向边和无向边、没有处理重复边和自环、把权重含义写反，或者没有估算稠密图与稀疏图的空间差异。

所以现在拿到图问题，我会先在纸上确认几件事：节点代表什么，边代表什么，边有没有方向和权重，是否允许重复与自环，数据规模更适合邻接矩阵还是邻接表。把这些确定下来，后面的遍历和路径算法才有意义。

第四段路：开始接受“不追求绝对准确”的结构

Bloom Filter、Count-Min Sketch 和 HyperLogLog 刚接触时让我有些不适应。以前学的数据结构都强调得到准确答案，它们却主动接受误差。

把它们放到海量数据场景里，我才理解这不是“不可靠”，而是明确做了一次交换：业务允许少量误差，系统就能用更少的空间处理更大的数据量。Bloom Filter 能确定“一定不存在”，但只能判断“可能存在”；这个边界也决定了它适合挡在数据库前面做预判，而不能替代最终的准确查询。

再往工程里走，还会遇到更多组合和取舍：跳表用多层索引加速有序链表，一致性哈希减少节点变化时的数据迁移，B+ 树适应磁盘页和范围查询。它们并不是为了让名字越来越多，而是在新的约束下重新组合时间、空间、顺序和准确性。

我给自己安排的学习顺序

我后来重新补数据结构时，按下面这条路线走得更顺：

数组
  ↓
链表
  ↓
栈、队列
  ↓
哈希表
  ↓
堆、Trie、二叉搜索树
  ↓
AVL、红黑树、2-3 树
  ↓
并查集、图
  ↓
Bloom Filter
  ↓
LRU、跳表、B+ 树、一致性哈希等工程结构

这不是唯一顺序，只是比较符合我的理解过程：先看连续存储和节点连接，再看访问顺序与键值映射；之后进入需要维护不变量的树和集合，最后再讨论图、概率结构与工程组合。

我会用这些问题检查自己

现在学完一种结构，我不再只问“代码能不能默写”，而会回头回答下面这些问题：

它主要优化了哪一种操作，又让哪一种操作变贵了？
“数组查询快、链表删除快”分别缺少什么前提？
栈和队列为什么更像访问规则，而不是固定的底层存储？
哈希表为什么只能说平均 O(1)？
堆为什么适合 Top K，却不适合完整的有序遍历？
普通二叉搜索树在什么情况下会退化？
图的方向、权重和存储方式会怎样影响后续算法？
Bloom Filter 的“可能存在”和“一定不存在”应该怎样用在真实系统里？

如果这些问题能够用自己的话说清楚，后面再进入具体实现，很多代码就不再像需要硬背的模板。这也是我写接下来每一篇数据结构文章时，会一直沿用的方式。