数据结构与算法之美 — 学习笔记

来源：极客时间专栏《数据结构与算法之美》— 王争（前 Google 工程师） 专栏共 81 讲，本文涵盖数据结构核心章节（约 25 讲），按知识点分类整理。

📖 专栏章节速查

⚡ 复杂度分析（第 03-04 讲）

"数据结构和算法的半壁江山，是学习的精髓。" —— 王争

为什么需要复杂度分析？

把代码跑一遍统计执行时间的方法叫事后统计法，有致命缺陷：

• 依赖测试环境（不同机器性能差异大）
• 依赖数据规模（数据量小测不出问题）
• 不同数据可能导致不同结果

因此需要不依赖测试数据、粗略估算执行效率的方法。

大 O 复杂度表示法

T(n) = O(f(n))

• T(n)：代码执行时间
• n：数据规模的大小
• f(n)：每行代码执行次数总和
• O 表示执行时间与 f(n) 成正比

大 O 不表示具体执行时间，而是代码执行时间随数据规模增长的变化趋势（渐进时间复杂度）。

时间复杂度分析三法则

常见复杂度量级

效率排序：O(1) > O(logn) > O(n) > O(nlogn) > O(n²) > O(n³) > O(2ⁿ) > O(n!)

空间复杂度

表示存储空间与数据规模之间的增长关系。常见的有 O(1)、O(n)、O(n²)。

四个复杂度分析维度（第 04 讲）

均摊分析要点

• 大部分情况下时间复杂度很低（如 O(1)），个别情况较高（如 O(n)）
• 操作之间存在连贯的时序关系
• 可将高复杂度操作均摊到低复杂度操作上
• 一般均摊时间复杂度等于最好情况时间复杂度（相当于最佳实践情况）

复杂度分析在面试中的重要性

"只掌握数据结构和算法的特点用法，而没学会复杂度分析，相当于只知道操作口诀，没掌握心法。心法了然于胸，才能无招胜有招。"

🧱 一、数组（第 05 讲）

定义

数组（Array）是一种线性表数据结构，用一组连续的内存空间，存储一组具有相同类型的数据。

三个关键字：

随机访问

寻址公式：

a[i]_address = base_address + i * data_type_size

• 通过下标随机访问：O(1)
• ⚠️ 纠错：数组的查找操作并不是 O(1)！排好序的数组用二分查找也是 O(logn)

多维数组寻址：

// 二维 m×n
a[i][j] = base_address + (i * n + j) * type_size

为什么数组从 0 开始编号？

效率原因（本质）：从 1 开始编号，寻址公式变为 base_address + (i - 1) * type_size，每次随机访问多一次减法指令。数组是最基础的数据结构，效率优化要做到极致。

历史原因：C 语言用 0 开始，Java、JavaScript 效仿以降低学习成本。并非所有语言都从 0 开始（Matlab 从 1 开始，Python 支持负数下标）。

本质理解："下标"最确切的定义是偏移（Offset）——a[0] = 偏移为 0 = 首地址。

插入和删除的低效性

插入优化技巧：如果数组仅作为存储集合（不关心顺序），可将第 k 位原数据移到末尾，新元素放入第 k 位 → O(1)。这也是快排中用到的思想。

删除优化技巧：先标记已删除，不立即搬移数据，等空间不足时再统一清理。这正是 JVM 标记-清除 GC 的核心思想！

容器 vs 数组

🧱 二、链表（第 06-07 讲）

数组 vs 链表核心对比

链表类型

1. 单链表（Singly Linked List）

• 结点（Node）：存储数据 + 后继指针 next
• 头结点（Head）：第一个节点，记录链表基地址
• 尾结点（Tail）：最后一个节点，next 指向 NULL

2. 循环链表（Circular Linked List）

尾结点的 next 指向头结点，形成环。适合处理具有环形结构特点的数据（如约瑟夫问题）。

3. 双向链表（Doubly Linked List）

每个节点有两个指针：next（后继）和 prev（前驱）。

空间换时间的经典应用。Java LinkedHashMap 底层用双向链表实现。

4. 双向循环链表

