本专栏覆盖数组、链表、哈希表、树、堆、图以及 Trie、跳表、红黑树、LRU 等进阶结构。这一篇是学习地图：先把主题按解决的问题分组，再理清依赖关系与推荐顺序，最后用一句话索引告诉你每个结构到底解决什么问题。

主题分组

按”解决的问题类型”，全部主题可以分成四组。

基础线性组：数组、链表、栈、队列。回答”元素在内存里怎么摆、按什么秩序进出”，是一切结构的地基，也是复杂度思维的起点。

定位组：哈希表。回答”怎样按键用平均 O(1) 找到元素”，是缓存、索引、去重、计数的共同底座。

层级与关系组：树、堆、图。树表达层级与有序，堆表达偏序下的极值，图表达任意连接关系——三者分别对应”有等级””有轻重””有连接”三类现实问题。

进阶工程组：Trie、并查集、跳表、红黑树、布隆过滤器、LRU 缓存。每个都对应真实的系统组件：搜索提示、动态连通分组、Redis ZSet、TreeMap、缓存穿透防护、缓存淘汰策略。

依赖与顺序

依赖主线是：线性结构 → 哈希表 → 树 → 堆/图 → 进阶结构。理由如下：

  1. 线性结构建立”存储布局决定操作成本”的核心直觉，后面每个结构都是这个直觉的变体；
  2. 哈希表建立在数组与链表之上（拉链法），不懂线性结构就谈不上冲突处理与扩容；
  3. 树是堆、红黑树、B+ 树、Trie 的共同祖先，二叉树遍历与递归是必备前置技能；
  4. 堆紧跟在树之后：完全二叉树加数组表示，理解树之后它只是”维护父子偏序的特例”；
  5. 图需要栈和队列（DFS/BFS）以及哈希表（邻接表、访问标记）做支撑，因此放在中段；
  6. 进阶组各自挂靠前面某一支：LRU = 哈希表 + 双向链表；跳表 = 有序链表 + 多级索引；红黑树 = 二叉搜索树 + 平衡约束；布隆过滤器 = 位数组 + 多个哈希函数。

推荐学习顺序：线性结构 → 哈希表 → 树 → 堆 → 图 → Trie → 并查集 → 跳表 → 红黑树 → 布隆过滤器 → LRU 缓存。把 LRU 放在最后，因为它是”组合多个基础结构解决工程问题”的最佳范例，相当于一次总复习。

一句话索引

主题 一句话说明
线性结构 数组与链表的存储之争、栈与队列的进出约束，回答”元素怎么摆、怎么进出”
哈希表 用哈希函数把 key 映射到桶，换来平均 O(1) 的查找、插入与删除
树 表达层级关系，二叉搜索树与 B/B+ 树是 MySQL 索引的结构基础
堆 只维护父子偏序，O(log n) 插删、O(1) 取极值，专治 Top K 与调度
图 表达任意连接关系，DFS/BFS 是遍历、搜索与依赖分析的起点
Trie 按字符逐层展开的前缀树，解决前缀匹配与搜索框自动提示
并查集 近乎 O(1) 的合并与连通查询，解决动态分组与连通性问题
跳表 给有序链表加多级索引，用简单实现换来 O(log n) 查找与范围查询
红黑树 近似平衡的二叉搜索树，保证最坏 O(log n)，是 TreeMap 与 HashMap 树化的底座
布隆过滤器 位数组加多个哈希函数，用可控的误判率换”一定不存在/可能存在”的极速判定
LRU 缓存 哈希表加双向链表，实现读写 O(1) 的最近最少使用淘汰

小结

先建立”布局决定成本”的直觉，再沿依赖链逐个击破：线性、哈希、树、堆与图，最后进阶结构。每学一个结构都自问四件事——怎么存、怎么查、怎么改、适合什么场景；四个问题都答得上来，再进入下一个主题。