面试追问地图
| 主问题 | 必讲关键点 | 下一层追问 |
|---|---|---|
| 数组/链表 | 连续内存、随机访问、插入删除 | 缓存局部性、扩容 |
| 栈/队列 | LIFO/FIFO | 单调栈、优先队列、阻塞队列 |
| 哈希表 | hash、桶、冲突、扩容 | 负载因子、开放寻址 vs 链地址 |
| 红黑树/AVL | 平衡程度、旋转、复杂度 | 为什么工程上常选红黑树 |
| B/B+树 | 多路、磁盘页、叶子链表 | 为什么数据库索引使用 B+树 |
| 跳表 | 多层索引、概率平衡 | 与红黑树/B+树对比 |
| 时间轮 | 环形数组、O(1) 增删 | 轮次 vs 层级、Netty/Kafka 应用 |
| 堆/Top-K | 完全二叉树、上浮下沉 | 大数据流、K 很大时如何选 |
| 排序 | 时间、空间、稳定性 | 数据规模、近乎有序、外部排序 |
| 二分 | 单调性和边界 | 左闭右闭/左闭右开模板 |
| DFS/BFS | 栈/队列、访问标记 | 最短路、回溯、空间爆炸 |
| 动态规划 | 状态、转移、初始化、遍历顺序 | 与贪心/回溯区别、空间压缩 |
| 前缀树 | 多叉树、共享前缀 | 自动补全、AC 自动机、空间优化 |
| LRU/布隆过滤器 | 哈希+双向链表、位图+哈希 | 热点数据、缓存污染、误判率 |
算法题除了写出代码，还要主动说明不变量、边界条件、复杂度和可替代方案。
一、数据结构与算法
数组 vs 链表
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续 | 分散 |
| 随机访问 | O(1) | O(n) |
| 插入/删除 | O(n) 需移动 | 已定位后 O(1)，找位置 O(n) |
| 缓存命中率 | 高 | 低 |
| 适用场景 | 频繁访问 | 频繁插入删除 |
数组查询 O(1) 的原因 ：连续内存 + 相同类型，通过 基地址 + 下标 * 元素大小 直接计算内存地址。
通用概念：连续内存带来的局部性让数组在实践中常胜过复杂度更优的链表。
栈 vs 队列
- 栈 ：LIFO（后进先出），push/pop 都在栈顶，用于函数调用、表达式求值
- 队列 ：FIFO（先进先出），队尾插入队首删除，用于任务调度、BFS
常见队列类型
- 顺序队列 ：连续存储，可能假溢出
- 链式队列 ：链表实现，动态大小
- 循环队列 ：首尾相接，避免假溢出
- 双端队列 ：两端都可插入/删除
- 优先级队列 ：按优先级出队，通常用堆实现
用两个栈实现队列
一个栈 stackPush 负责入队，一个栈 stackPop 负责出队。出队时若 stackPop 为空，将 stackPush 全部倒入 stackPop。入队均摊 O(1)，出队均摊 O(1)。
平衡二叉树
左右子树高度差不超过 1。目的是避免 BST 退化为链表（O(n)），维持 O(log n) 操作复杂度。
红黑树性质
- 节点红色或黑色
- 根节点黑色
- 叶子节点（NIL）黑色
- 红色节点的子节点必须黑色
- 根到叶子的每条路径黑色节点数相同
最长路径不超过最短路径 2 倍，增删查 O(log n)。
红黑树 vs AVL 树
| 操作 | AVL | 红黑树 |
|---|---|---|
| 查询 | 更快（严格平衡） | 稍慢（弱平衡） |
| 插入/删除 | 慢（旋转多） | 快（最多 2 次旋转 + 变色） |
实际应用：Java TreeMap/TreeSet 用红黑树；epoll 用红黑树保存 socket。
跳表
多层有序链表，通过索引加速查找。增删查平均 O(log n)。Redis ZSet 用跳表实现，层高随机化细节与「为什么不用 B+树」见 Redis。
时间轮
是什么：环形数组 + 链表，专为海量定时任务设计。数组每格代表一个时间刻度（如 100ms），任务按到期时间取模挂到对应格子的链表上；指针每 tick 前进一格，执行该格到期任务。
为什么这么设计：
| 方案 | 添加 | 取最近到期 | 适用 |
|---|---|---|---|
| JDK Timer / DelayQueue（小顶堆） | O(log n) | O(1) | 任务量小 |
| 时间轮 | O(1) | O(1)（tick 驱动） | 十万级+定时任务（连接超时、重试） |
超出一轮范围的任务怎么办：
- 轮次法（Netty
HashedWheelTimer）：任务记 rounds，指针扫到时 rounds > 0 则减一跳过 - 层级时间轮（Kafka）：秒轮转完进分钟轮，像水表刻度，溢出任务降级到上层轮
常见追问
- 精度和空间怎么取舍？→ tick 越小精度越高但空转越多；Kafka 用 DelayQueue 推进层级时间轮，避免空转。
- 实际应用？→ Netty 连接超时检测、Kafka 延迟操作、Dubbo 重试；业务层的订单超时取消方案对比见系统设计。
B+ 树 vs B 树 vs 红黑树
| 特性 | 红黑树 | B 树 | B+ 树 |
|---|---|---|---|
| 节点容量 | 1 个键值 | 多个键值 | 非叶存键，仅叶存值 |
| 分支数 | 二叉 | 多叉 | 多叉，叶子链表连接 |
| 数据存储 | 所有节点 | 所有节点 | 仅叶节点 |
| 查找 | 查到即返回 | 查到即返回 | 必须到叶子 |
| 范围查询 | 差 | 差（中序遍历） | 优（叶子链表） |
B+ 树是数据库索引首选 ：树高更低（磁盘 I/O 少），叶子链表支持高效范围查询。
通用概念：这三者不是三个独立结构，而是同一取舍在不同介质定价下的三个解——树。红黑树的旋转次数摊还后是常数，这正是它在内存里胜过 AVL 的原因。
堆
完全二叉树，大顶堆/小顶堆。用数组存储，节点 i 的左右子节点为 2i+1、2i+2。
堆排序 ：建堆 O(n) + 排序 O(n log n)，原地排序但不稳定。
前缀树（Trie）
利用公共前缀减少比较次数。根不含字符，每节点子节点字符不同。用于搜索引擎自动补全、拼写检查、路由表最长前缀匹配。
LRU 缓存淘汰
哈希表 + 双向链表 。访问时将节点移到链表头部，淘汰时删除尾部节点。插入/查找/删除均 O(1)。
布隆过滤器
位数组 + 多个哈希函数。判断元素是否在集合中：
- 返回不存在 -> 一定不存在
- 返回存在 -> 可能存在 （有误判率）
时间复杂度 O(k)，k 为哈希函数个数。适用于 IP 黑名单、缓存穿透防护等。
哈希表冲突解决
- 链地址法 ：每个桶挂链表，JDK 1.8+ HashMap 链表长度 >= 8 且数组 >= 64 时转红黑树
- 开放寻址法 ：线性探测/二次探测/双重哈希，ThreadLocalMap 用此方式
负载因子 ：元素数/桶数，Java HashMap 默认 0.75
排序算法复杂度
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 快排 | O(n log n) | O(n^2) | O(n log n) | O(log n) | 不稳定 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
快排原理
分治策略：选基准 -> partition 分成左右两部分 -> 递归排序。 最坏 O(n^2) ：每次选到最大/最小值（已有序数组），优化：随机选基准或三数取中。
归并排序原理
分治：从中间分开 -> 递归排序两半 -> 合并两个有序数组。 最坏 O(n log n)，稳定，需要 O(n) 额外空间。适用于外部排序、链表排序。
排序稳定性
相同关键字的元素在排序后保持原始相对顺序。归并、冒泡、插入稳定；快排、堆排、选择不稳定。
外部排序（大数据排序）
- 部分排序 ：拆分文件，每块内存排序（快排），生成有序”顺段”
- 归并 ：多路归并合并顺段，借助败者树减少归并层数降低 I/O
Top-K 问题（找最大前 K 个）
- K 小 ：最小堆，O(N log K)
- K 大 ：快速选择，平均 O(N)
- 简单方案 ：全排序 O(N log N)
二分查找
对有序数组 O(log n) 查找。
常见坑 ：
- 防止溢出：
mid = left + (right - left) / 2 - 边界写法统一：闭区间
[left, right]用left <= right，左闭右开用left < right - 变体题：第一个等于、最后一个等于、第一个大于等于等
DFS vs BFS
| 维度 | DFS | BFS |
|---|---|---|
| 实现 | 递归/栈 | 队列 |
| 空间 | O(h) 树高 | O(w) 最大宽度 |
| 最短路径 | 不能 | 能（无权图） |
| 适用 | 全排列/子集/回溯 | 层序遍历/最短路径 |
二叉树遍历
DFS 三种 ：前序（根左右）、中序（左根右，BST 中序=升序）、后序（左右根） BFS 一种 ：层序遍历（队列实现）
链表操作
反转链表 ：迭代（三指针 prev/curr/next）或递归。
判断环/找环入口 ：快慢指针。相遇后一个指针回到头部，两指针同步走，再次相遇处即环入口。
动态规划
将大问题拆为重叠子问题，记录子问题解避免重复计算。
两个特征 ：最优子结构、重叠子问题。 解题套路 ：定义状态 -> 状态转移方程 -> 初始化 -> 遍历顺序
经典题 ：斐波那契、背包问题、LCS、LIS、编辑距离、打家劫舍、零钱兑换。
贪心 vs 动态规划
贪心：每步选当前最优，不保证全局最优（如找零钱特定面值可贪心）。 DP：枚举所有子问题解，一定得到最优解但更慢。
时间/空间复杂度分析
常见等级：O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
规则 ：只看最高阶、忽略常数系数、加法取最大、乘法相乘。