双向链表 + 循环链表的结合体。

链表实现 LRU 缓存淘汰算法

三种常见缓存淘汰策略：

LRU 实现思路（有序单链表）：

维护一个有序单链表，越靠近尾部的节点是越早被访问的：

1. 如果数据之前已在链表中：
   → 找到对应节点，从原位置删除
   → 插入到链表头部

2. 如果数据不在链表中：
   - 缓存未满 → 直接插入链表头部
   - 缓存已满 → 删除尾部节点，新数据插入头部

复杂度：O(n)（纯链表）。优化：引入散列表 → LinkedHashMap → 全部 O(1)。

写好链表代码的六大技巧（第 07 讲）

1. 理解指针/引用的含义：指针存储的是所指对象的内存地址
2. 警惕指针丢失：插入操作先让新节点指向后续节点，再修改前驱指针
3. 利用哨兵简化实现：哨兵（Sentinel）是解决边界问题的虚拟节点，消除头尾特殊处理
4. 重点留意边界条件：链表为空、只有一个节点、只有两个节点、处理头尾节点
5. 举例画图辅助思考：可视化指针操作
6. 多写多练，没有捷径

5 个必练的经典链表操作：单链表反转、链表中环的检测、两个有序链表合并、删除链表倒数第 n 个节点、求链表的中间节点。

🧱 三、栈（第 08 讲）

定义

栈是一种操作受限的线性表，只允许在一端插入和删除数据。后进先出（LIFO）。

• 顺序栈：用数组实现
• 链式栈：用链表实现

核心应用：浏览器前进后退

使用两个栈 X 和 Y：

当栈 X 为空 → 无页面可后退；栈 Y 为空 → 无页面可前进。中途打开新页面清空 Y，这正是浏览器的精妙之处。

其他经典应用

为什么要用栈而不是数组/链表？

数组或链表暴露了太多操作接口，使用灵活但也更不可控。栈是对特定场景的抽象——限制操作让逻辑更清晰安全。

🧱 四、队列（第 09 讲）

定义

队列是一种操作受限的线性表，只允许在队尾插入、在队头删除。先进先出（FIFO）。

顺序队列的关键问题：数据搬移

用数组实现时，head 和 tail 指针不断后移。当 tail 到末尾时，即使前面有空位也无法插入。

优化：不每次出队搬移，而是 tail==n && head!=0 时，入队时集中搬移一次。出队 O(1)，入队均摊 O(1)。

循环队列（重点）

将数组首尾相连成环，避免数据搬移。

队空判断：head == tail
队满判断：(tail + 1) % n == head  // 会浪费一个位置

// 入队
items[tail] = item;
tail = (tail + 1) % n;

// 出队
ret = items[head];
head = (head + 1) % n;

高级队列类型

核心应用：线程池中的请求排队

当线程池没有空闲线程时，两种处理策略：

链式 vs 顺序队列的选择：链表实现（无界队列）支持无限排队但响应时间不可控；数组实现（有界队列）大小有限但响应时间敏感系统适合。

核心思想：队列可应用在任何有限资源池中用于请求排队——数据库连接池、线程池、消息队列等。

🌲 五、跳表（第 17 讲）

核心思想

跳表 = 链表 + 多级索引，是"空间换时间"的经典应用。

二分查找依赖数组随机访问，无法直接用于链表。如果对有序链表建立多级索引，就能实现类似"二分"的查找效率——这就是跳表。

做法：每两个节点提取一个到上一级形成索引层，索引节点有 down 指针指向下一级对应节点。多层索引叠加 = 跳表。

时间复杂度：O(logn)

推导过程（每 2 个节点抽 1 个）：

设最高级有 2 个节点：n/(2ʰ) = 2 → h = log₂n - 1，跳表高度 = log₂n。

为什么每层最多遍历 3 个节点？ 在第 k 级找到 y < x < z，下降到第 k-1 级后，y 和 z 之间最多只有 3 个节点。

总时间复杂度 = O(3 × logn) = O(logn)，与二分查找一致。

空间复杂度：O(n)

索引节点总和：n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2 ≈ O(n)。

优化：每 3 个或 5 个节点抽 1 个做索引，空间降到约 n/2，仍为 O(n)。

实际中不必太在意——索引节点只存 key 和指针，数据节点可能存大对象，额外空间可忽略。

动态更新：随机函数维护平衡

不断插入而不更新索引 → 某两节点间数据越来越多 → 退化到 O(n)。

解决方案：通过随机函数生成值 K，将新节点插入到第 1 级到第 K 级的 K 级索引中。

为什么 Redis 用跳表实现有序集合而不用红黑树？

三大原因：

1. 区间查找效率高：O(logn) 定位起点，在原始链表顺序遍历
2. 实现更简单：比红黑树的旋转、变色好懂好写
3. 更加灵活：可通过改变索引构建策略，灵活平衡效率和内存消耗

🔑 六、散列表 / 哈希表（第 18-20 讲）

定义

散列表 = 数组 + 散列函数，本质是数组的扩展。

利用数组按下标随机访问 O(1) 的特性，通过 hash(key) 将 key 映射为数组下标，存储键值对（key-value）。

散列函数设计要求

⚠️ 第三点几乎无法完美实现，MD5、SHA、CRC 也存在冲突。散列冲突不可避免。

散列冲突的两种解决方法

方法一：开放寻址法（Open Addressing）

冲突了就去找下一个空闲位置。

删除时不能直接置空，要标记为 deleted，否则查找时会误判"不存在"。

方法二：链表法（Chaining）

每个数组槽位（桶/bucket）指向一条链表。冲突元素追加到对应链表中。插入 O(1)，查找/删除 O(k)，k = n/m。

装载因子（Load Factor）

装载因子 = 填入表中的元素个数 / 散列表的长度

• 越大 → 空闲越少 → 冲突越多 → 性能越差
• 一般经验：装载因子 > 0.7 时考虑扩容

工业级散列表（第 19 讲）

核心要求：快速查询插入删除 + 内存占用合理 + 性能稳定（极端不退化到 O(n)）。

动态扩容

查询时：先查新表，再查老表。

HashMap 参数（JDK）

// HashMap 散列函数
int hash(Object key) {
    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (capacity - 1);
}

开放寻址法 vs 链表法

散列表 + 链表组合（第 20 讲）

散列表的天然缺陷：数据被散列函数打乱后无规律存储，无法快速有序遍历。

经典组合：

🌳 七、二叉树（第 23-24 讲）

基本概念

特殊二叉树

满二叉树（Full Binary Tree）：叶子节点全在最底层，除叶子外每个节点都有左右两个子节点。

完全二叉树（Complete Binary Tree）：

• 叶子节点在最底下两层
• 最后一层的叶子节点都靠左排列
• 除最后一层，其他层节点数达到最大
• ⚠️ 满二叉树是完全二叉树的特殊情况

存储方式

链式存储（最常用）

class Node {
    int data;
    Node left;   // 左子节点
    Node right;  // 右子节点
}

数组顺序存储（适合完全二叉树）

假设根节点下标 i = 1：

• ✅ 完全二叉树用数组存储最省内存（无需额外指针）
• ❌ 非完全二叉树会浪费大量数组空间
• 💡 堆（Heap）就是完全二叉树，最常用的存储方式就是数组

二叉树的遍历

前、中、后序表示的是「节点本身」与「左右子树」之间的打印顺序：

时间复杂度：每个节点最多访问两次，O(n)。

二叉查找树（BST, Binary Search Tree）

定义：树中任意一个节点，左子树中每个节点的值 < 该节点的值 < 右子树中每个节点的值。

核心操作

删除操作的三种情况

💡 取巧方法：不真正删除，标记为"已删除"（Lazy Deletion）。省事但浪费内存。

支持重复数据

时间复杂度

BST 的插入、删除、查找时间复杂度与树的高度成正比 = O(height)

• 完全二叉树高度 ≤ log₂n → 最佳 O(logn)
• 退化为链表 → 最差 O(n)
• 因此需要平衡二叉查找树来避免退化

BST vs 散列表

两者各有优势，互补而非替代。

🌳 八、红黑树（第 25-26 讲）

什么是平衡二叉查找树？

严格定义：任意一个节点的左右子树高度相差不能大于 1。AVL 树是严格符合该定义的平衡二叉查找树。

红黑树是不严格符合平衡定义的平衡二叉查找树，只需要满足 5 条规则。

红黑树的 5 条规则

为什么红黑树是近似平衡的？

• 抹掉所有红色节点 → "黑树"高度 ≈ log₂n
• 红色节点不连续 → 每层黑色间最多夹一层红色
• 红黑树高度 ≈ 2log₂n，仅比 AVL（log₂n）高一倍

为什么工程中更爱用红黑树而不用 AVL？

• AVL 高度平衡，查询效率略高
• 但插入/删除时 AVL 需要频繁调整，维护成本高
• 红黑树是性能和维护成本的折中 → 工业首选
• Treap、Splay Tree 可能极端退化，不适合对单次操作敏感的场景

两个核心操作：左旋与右旋

旋转前后 BST 性质不变。

插入操作的平衡调整

规定：新插入的节点必须是红色，且放在叶子位置。

其他情况分为 CASE 1~3：

学习建议

"对于绝大部分开发工程师来说，这辈子你可能都用不着亲手写一个红黑树。" —— 王争

三点学习建议：

1. 像玩魔方一样：记住固定步骤，不必深究正确性证明
2. 盯住关注节点：调整过程中关注节点不断变化
3. 插入简单删除复杂：删除分两次调整（先保证黑节点数，再消除相邻红节点）

📦 九、堆（第 28-29 讲）

定义

堆是一种特殊的树，满足两个条件：

1. 堆是一个完全二叉树
2. 堆中每个节点的值都必须 ≥ 或 ≤ 其子树中每个节点的值

⚠️ 与 BST 的区别：BST 左<根<右，用于查找；堆左右无大小之分，主要用于排序和优先级。

堆的存储

用数组存储（完全二叉树的优势）：

假设数组从下标 1 开始：

左子节点 = i * 2
右子节点 = i * 2 + 1
父节点   = i / 2

堆的核心操作（O(logn)）

插入元素 — 自下往上堆化

新元素放数组末尾 → 与父节点比较 → 不满足堆特性则交换 → 重复直到满足。

删除堆顶 — 自上往下堆化

最后一个节点放到堆顶 → 从堆顶开始与较大（或较小）的子节点交换 → 重复直到满足。

堆排序 O(nlogn)

分两步：

第一步：建堆（O(n)）

从 n/2 到 1 的非叶子节点，依次自上往下堆化。

第二步：排序（O(nlogn)）

public static void sort(int[] a, int n) {
    buildHeap(a, n);       // 建堆 O(n)
    int k = n;
    while (k > 1) {
        swap(a, 1, k);     // 堆顶与末尾交换
        --k;
        heapify(a, k, 1);  // 重新堆化 O(logn)
    }
}

特点：原地排序（O(1) 额外空间）、不稳定排序、时间复杂度很稳定。

为什么快排比堆排序更受欢迎？

堆的三大应用（第 29 讲）

1. 优先级队列

堆是优先级队列的天然实现。出队顺序按优先级而非 FIFO。

场景：合并有序小文件（100 个有序文件合并为 1 个，用小顶堆每次取最小）；高性能定时器（小顶堆存任务，堆顶即最早执行的任务，无需轮询）。

2. 求 Top K

静态数据：维护大小为 K 的小顶堆，遍历数组，元素 > 堆顶则替换堆顶并堆化。O(nlogK)。

动态数据（实时）：始终维护大小为 K 的小顶堆，新数据到即与堆顶比较决定是否入堆。

3. 求中位数 / 百分位数

维护两个堆：

中位数：大顶堆堆顶即为中位数。 99% 响应时间：大顶堆存 99% 数据，堆顶即为 99 百分位值。

面试题：10 亿搜索关键词求 Top 10（单机 1GB 内存）

1. 哈希分片：10亿关键词通过哈希分到10个文件（每个~1亿）
2. 统计频率：每个文件用散列表统计词频
3. Top10堆：每个文件用大小为10的小顶堆求Top10
4. 合并：10个Top10（共100个词）再求一次Top10

🕸️ 十、图（第 30-31 讲）

基本概念

图是一种非线性数据结构，由顶点（Vertex） 和边（Edge） 组成。

度：与该顶点相连的边的条数（无向图）。 入度/出度：指向该点的边数 / 从该点出发的边数（有向图）。

图的存储方式

邻接矩阵（Adjacency Matrix）

底层是二维数组 A[i][j]：

• 无向图：有边则 A[i][j] = A[j][i] = 1
• 有向图：i→j 有边则 A[i][j] = 1
• 加权图：存储权重值

邻接表（Adjacency Table）

每个顶点对应一个链表，存储与该顶点相连的顶点。

优化：链表替换为红黑树、跳表、散列表等高效动态数据结构。

逆邻接表

用于有向图，存储"谁关注了我"，常用于社交网络双向查询。

广度优先搜索（BFS）

思路：地毯式层层推进，先查找离起点最近的，然后是次近的。

• 辅助数据结构：队列
• BFS 找到的路径是 s 到 t 的最短路径（边数最少）
• 时间复杂度（邻接表）：O(V + E)，对于连通图简化为 O(E)
• 空间复杂度：O(V)（visited + queue + prev）

深度优先搜索（DFS）

思路：沿一个方向走到底，走不通则回溯到上一个分岔口继续尝试。

• 辅助数据结构：递归 + 回溯（递归调用栈）
• DFS 找到的路径不一定是最短路径
• 时间复杂度（邻接表）：O(E)（每条边最多被访问两次）
• 空间复杂度：O(V)（visited + prev + 递归栈）

BFS vs DFS

🔤 十一、Trie 树（第 35 讲）

定义

Trie 树（字典树） 是专门处理字符串匹配的树形结构，利用字符串之间的公共前缀来合并重复部分。

别名字典树（Dictionary Tree）、前缀树（Prefix Tree）。

核心思想

将 6 个字符串 how, hi, her, hello, so, see 构建成 Trie 树：

          root
         /    \
        h      s
       / \      \
      o   i      o
     /     \      \
    w       r      e
    |       |      |
   (how)   e→(her) e→(see)
            |
            l
            |
            l
            |
            o→(hello)

• 根节点不包含信息
• 每个节点表示字符串中的一个字符
• 红色节点（isEndingChar = true）表示存在完整字符串

时间复杂度

内存消耗与优化

Trie 树非常耗内存。每个节点存储 26 长度的数组，每个元素 8 字节指针：

• 每个节点额外开销：26 × 8 = 208 字节
• 如果包含大写字母、数字、中文，需求更大

优化方案：有序数组（二分查找）、跳表、散列表、红黑树取代子节点数组；缩点优化（单子节点合并）。

Trie 树 vs 散列表/红黑树

搜索引擎关键词提示原理

1. 将热门搜索关键词库构建成 Trie 树
2. 用户输入字符时，将该字符作为前缀子串在 Trie 树中匹配
3. 返回以该前缀开头的所有关键词展示在提示框中

实际工程挑战：中文编码、关键词排序（热门度）、拼写纠错。

🌳 十二、B+ 树（第 48 讲）

问题背景

数据库索引需要同时满足：单值查找 + 区间查找 + 高效 + 省内存。

从二叉树到 B+ 树的演化

1. 改造 BST 支持区间查找：节点不存数据只做索引，叶子节点用链表串联
2. 解决内存占用：索引存磁盘 → 但磁盘 IO 极慢（毫秒 vs 纳秒）→ 树的高度 = IO 次数 → 优化核心：降低高度
3. 多叉树降低高度：二叉树存 16 个数据 → 高度 4 → 4 次 IO。五叉树 → 高度 2 → 2 次 IO。100 叉树存 1 亿数据 → 高度仅 3 → 最多 3 次 IO！
4. m 的选择：让每个节点大小正好 = 一页（4KB），读取一个节点只需一次 IO

B+ 树的核心特点

1. 每个节点子节点数：m/2 ≤ n ≤ m（根节点例外）
2. 非叶子节点只存索引，不存数据（类似跳表）
3. 叶子节点用双向链表串联 → 支持区间查找和升降序
4. 根节点常驻内存，其他存磁盘
5. 叶子节点存的是键值 + 数据地址（或完整数据）

插入与删除

• 插入 → 节点分裂：子节点超 m 个→一分为二→可能级联分裂至根
• 删除 → 节点合并：子节点< m/2 →与相邻兄弟合并→合并后超 m 再分裂

B 树 vs B+ 树

💾 十三、位图 & 布隆过滤器（第 45 讲）

问题场景

10 亿个 URL 需要判重，散列表方案至少需 100GB+ 内存（不可接受）。需要更省内存的方案。

位图（BitMap）

原理：用1 个二进制位（bit） 表示一个数字是否存在。数字本身作为数组下标。

public class BitMap {
    private char[] bytes;  // char占2字节=16bit

    public void set(int k) {
        int byteIndex = k / 16;
        int bitIndex = k % 16;
        bytes[byteIndex] |= (1 << bitIndex);  // 置1
    }

    public boolean get(int k) {
        int byteIndex = k / 16;
        int bitIndex = k % 16;
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;
    }
}

• ✅ 访问效率极高，内存节省（1 亿个数约 12MB）
• ❌ 数字范围很大时内存反增（1~10 亿需 120MB）

布隆过滤器（Bloom Filter）

核心思想：

• 固定大小位图
• 用 K 个哈希函数将每个数据映射到 K 个位图位置
• 插入：K 个位置全部置 1
• 查询：K 个位置全为 1 → 可能存在；任意为 0 → 一定不存在

False is always false. True is maybe true.

为什么比散列表快？ 布隆过滤器是 CPU 密集型（多次哈希计算），散列表方案是内存密集型（大量字符串匹配），CPU 计算通常比内存访问更快。

空间对比（10 亿 URL）：

实际应用

1. 爬虫 URL 去重（稍许误判可容忍）
2. Redis 缓存穿透防护：先过滤不存在的数据
3. 大型网站 UV 统计
4. 垃圾邮件过滤
5. 短网址冲突检测

相关实现

• Java：BitSet（位图）、Google Guava BloomFilter
• Redis：BitMap 位图类
• 自动扩容：数据量超阈值 → 新建位图（查询需查多个位图）

🎯 核心总结：数据结构全景图

数据结构全景
├── 线性表
│   ├── 数组 ──── 连续内存，随机访问O(1)，插入/删除O(n)
│   ├── 链表 ──── 离散内存，插入/删除O(1)，随机访问O(n)
│   ├── 栈 ──── LIFO，浏览器前进后退，函数调用栈，括号匹配
│   └── 队列 ──── FIFO，线程池排队，消息队列，资源池
│
├── 哈希结构
│   └── 散列表 ──── O(1)查找，空间换时间，装载因子+冲突解决
│       ├── 拉链法 → HashMap (Java)
│       └── 开放寻址 → ThreadLocalMap (Java)
│
├── 树结构
│   ├── 二叉树 ──── 遍历 O(n)，三种方式（前中后序）
│   ├── 二叉查找树 ──── 查找 O(logn)~O(n)，支持有序输出
│   ├── 红黑树 ──── 工程首选平衡BST，高度≈2log₂n
│   ├── 堆 ──── 完全二叉树+数组存储，TopK O(nlogK)，中位数
│   ├── B+树 ──── 多叉树，MySQL索引核心，≤3次IO查1亿数据
│   └── Trie树 ──── 前缀树，搜索引擎补全 O(k)，空间换时间
│
├── 概率/索引结构
│   └── 跳表 ──── 链表+多级索引，O(logn)查找，Redis ZSet核心
│
├── 图结构
│   └── 图 ──── 邻接矩阵/邻接表存储，BFS(最短路径) + DFS(回溯)
│
└── 大数据结构
    ├── 位图 ──── 1bit标记存在，1亿数≈12MB
    └── 布隆过滤器 ──── K个哈希+位图，判定不存在100%准确

🧠 设计思想总结