算法与数据结构面试题

Java大神2026/4/20大约 62 分钟高频面试题算法与数据结构面试题

常用数据结构：数组、链表、栈、队列、哈希表、树、堆、图

好的面试官，我来梳理一下我对这些常用数据结构的理解，我会从核心特性、Java 实现、时间复杂度、典型场景这几个面试最关注的维度展开，尽量讲得清晰有条理。

核心数据结构总览

所有数据结构本质上都是为了解决 "如何高效存储和操作数据"的问题，核心差异体现在增删改查的时间复杂度和内存占用 上。

逐个拆解（面试高频考点）

1. 数组（Array）✅

int[] arr = new int[10];          // 固定长度
List<Integer> list = new ArrayList<>(); // 动态数组

核心本质：连续的内存空间，存储相同类型的元素
Java 实现：ArrayList（动态数组，默认容量 10，扩容 1.5 倍）
核心优势：随机访问 O (1)（通过下标直接计算内存地址），缓存友好（局部性原理）
核心劣势：插入 / 删除 O (n)（需要移动元素），容量固定（动态数组扩容有拷贝开销）
适用场景：频繁查询、少插入删除、数据量已知的场景

图形化示意（逻辑内存布局）：

索引: [0] [1] [2] [3] ...
值:    10  20  30  40  ...

✅ 场景：频繁读、按索引访问，比如配置列表、固定大小的缓冲区。

2. 链表（LinkedList）🔗

// Java 内置双向链表
LinkedList<String> linkedList = new LinkedList<>();

核心本质：非连续内存空间，节点存储 "数据 + 指针"
分类：单链表、双链表、循环链表
Java 实现：LinkedList（双链表，同时实现了 List 和 Deque 接口）
核心优势：已知前驱节点时，插入 / 删除 O (1)，容量动态无上限
核心劣势：随机访问 O (n)，缓存不友好，额外指针开销大
适用场景：频繁插入删除、查询少、数据量不确定的场景

双向链表结构：

null ← [prev|data|next] ⇄ [prev|data|next] → null

✅ 场景：频繁增删（尤其是头尾），LRU 缓存淘汰里就用 LinkedHashMap（内部的链表）。

数组 vs 链表核心对比表（面试必问）

特性	数组（ArrayList）	链表（LinkedList）
内存布局	连续	非连续
随机访问	O(1) ✅	O(n) ❌
头部插入 / 删除	O(n) ❌	O(1) ✅
尾部插入 / 删除	O(1) ✅	O(1) ✅
中间插入 / 删除	O(n) ❌	O (1) ✅（已知前驱）
缓存命中率	高 ✅	低 ❌
内存浪费	扩容预留空间	指针额外开销

3. 栈（Stack）📚

Deque<Integer> stack = new ArrayDeque<>(); // 推荐，不要用旧 Stack 类
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2

核心本质：后进先出（LIFO），只能在栈顶进行操作
Java 实现：不推荐使用 Stack 类（继承 Vector，线程安全但效率极低），推荐用ArrayDeque（双端队列实现栈，性能最好）
核心操作：push（入栈 O (1)）、pop（出栈 O (1)）、peek（查看栈顶 O (1)）
适用场景：括号匹配、函数调用栈、表达式求值、逆序输出、深度优先搜索（DFS）

示意图：

| 3 | ← 栈顶 (push/pop 处)
| 2 |
| 1 |
+---+

4. 队列（Queue）🚶

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
String head = queue.poll(); // "A"

核心本质：先进先出（FIFO），队尾入队，队头出队
Java 实现分类：
- 非阻塞队列：ArrayDeque（推荐，数组实现）、LinkedList
- 阻塞队列：ArrayBlockingQueue、LinkedBlockingQueue（线程安全，用于生产者消费者模型）
- 优先级队列：PriorityQueue（堆实现，后面单独讲）
适用场景：消息队列、任务调度、广度优先搜索（BFS）、限流

队列示意：

入队 → [ 3 | 2 | 1 ] → 出队

5. 哈希表（Hash Table）🔑

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
int val = map.get("apple");

核心本质：通过哈希函数将 "键" 映射到数组索引，实现键值对的快速存储
哈希冲突解决：
- 链地址法：Java HashMap 采用（数组 + 链表 + 红黑树）
- 开放寻址法：Java ThreadLocalMap 采用
Java 实现：
- HashMap：非线程安全，最常用，允许 null 键值
- ConcurrentHashMap：线程安全，高并发场景推荐
- LinkedHashMap：有序（插入顺序 / 访问顺序）
- TreeMap：有序（自然排序 / 自定义排序，红黑树实现）
核心考点（面试 100% 问）：
- HashMap 默认容量 16，负载因子 0.75，扩容 2 倍
- 链表长度≥8 且数组长度≥64 时，链表转红黑树；红黑树节点≤6 时转回链表
时间复杂度：平均 O (1)，最坏 O (n)（哈希冲突严重时）
适用场景：快速查找、去重、频率统计、缓存

HashMap 结构：

桶数组
[0] → (key1,val1) → (key2,val2)  // 链表
[1] → 红黑树节点...
[2] → null
...

6. 树（Tree）🌳

// TreeMap 红黑树实现
TreeMap<Integer, String> treeMap = new TreeMap<>();

核心本质：层次化的非线性结构，一个根节点，多个子节点
常见类型及 Java 实现：
- 二叉树：每个节点最多 2 个子节点
- 二叉搜索树（BST）：左子树 < 根 < 右子树，中序遍历有序
- 红黑树：近似平衡二叉搜索树，Java TreeMap/TreeSet 底层实现
遍历方式：
- 深度优先（DFS）：前序、中序、后序
- 广度优先（BFS）：层序遍历
适用场景：有序数据存储、范围查询、数据库索引、文件系统

BST 示意：

      8
     / \
    3   10
   / \    \
  1   6    14

7. 堆（Heap）⛰️

PriorityQueue<Integer> minHeap = new PriorityQueue<>();          // 小顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

核心本质：完全二叉树，满足堆性质：
- 大顶堆：父节点值 ≥ 所有子节点值
- 小顶堆：父节点值 ≤ 所有子节点值
Java 实现：PriorityQueue（默认小顶堆，可通过Comparator实现大顶堆）
核心操作：插入 O (logn)、删除堆顶 O (logn)、查看堆顶 O (1)
适用场景：TopK 问题、优先级任务调度、堆排序、中位数查找

小顶堆示意图（数组视角）：

     1
   /   \
  3     5
 / \   /
7   8 9
存储: [1,3,5,7,8,9]

8. 图（Graph）🕸️

Java 无内置图库，常自己实现：

// 邻接表
Map<Integer, List<Integer>> graph = new HashMap<>();
// 邻接矩阵
int[][] matrix = new int[n][n];

核心本质：顶点 + 边组成的非线性结构，用于表示实体间的关系
存储方式：
- 邻接矩阵：适合稠密图，空间复杂度 O (n²)
- 邻接表：适合稀疏图，空间复杂度 O (n+e)
核心操作：
- 遍历：深度优先（DFS，栈实现）、广度优先（BFS，队列实现）
- 常见算法：最短路径（Dijkstra）、拓扑排序、最小生成树
适用场景：社交网络、地图导航、依赖关系分析、推荐系统

有向图邻接表：

0 → [1,2]
1 → [3]
2 → [3]
3 → []

所有数据结构时间复杂度速查表（面试必背）

数据结构	访问	查找	插入	删除	Java 代表类
数组	O(1)	O(n)	O(n)	O(n)	`ArrayList`
链表	O(n)	O(n)	O(1)	O(1)	`LinkedList`
栈	O(n)	O(n)	O(1)	O(1)	`ArrayDeque`
队列	O(n)	O(n)	O(1)	O(1)	`ArrayDeque`/`LinkedList`
哈希表	-	O(1)	O(1)	O(1)	`HashMap`
二叉搜索树	O(logn)	O(logn)	O(logn)	O(logn)	`TreeMap` (红黑树)
红黑树	O(logn)	O(logn)	O(logn)	O(logn)	`TreeMap` (红黑树)
堆	O(1)	O(n)	O(logn)	O(logn)	`PriorityQueue`

📌 注：哈希表为平均复杂度；堆搜索任意元素 O(n)，但查顶是 O(1)。

面试总结加分项 💯

选择数据结构的核心原则是：根据业务中最频繁的操作来选择

要快速随机访问 → 数组
要频繁插入删除 → 链表
要先进先出 → 队列
要后进先出 → 栈
要快速查找键值对 → 哈希表
要有序且支持范围查询 → 红黑树 / TreeMap
要快速获取最大值 / 最小值 → 堆

排序算法：快速排序、归并排序、堆排序（原理+复杂度+稳定性）

面试官您好！接下来我将从核心原理、复杂度分析、稳定性三个维度，为您详细讲解快速排序、归并排序和堆排序这三种面试必问的排序算法。

快速排序（Quick Sort）⭐

一句话：选基准，分左右，再递归。

核心思想：分治思想 + 基准值划分。选择一个基准元素，将数组分为 "小于基准" 和 "大于基准" 两部分，递归排序子数组。

[ 3, 5, 1, 7, 2, 8, 4 ]
        ↓ 选基准 pivot = 4
[ 3, 1, 2 ]  4  [ 5, 7, 8 ]   ← partition 分区
    ↓ 递归排序        ↓ 递归排序
[ 1, 2, 3 ]  4  [ 5, 7, 8 ]  → 完成 🎉

核心是 partition 函数：把小于 pivot 的放左边，大于的放右边，最后把 pivot 放到中间正确位置。这个过程像“挖坑填数”，左右指针交替扫描。

算法流程

关键指标

指标	最好情况	平均情况	最坏情况
时间复杂度	O(n log n)	O(n log n)	O(n²)
空间复杂度	O(log n)	O(log n)	O(n)
稳定性	❌ 不稳定	-	-

面试关键点

最坏情况触发：数组已排序 / 逆序，且每次选第一个 / 最后一个元素作为基准
优化方向：随机选基准、三数取中法、小数组用插入排序
Java 实现：双指针法（左右指针向中间扫描，交换不符合条件的元素）

归并排序（Merge Sort）💡

经典分治：先切到不能再切，再两两有序合并。

核心思想：分治思想 + 有序合并。将数组递归拆分为两半，分别排序后再合并两个有序数组。

       [38, 27, 43, 3, 9, 82, 10]
            ↙                ↘
    [38, 27, 43, 3]     [9, 82, 10]
       ↙      ↘           ↙      ↘
   [38,27]  [43,3]     [9,82]   [10]
    ↙  ↘    ↙  ↘      ↙  ↘
 [38][27] [43][3]   [9][82] [10]
    ↘  ↙    ↘  ↙      ↘  ↙    |
   [27,38]  [3,43]   [9,82] [10]
       ↘      ↙           ↘   ↙
    [3,27,38,43]     [9,10,82]
            ↘        ↙
      [3,9,10,27,38,43,82]   ✅

合并时用双指针比较两个有序子数组，谁小取谁，像拉链一样并起来 🔗

算法流程

关键指标

指标	最好情况	平均情况	最坏情况
时间复杂度	O(n log n)	O(n log n)	O(n log n)
空间复杂度	O(n)	O(n)	O(n)
稳定性	✅ 稳定	-	-

面试关键点

唯一稳定的 O (n log n) 排序算法
缺点：需要额外的 O (n) 空间存储临时数组
变种：原地归并排序（空间复杂度 O (1)，但实现复杂）
应用场景：外部排序（数据量超过内存容量时）

堆排序（Heap Sort）🏔️

核心思想：利用堆这种数据结构的性质。构建大顶堆（升序）或小顶堆（降序），每次取出堆顶元素与最后一个元素交换，再调整堆。

把数组看成完全二叉树，利用大顶堆的性质：父节点 ≥ 子节点。

过程分两大步：

建堆（heapify 整个数组）—— 从最后一个非叶节点开始向下调整 O(n)
排序 —— 反复把堆顶（最大值）与末尾元素交换，然后“沉”下去调整，缩小堆范围

初始数组: [4, 10, 3, 5, 1]
建大顶堆: 
      10
     /  \
    5    3
   / \
  4   1
数组形式: [10, 5, 3, 4, 1]

第1次交换堆顶与末尾:
[1, 5, 3, 4 | 10]   ← 10 就位
重新调整堆:
      5
     / \
    4   3
   /
  1
[5, 4, 3, 1 | 10]
...重复直到全部有序 ✨

算法流程

关键指标

指标	最好情况	平均情况	最坏情况
时间复杂度	O(n log n)	O(n log n)	O(n log n)
空间复杂度	O(1)	O(1)	O(1)
稳定性	❌ 不稳定	-	-

面试关键点

原地排序，空间复杂度最优 O (1)
构建堆时间：O (n)，调整堆时间：O (log n)
缺点：不稳定，且缓存命中率低（跳跃式访问元素）
应用场景：优先队列、Top K 问题

三大排序算法综合对比 📊

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不稳定	大多数场景，数据量较大
归并排序	O(n log n)	O(n log n)	O(n)	✅ 稳定	需要稳定性、外部排序
堆排序	O(n log n)	O(n log n)	O(1)	❌ 不稳定	内存受限、Top K 问题

面试总结 🎯

时间复杂度：三者平均都是 O (n log n)，但快速排序常数项最小，实际运行最快
空间复杂度：堆排序最优 O (1)，归并排序最差 O (n)
稳定性：只有归并排序是稳定的
Java 内置排序：Arrays.sort () 对基本类型用双轴快速排序，对对象用 TimSort（归并排序的优化版）

查找算法：二分查找、二叉搜索树、红黑树、B/B+树

面试官您好！查找算法本质是“在数据集合里快速定位目标”，不同数据结构决定了查找效率的上限。我将从核心原理、时间复杂度、Java 实现、优缺点、工业级应用五个维度，为您系统讲解这五大查找算法。

二分查找 🔍

核心前提

必须是有序数组，这是很多人面试时容易忽略的致命点！

核心思想

每次取中间元素与目标值比较，将查找范围缩小一半，直到找到目标或确定不存在。

// 经典实现，注意防溢出
int mid = low + (high - low) / 2;  // 而不是 (low+high)/2

Java 里 Arrays.binarySearch() 就是这原理。如果没找到返回负数，这个负数是 -(插入点+1)，方便直接插入转为有序。

🔍 一句话：内存里的有序数组，二分查找是最快的，O(log n) 且常数极小。

❌ 但插入/删除要 O(n) 搬移数据，所以只适合 静态数据。

时间 / 空间复杂度

实现方式	时间复杂度	空间复杂度
迭代实现	O(logn)	O(1)
递归实现	O(logn)	O(logn)

关键代码（Java 迭代版）

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) { // 注意是<=，不是<
        int mid = left + (right - left) / 2; // 防止溢出，不要用(left+right)/2
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 未找到
}

高频考点

防止整数溢出的 mid 计算方式
左边界、右边界查找变种
旋转有序数组的二分查找

应用场景

Java Arrays.binarySearch() 工具类
有序数据的快速查找
数值范围的二分答案问题

二叉搜索树 (BST) 🌳

核心性质

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
左右子树也都是二叉搜索树

查找流程

性能问题 ⚠️

平均时间复杂度：O (logn)
最坏时间复杂度：O (n)（当插入有序数据时，退化为链表）

          5
         /
        4       ← 像这样全部左倾，查找变成 O(n)
       /
      3

这就是为什么工业界几乎不直接使用原生 BST 的根本原因！

红黑树 🔴⚫ Java 集合的“心脏”🫀

为什么是红黑树？

它通过 颜色约束 + 旋转 保证树近似平衡，任何路径不会长于最短路径的两倍，确保 增删改查全是 O(log n)。比起 AVL（严格平衡），红黑树牺牲一点查询速度，换来 插入/删除更少的旋转次数，写密集型场景更优。

核心定位

自平衡二叉搜索树，解决了 BST 不平衡导致的性能退化问题。

5 条铁律（面试必背）

每个节点要么是红色，要么是黑色
根节点必须是黑色
所有叶子节点 (NIL) 都是黑色
如果一个节点是红色，它的两个子节点都是黑色
从任意节点到其所有后代叶子节点的路径，包含相同数量的黑色节点

平衡操作

变色：改变节点颜色
左旋：将节点向左旋转
右旋：将节点向右旋转

性能优势

插入、删除、查找的最坏时间复杂度都是 O (logn)
保证最长路径不超过最短路径的 2 倍

Java 中的应用

TreeMap 底层实现
TreeSet 底层实现
- TreeMap / TreeSet：底层就是红黑树，因此能按 key 自然排序，firstKey()、subMap() 这些操作都是 O(log n)。
HashMap JDK1.8+ 链表长度超过 8 时转为红黑树
- HashMap：链表长度 ≥8 且数组容量 ≥64 时，链表树化为红黑树，防止哈希冲突严重时查找退化到 O(n)。

        ⬛8 (黑)
      /     \
    🔴5     ⬛12        ← 经典红黑树示意
    / \     /  \
  ⬛3 ⬛7 🔴10 ⬛15

🌳 红黑树是 内存数据结构的工业标准，只要数据全在内存，它几乎是最通用的有序树选择。

B 树 📚

核心痛点

数据库索引动辄上千万行，如果用二叉树，树高可能达到 20~30 层，每层是一次磁盘 IO，查询一条记录就要几十次 IO，不可接受。

解决思路：让每个节点存多个键，变成 多叉树，腰围变粗、身高变矮，一次 IO 加载一个节点（磁盘页），大幅减少 IO 次数。

核心定位

多路平衡查找树，专为磁盘等外存设备设计，减少磁盘 I/O 次数。

核心概念（以 m 阶 B 树为例）

每个节点最多有 m-1 个关键字
根节点最少有 1 个关键字
非根节点最少有⌈m/2⌉-1 个关键字
所有叶子节点都在同一层

每个节点既存 key 也存 data，非叶子节点也参与数据存储。

    [ 10 | 20 | 30 ]
    /     |      \
  子节点  子节点  子节点      ← 多叉结构，度可达上百

3 阶 B 树结构示例

为什么 B 树适合磁盘？

磁盘 I/O 是按页读取的（通常 4KB），B 树的一个节点大小正好可以设计为一个磁盘页，每次 I/O 读取一个完整节点，大大减少 I/O 次数。

B + 树 🌟 MySQL InnoDB 的默认索引

核心定位

B 树的优化版本，是数据库索引的首选数据结构。

数据只存在叶子节点，非叶子只存导航用的 key。
叶子节点用 双向链表 串联，天然支持 范围查询 (BETWEEN、ORDER BY)。

           [10 | 20]          ← 非叶子（仅索引）
          /    |    \
    [1|3|8]→[12|15]→[23|27]   ← 叶子（存数据+双向链表）

与 B 树的核心区别

特性	B 树	B + 树
数据存储	所有节点都存储数据	只有叶子节点存储数据
叶子节点	不相连	形成双向链表
查找效率	不稳定	稳定（必须走到叶子节点）
范围查询	复杂	简单（遍历链表即可）

B + 树结构示例

为什么MySQL数据库用 B + 树而不是红黑树？

磁盘 I/O 更少：B + 树更矮胖，树高更低
高度极低：InnoDB 默认页 16KB，一条记录约 1KB，一个非叶子节点可存上千个 key。3~4 层的 B+ 树就能存几千万数据，一次查询只需 3~4 次磁盘 IO。红黑树高 20+ 层无法接受。
范围查询更高效：叶子节点链表直接遍历
🧹 范围查询友好：B+ 树叶子链表可以直接扫描，B 树需要中序遍历来回跳节点。
查询更稳定：所有查询都走到叶子节点
全表扫描更简单：只需遍历叶子节点链表
🔒 磁盘预读：一次 IO 加载整个节点，高扇出完美利用空间局部性，红黑树节点太小，浪费磁盘带宽。

五大查找算法对比总结 📊

算法	时间复杂度 (平均)	时间复杂度 (最坏)	空间复杂度	适用场景
二分查找	O(logn)	O(logn)	O(1)	有序数组
二叉搜索树	O(logn)	O(n)	O(n)	理论研究，不用于生产
红黑树	O(logn)	O(logn)	O(n)	内存中的有序映射
B 树	O(log_m n)	O(log_m n)	O(n)	文件系统索引
B + 树	O(log_m n)	O(log_m n)	O(n)	数据库索引

🔁 一条总结链（面试官爱听的提炼）

二分查找是思想源头，BST 把它动态化但会歪，红黑树加锁保证不歪且适应高频写，B+树把“矮胖多路”做到极致去适应磁盘 IO。Java 内存世界用红黑树统治有序集合，数据库世界用 B+ 树掌管持久化索引。

🔍 二分查找 → 🌳 BST（退化成链表） → 🌲 红黑树（TreeMap / HashMap 树化） → 🗄️ B+ 树（MySQL InnoDB）

常见算法思想：递归、分治、贪心、动态规划、回溯

面试官您好，我来系统梳理这五种核心算法思想，我会从核心逻辑、适用场景、极简代码和典型题目四个维度展开，保证清晰易懂😊

🧠 先看一张全景图

                     ┌─────────────┐
                     │   递归       │  ← 基础中的基础，自调用的思维方式
                     └──────┬──────┘
                            │ 演化
          ┌────────┬────────┼────────┬────────┐
          ▼        ▼        ▼        ▼        ▼
       分治      回溯    动态规划    贪心     （其他）
     (Divide) (Backtrack)  (DP)   (Greedy)

核心理解：递归是一种编程技巧，而分治、回溯、动态规划、贪心是算法思想，它们大多用递归实现，但本质不同。

1. 递归（Recursion）💡

把大问题拆成同类型的小问题，自己调用自己。

核心思想：函数直接或间接调用自身，将大问题拆解为结构完全相同的小问题，直到达到基线条件（终止条件）后逐层返回结果。

本质：利用系统栈保存每一层的调用状态。

生活例子：你站成一排，想知道自己排第几。你问前面的人：“你排第几？” 前面的人再问他前面的…… 一直问到第一个人说“我排第1”。然后答案一路传回来，你就知道了。

关键三要素（缺一不可）：

终止条件（不然就栈溢出了 💥）
递推公式（问题如何缩小）
返回值（如何合并结果）

Java 极简示例（阶乘）：

// 基线条件：n=0时返回1；递归条件：n! = n * (n-1)!
public int factorial(int n) {
    if (n <= 1) return 1; // 必须有基线条件，否则栈溢出
    return n * factorial(n - 1);
}

适用场景：

树 / 图的遍历（前中后序、深度优先搜索 DFS）
分治、回溯、动态规划的基础实现方式
具有天然递归结构的问题（汉诺塔、斐波那契）

优缺点：

✅ 代码简洁优雅，逻辑清晰

⚠️ Java 默认栈深度约 1000 层，存在栈溢出风险

⚠️ 朴素实现可能存在大量重复计算

典型面试题：二叉树的最大深度、反转二叉树、汉诺塔问题

2. 分治（Divide and Conquer）⚔️

将大问题分解为若干个独立的子问题，分别解决后再合并结果。

与递归的关系：分治通常用递归实现，但多了“合并”这一步，并且子问题相互独立（没有重叠）。

核心思想：分而治之，标准三步法：

分：将原问题拆分为相互独立、无重叠的子问题
治：递归解决每个子问题
合：将子问题的结果合并得到原问题的解

         原问题 [8,3,5,1,9,2]
            /            \
     [8,3,5]            [1,9,2]      ← 拆分 (Divide)
      /    \             /    \
   [8,3]  [5]        [1,9]  [2]
    / \    |          / \    |
  [8][3]  [5]      [1][9]  [2]       ← 最小子问题
    \ /    |          \ /    |
   [3,8]  [5]       [1,9]  [2]       ← 解决 & 合并 (Conquer & Merge)
      \   /             \   /
     [3,5,8]           [1,2,9]
            \         /
          [1,2,3,5,8,9]              ← 最终解

Java 极简示例（归并排序核心）：

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid); // 分：左半部分
    mergeSort(arr, mid + 1, right); // 分：右半部分
    merge(arr, left, mid, right); // 合：合并两个有序数组
}

适用场景：

子问题独立且与原问题结构相同
适合并行计算（子问题互不影响）

优缺点：

✅ 天然支持并行，效率高

✅ 可将 O (n²) 复杂度降为 O (nlogn)

⚠️ 合并步骤可能有额外空间开销

典型面试题：归并排序、快速排序、二分查找、大整数乘法

3. 贪心（Greedy）💰

每一步都选当前看起来最好的选择，期望最终得到全局最优解。

核心思想：每一步都做出当前看起来最优的选择，不考虑后续结果，期望通过局部最优得到全局最优。

特点：不回溯，不后悔，只顾眼前。但前提是问题必须满足贪心选择性质（局部最优能导致全局最优）。

两个必要条件：

贪心选择性质：全局最优可以通过一系列局部最优选择得到
最优子结构：原问题的最优解包含子问题的最优解

生活例子：找零钱，硬币面额[1,5,10,25]，凑36块。贪心：先拿25，剩11拿10，剩1拿1，完美。

但如果面额是[1,3,4]，凑6，贪心拿4+1+1=3枚，可最优是3+3=2枚。❌ 此时贪心失效。

Java 极简示例（活动选择问题）：

// 选择最多的不重叠活动，按结束时间排序后贪心选择
public int maxActivities(int[][] activities) {
    Arrays.sort(activities, (a, b) -> a[1] - b[1]);
    int count = 1, lastEnd = activities[0][1];
    for (int i = 1; i < activities.length; i++) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}

适用场景：

满足贪心选择性质和最优子结构的问题
对时间复杂度要求高，不需要绝对最优解的场景

优缺点：

✅ 时间复杂度极低（通常 O (n) 或 O (nlogn)）

✅ 代码简单，空间复杂度低

⚠️ 不一定能得到全局最优解（如部分零钱兑换问题）

典型面试题：哈夫曼编码、Kruskal 最小生成树、活动选择、跳跃游戏 II

4. 动态规划（Dynamic Programming, DP）🎯

把复杂问题分解成重叠子问题，通过记忆化存储中间结果，避免重复计算，自底向上或自顶向下求解。

核心思想：将原问题拆解为重叠的子问题，通过存储子问题的解（DP 数组 / 表）避免重复计算，最终得到全局最优解。

核心：记住你算过的东西！记忆化 + 最优子结构 + 状态转移方程。

两个必要条件：

重叠子问题：子问题会被重复计算多次
最优子结构：原问题的最优解包含子问题的最优解

Java 极简示例（斐波那契 DP 优化）：

// 用DP数组存储中间结果，避免重复计算
public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
    }
    return dp[n];
}

适用场景：

求最值、计数、可行性判断的问题
子问题存在大量重叠的场景

优缺点：

✅ 彻底避免重复计算，时间复杂度远优于暴力

✅ 结果一定是全局最优

⚠️ 状态定义和状态转移方程较难推导

⚠️ 空间复杂度较高（可通过滚动数组优化）

典型面试题：最长公共子序列 (LCS)、0-1 背包问题、爬楼梯、编辑距离

DP 解题四步法：

定义状态（dp[i] 代表什么？）🎯
推导状态转移方程（怎么从以前的状态过来？）
设置初始条件（边界值）
确定遍历顺序（从前到后，还是从后到前？）

背包问题状态转移图示：

dp[i][w] = max( dp[i-1][w] , dp[i-1][w - wt[i]] + val[i] )
              不选当前物品      选当前物品

重量→  0   1   2   3   4   5
物品0  0   0   0   0   0   0
物品1  0   1   1   1   1   1   (wt=1,val=1)
物品2  0   1   2   3   3   3   (wt=2,val=2)
物品3  0   1   2   3   4   5   (wt=3,val=3)

5. 回溯（Backtracking）🔙

暴力搜索 + 试探 + 撤销。走不通就回头，能进能退。

核心思想：暴力搜索的优化版，通过尝试所有可能的路径，当发现当前路径无法得到解时，回退到上一步选择其他路径，直到找到所有解或最优解。

本质：深度优先搜索 (DFS) + 剪枝（提前排除不可能的路径）

模板要刻进DNA里：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        res.add(路径);
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);  // 前进
        撤销选择;                   // 回溯
    }
}

形象理解：走迷宫 👣，每个路口放个标记，走到死路就退回标记处，换条路再试。

经典问题： N皇后、全排列、组合总和。

  全排列决策树 (nums=[1,2])：

              []
        /          \
       1            2          ← 做选择
      / \          / \
     [1,2]       [2,1]        ← 满足结束，记录路径
        回溯去掉2，再回溯去掉1

与DP区别：回溯重在“搜索所有解”，常用来解没有最优子结构的问题；DP重“最优解”，要求子问题重叠。

Java 极简示例（全排列问题）：

List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
    backtrack(nums, new boolean[nums.length], new ArrayList<>());
    return res;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); // 找到一个解
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // 剪枝：跳过已使用的元素
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path); // 递归尝试
        path.remove(path.size() - 1); // 回溯：撤销选择
        used[i] = false; // 回溯：恢复状态
    }
}

适用场景：

组合、排列、子集问题
棋盘类问题（N 皇后、数独）
需要枚举所有可能解的问题

优缺点：

✅ 能解决几乎所有组合枚举类问题

✅ 剪枝可以大幅降低时间复杂度

⚠️ 最坏情况时间复杂度仍为指数级（O (2ⁿ) 或 O (n!)）

典型面试题：N 皇后问题、全排列、子集、组合总和

五种算法思想核心对比表 📊

算法思想	核心逻辑	子问题关系	是否需要回溯	时间复杂度特点	典型题目
递归	自己调用自己，基线终止	结构相同	否	取决于问题	二叉树遍历、汉诺塔
分治	分→治→合，子问题独立	相互独立，无重叠	否	通常 O (nlogn)	归并排序、二分查找
贪心	每步选当前最优	无直接依赖	否	通常 O (n) 或 O (nlogn)	活动选择、哈夫曼编码
动态规划	存储子问题解，避免重复计算	大量重叠	否	通常 O (n²) 或 O (nm)	0-1 背包、最长公共子序列
回溯	DFS + 剪枝，尝试所有可能	枚举所有组合	是	最坏指数级 O (2ⁿ)/O (n!)	N 皇后、全排列

算法思想选择流程图 🧠

面试高频追问小贴士 💬

1. 贪心和动态规划的区别？

贪心：每步局部最优，不可逆，不一定全局最优
DP：存储所有子问题解，可回溯，一定全局最优
贪心是 DP 的特例（当每步最优能得到全局最优时）

2. 分治和动态规划的区别？

分治：子问题独立，无重叠，结果合并即可
DP：子问题重叠，需要存储中间结果避免重复计算

3. 递归的优化方法？

尾递归优化（Java 原生不支持，可手动实现）
迭代法（手动模拟栈）
记忆化递归（缓存子问题解，本质是 DP 的递归实现）

4. 回溯的核心优化技巧？

剪枝：提前排除不可能的路径（如排序后剪枝重复元素）
空间优化：使用原数组标记状态，避免额外空间

最后，我给你一个练手题单感受一下：

递归：反转二叉树 🌳
分治：数组中的逆序对（归并思想）
贪心：跳跃游戏 II
DP：最长递增子序列、打家劫舍
回溯：全排列、N皇后

把每题用对应思想写一遍，写完后问自己：状态怎么定义的？有没有重复计算？能否剪枝？ 这五种思想你就真的通了。

字符串算法：KMP、Trie 树

KMP 算法 💡

1. 核心思想

暴力匹配每次不匹配都会回溯主串指针，导致最坏时间复杂度 O (n*m)。KMP 通过预处理模式串生成 next 数组，记录最长相等前后缀长度，让主串指针永不回溯，只移动模式串指针，将时间复杂度优化到 O (n+m)。

📌 为什么要 KMP？

暴力匹配每次失配，主串 i 回退，复杂度最坏 O(n*m)。KMP 做到 O(n+m)。

2. 关键原理：next 数组 🔍

next 数组是 KMP 的灵魂，next[j]表示：模式串前 j 个字符组成的子串中，最长相等前缀和后缀的长度。

不匹配时，模式串指针直接跳转到next[j]的位置继续匹配
本质是利用已经匹配过的前缀信息，避免重复比较

举个例子：模式串 "ABABC" 的 next 数组计算

模式串索引 j	0	1	2	3	4
模式串字符	A	B	A	B	C
next[j]	-1	0	0	1	2

推导过程：

j=0：没有字符，约定 next [0]=-1
j=1：子串 "A"，无前后缀，next [1]=0
j=2：子串 "AB"，前后缀无相等，next [2]=0
j=3：子串 "ABA"，最长相等前后缀 "A"（长度 1），next [3]=1
j=4：子串 "ABAB"，最长相等前后缀 "AB"（长度 2），next [4]=2

我画出模式串 ABABC 的 next 构建过程：

j	子串 P[0..j-1]	最长相等前后缀	next[j]
0	(空)	-	-1
1	A	无	0
2	AB	无	0
3	ABA	A	1
4	ABAB	AB	2

图示 next[4] 前后缀：

A B A B
   ‾‾‾‾ → 前缀 A B
A B A B
‾‾‾‾   → 后缀 A B，长度 2

3. Java 极简实现

// KMP匹配：返回主串中模式串第一次出现的索引，不存在返回-1
public int kmp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    int[] next = getNext(pattern);
    int i = 0, j = 0; // i主串指针，j模式串指针
    
    while (i < n && j < m) {
        if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
            i++; j++;
        } else {
            j = next[j]; // 核心：模式串指针跳转，主串不动
        }
    }
    return j == m ? i - j : -1;
}

// 生成next数组
private int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = -1;
    int k = -1, j = 0;
    
    while (j < m - 1) {
        if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
            next[++j] = ++k;
        } else {
            k = next[k]; // 递归找更短的相等前后缀
        }
    }
    return next;
}

“代码能随手写一下不？尤其是 next 数组怎么求的，很多候选人卡在 k = next[k] 的回退上。”

// 构建 next 数组
int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = -1;
    int k = -1, j = 0;
    while (j < m - 1) {
        if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
            j++; k++;
            next[j] = k;          // 记录最长前后缀长度
        } else {
            k = next[k];          // 🔁 核心回退：找次长前后缀
        }
    }
    return next;
}

🔁 回退释义：当 P[j] != P[k] 时，不能直接扩展前后缀，那我们就退一步，检查 next[k] 长度是否存在可用的前后缀，这步用图画一个状态机最直观：

 j:   0 1 2 3 4
 P:   A B A B C
next:-1 0 0 1 2
           ↘ 当 j=4, k=2 (P[4]='C' != P[2]='A')
              k = next[2] = 0 → 回退到长度0继续比较

🔍 匹配过程（主串 ABABABC）：

主: A B A B A B C
模: A B A B C
匹配到 j=4 时失配 (主串[4]='A', P[4]='C')
j = next[4] = 2 → 模式串右移两位，i 不变
主: A B A B A B C
模:     A B A B C  ← 从 j=2 继续，最终匹配成功 ✅

4. 面试必考点 ⚠️

时间复杂度：O (n+m)（n 主串长度，m 模式串长度）
空间复杂度：O (m)（存储 next 数组）
优化点：nextval 数组（解决模式串重复字符导致的多余比较）
应用场景：文本编辑器查找功能、生物信息学 DNA 序列匹配、日志关键词检索

Trie 树（字典树 / 前缀树） 🚀

Trie 树（前缀树）。查询只和字符串长度有关，跟数据总量无关。

1. 核心思想

一种多叉树结构，利用字符串的公共前缀来减少查询时间，典型的 "空间换时间" 算法。

相同前缀的字符串共享路径节点
从根节点到某一叶子节点的路径，就是一个完整的字符串

2. 结构特点 🔍

每个节点代表一个字符
每个节点有一个isEnd标记，表示是否是字符串的结尾
子节点通常用数组或哈希表存储（Java 中常用长度 26 的数组对应小写字母）

Trie 树结构示意图（插入 "app"、"apple"、"apricot"）

📌 结构图

插入 "abc", "abd", "ac" 后的 Trie：

        (root)
       /     \
      a       ...
     / \
    b   c
   / \   ✅
  c   d
  ✅   ✅

✅ 标记一个完整单词结束。

3. Java 极简实现

class Trie {
    // Trie节点定义
    private class TrieNode {
        boolean isEnd;
        TrieNode[] children;
        
        public TrieNode() {
            isEnd = false;
            children = new TrieNode[26]; // 仅存储小写字母
        }
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    // 插入字符串
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    
    // 查找完整字符串是否存在
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }
    
    // 查找是否存在以prefix为前缀的字符串
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

4. 优缺点与应用

优点	缺点
前缀匹配效率极高（O (k)，k 为字符串长度）	空间占用大（每个节点有 26 个子节点指针）
插入和查询速度快，优于哈希表和红黑树	不适合存储长字符串
天然支持字符串排序	哈希冲突问题不存在

核心应用场景：

搜索引擎自动补全
拼写检查与纠错
路由表最长前缀匹配
敏感词过滤
字符串去重

5. 面试必考点 ⚠️

与哈希表的对比：哈希表查询 O (1) 但不支持前缀匹配，Trie 前缀匹配 O (k)
优化方向：压缩 Trie（基数树）、合并相同路径节点
实际项目中的变种：双数组 Trie（节省空间）、后缀树

Trie 虽快，但会耗费大量内存，尤其是中文场景，你怎么办？

压缩节点 → 基数树 (Radix Tree)，把单子节点路径合并。

原始：a → b → c   合并后：abc

用数组代替 Map 当孩子少时 → TrieNode[] children = new TrieNode[26] (英文)，空间换时间更极致。
双数组 Trie（Double-Array Trie）—— 状态机压缩，在分词库中常用。

那如果我用 Trie 做通配符搜索，比如 a.c，能直接用吗？

“不行。纯 Trie 只能前缀匹配。带 . 的模糊匹配要改用 回溯 DFS 在 Trie 上搜，或者引入后缀树 / AC 自动机。”

核心对比总结 📊

算法	核心优势	适用场景	时间复杂度	空间复杂度
KMP	单模式串精确匹配高效	文本中查找单个关键词	O(n+m)	O(m)
Trie 树	多模式串前缀匹配高效	自动补全、敏感词过滤	O (k)（k 为字符串长度）	O (Σ*N)（Σ 字符集大小，N 节点数）

                 KMP              |          Trie 树
——————————————————————————————————————————————————
核心思想    部分匹配表(next)       |  共享前缀的多叉树
匹配方式    单模式串滑动           |  多个模式串，按字符路径走
时间         O(n+m)               |  O(L) 每词
空间         O(m) next数组         |  O(节点数*字符集大小)
应用         Ctrl+F 查找           |  输入联想、拼写检查、敏感词

哈希算法：一致性哈希、布隆过滤器

好的面试官。这俩都是哈希算法的‘工程化变形’，本质是用空间、概率或结构优化，去解决大数据量下的精准定位和存在性判断问题。我一个一个说。

一致性哈希 💡

1. 解决的核心问题

传统哈希取模（hash(key) % nodeCount）的致命缺陷：节点数量变化时，几乎所有数据的映射关系都会失效，导致大规模缓存雪崩、数据库压力骤增。一致性哈希就是为了最小化节点增减时的数据迁移量。

2. 核心原理：哈希环

将整个哈希值空间组织成一个0 ~ 2^32 - 1的环形结构（哈希环）：

把所有服务器节点通过哈希函数映射到环上
把数据 key 也通过相同哈希函数映射到环上
数据从自身映射位置顺时针查找第一个遇到的节点，就是该数据的存储节点

增减节点时，只有受影响区间内的数据需要迁移，其余数据完全不动。

比如在 Node1 和 Node2 之间加 Node4，只是把那一段数据重新分配给 Node4。

3. 关键优化：虚拟节点 🔑

问题：节点数量少时，数据分布严重倾斜（大部分数据集中在少数节点）
解决方案：为每个真实节点创建 100~200 个虚拟节点，均匀分布在哈希环上
效果：数据分布更均匀，节点增减时仅影响相邻节点的数据，迁移量最小化

4. 优缺点与应用场景

✅ 优点：节点增减仅影响相邻节点，数据迁移量极小；扩展性好

❌ 缺点：存在数据倾斜问题（需虚拟节点解决）；实现复杂度高于传统哈希

👉 致命问题：数据倾斜:如果节点哈希不够散列，比如三个节点全挤在环的一侧，大量数据会压到某一个节点上 🤯。
👉 解决方案：虚拟节点:为每个物理节点生成 N 个虚拟副本，分散到环上各个位置，使负载均衡。实际落地时常用 100~200 个虚拟节点。

🌐 应用：Redis Cluster 集群、分布式缓存系统、Nginx 负载均衡、Ceph 分布式存储

5. 面试高频追问点

节点下线时，数据如何迁移？（自动迁移到顺时针下一个节点）
哈希冲突怎么处理？（一致性哈希本身冲突概率极低，一般用链式法兜底）
为什么用 2^32 作为哈希环大小？（刚好是 32 位无符号整数的取值范围，计算高效）

Java 简易实现思路：

// 用 TreeMap 实现哈希环，key 为节点哈希值，value 为节点名称
TreeMap<Integer, String> ring = new TreeMap<>();

// 初始化：每个物理节点生成 150 个虚拟节点
for (String node : physicalNodes) {
    for (int i = 0; i < 150; i++) {
        int hash = hash(node + "#" + i);
        ring.put(hash, node);
    }
}

// 定位数据所属节点
public String getNode(String key) {
    int hash = hash(key);
    Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
    if (entry == null) {
        return ring.firstEntry().getValue(); // 回到环起点
    }
    return entry.getValue();
}

👉 实际应用场景

分布式缓存（Memcached、Redis 分片）
分布式存储（Dynamo、Cassandra）
网关限流、服务路由

布隆过滤器 🚦

海量数据中判断一个元素是否存在，传统 HashSet 内存撑爆。布隆过滤器用极小的内存，换取一定误判率的存在性判断。

1. 解决的核心问题

缓存穿透：大量不存在的 key 直接穿透缓存打到数据库，导致数据库宕机。布隆过滤器可以快速判断一个元素一定不存在，从而拦截无效请求。

2. 核心原理

由一个位数组 + N 个独立的哈希函数组成：

添加元素：用 N 个哈希函数分别计算元素的哈希值，将位数组中对应位置设为 1
查询元素：用相同的 N 个哈希函数计算位置，若任意一个位置为 0，则元素一定不存在；若所有位置都为 1，则元素可能存在（存在假阳性）

👉 关键特性：宁可错杀，不可放过

返回“不存在”，100% 准确。
返回“存在”，可能被其他元素的哈希碰撞干扰，存在误判。
不支持删除，因为位可能被多个元素共用（计数布隆过滤器可缓解）。

👉 误判率公式

在 m 位数组、k 个哈希函数、插入 n 个元素后，误判率 p ≈ (1 - e^(-kn/m))k。

当 k = (m/n) * ln2 时，误判率最小。实际应用中，m/n 取 8~12，误判率可低于 1%。

3. 关键特性与参数选择

空间效率极高：10 亿条数据仅需约 1GB 内存（假阳性率 1%）
查询速度极快：O (k) 时间复杂度（k 为哈希函数数量）
不可删除：传统布隆过滤器不能删除元素（会影响其他元素的判断）
假阳性率控制：位数组长度 m、哈希函数数量 k、元素数量 n 满足公式：
m = -n * ln(p) / (ln2)^2，k = m/n * ln2（p 为期望假阳性率）

4. 优缺点与应用场景

✅ 优点：空间和时间复杂度远超其他数据结构；无存储开销（仅存标记位）

❌ 缺点：存在假阳性；不能删除元素；初始化需要预分配空间

🌐 应用：Redis 缓存穿透防护、爬虫 URL 去重、垃圾邮件过滤、黑名单系统、推荐系统去重

5. 面试高频追问点

假阳性率太高怎么办？（增加位数组长度或哈希函数数量）
如何实现可删除的布隆过滤器？（计数布隆过滤器，用计数器代替位）
Redis 中的布隆过滤器怎么用？（Redis 4.0 + 支持 Bloom 模块，BF.ADD/BF.EXISTS命令）

Java 落地：Guava 的 BloomFilter

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    1_000_000,   // 预期插入数量
    0.01         // 误判率
);

filter.put("apple");
filter.mightContain("apple");  // true
filter.mightContain("banana"); // false，但有小概率 true

如果布隆过滤器误判率用 1%，当存储元素远超预期数量，会发生什么？

误判率会陡升！因为每个比特被置1的概率更大，碰撞急剧增加，甚至接近 100%。所以生产上要么预留容量，要么用可伸缩布隆过滤器动态扩容。

🔗 两者怎么串起来？

一致性哈希解决分布式存储位置问题，布隆过滤器解决单机/局部快速存在性问题。

大型缓存系统常见组合：客户端用一致性哈希定位节点，节点内用布隆过滤器快速返回“无”，避免耗时的磁盘/DB IO。

限流算法：计数器、滑动窗口、漏桶、令牌桶

面试官您好，关于限流算法，我主要掌握四种工业界最常用的实现，我会从核心原理、优缺点、适用场景三个维度给您清晰介绍，最后补充 Java 生态的落地方式 🤓

🔍 先看全局：一图胜千言

在细抠算法前，先直观感受下四种算法的“脾气”

看明白了？计数器是毛坯房，滑动窗口是精装，漏桶是节流阀，令牌桶是蓄水池。下面逐一拆骨。

计数器固定窗口算法 ⏱️

核心原理

将时间划分为固定大小的窗口（比如 1 秒），每个窗口内维护一个计数器，请求到来时计数器 + 1，超过阈值则拒绝请求，窗口结束后计数器清零。

图解 ASCII：

窗口1 (0~1s)         窗口2 (1~2s)
|-------|-------|-------|-------|
  ✅ ✅ ✅ ❌(满)      ✅ ✅ ✅ ...
计数器: 3/3            计数器: 0 -> ...

⏳ 每过 1 秒，计数器“咣当”清零，重新计数。

优缺点

✅ 优点：实现极其简单，性能极高，几乎无额外开销

❌ 缺点：存在临界突刺问题—— 两个窗口交界处可能出现 2 倍阈值的流量（比如 0.9s 来 3 个，1.1s 来 3 个，0.2s 内共 6 个请求）

适用场景

对限流精度要求不高、流量相对平稳的简单场景，比如内部系统接口防护

滑动窗口算法 🪟

核心原理

为解决固定窗口的临界问题，将大窗口划分为多个小格子（比如 1 秒窗口划分为 10 个 100ms 的格子），每次请求到来时，滑动删除过期的小格子，统计当前所有有效格子的总请求数。

数据结构动图感：

时间轴 ->
|口|口|口|口|口|口|口|口|口|口|   (10格，每格100ms)
           ↑当前时间
统计范围: [过去10格] → 和 ≤ 阈值

🕰️ 窗口不是到点清零，而是随时间平移，永远只看最近一段时间内的请求量。

落地实现：

Redis 的 ZSET 经典操作：每个请求记一个 member = 唯一ID，score = 毫秒时间戳。统计时 ZREMRANGEBYSCORE 干掉过期数据，再 ZCARD 看数量。或使用 sorted set + 滑动窗口 Lua 脚本。

优缺点

✅ 优点：彻底解决了固定窗口的临界突刺问题，限流精度更高

❌ 缺点：需要维护多个小格子的计数，实现稍复杂，性能略低于固定窗口

适用场景

对限流精度要求较高的业务场景，比如对外提供的开放 API 接口

漏桶算法 🪣

核心原理

请求先进入一个固定容量的漏桶，漏桶以恒定速率向外流出请求（交给系统处理），如果漏桶满了，新的请求就会被丢弃。

水（请求）先进入桶里，桶底有个小孔以恒定速率漏水（处理请求）。桶满则溢出（拒绝）。不管上游是涓涓细流还是洪水滔天，下游看到的永远是恒速水流。💧

      💦 请求 💦
        ↓   ↓   ↓
    ┌─────────────┐
    │  🪣  漏桶    │  ← 容量 N
    │  水 水 水    │
    └──────┬──────┘
           ↓ 恒速滴出 (rate)
    ────────────────  处理请求

算法本质：

需要记录 上次漏水时间 和 当前水量。每次请求时计算流逝时间 × 流出速率 = 这段时间漏掉的水，从水量中减去。若当前水量 + 1 ≤ 容量，则请求入桶并增加水量；否则拒绝。

优缺点

✅ 优点：强制平滑突发流量，保证系统处理速率绝对稳定

❌ 缺点：无法应对突发流量 —— 即使系统空闲，也只能以固定速率处理请求，资源利用率低

适用场景

需要严格控制请求处理速率的场景，比如消息队列削峰填谷、数据库写入限流

令牌桶算法 🎫

核心原理

系统以恒定速率向令牌桶中放入令牌，令牌桶有最大容量，满了就不再添加。每个请求到来时，需要从桶中获取一个令牌才能被处理，获取不到则拒绝请求。令牌桶不同于漏桶的核心：允许积攒令牌应对突发。🎫

     🏭 令牌工厂 (rate/秒)
        ↓  ↓  ↓  (匀速产生)
    ┌─────────────┐
    │  🎫 令牌桶   │  ← 最多存 B 个令牌
    │ 令牌令牌令牌 │
    └──────┬──────┘
           ↓ 拿走令牌才能通过
      🚦 请求放行

关键参数：

rate：令牌生成速率（比如 100 个/秒）
capacity：桶最大容量（比如 200 个）

优缺点

✅ 优点：既能平滑流量，又能应对突发流量（桶中预存的令牌可以一次性被消耗），是工业界最常用的限流算法

❌ 缺点：实现相对复杂，需要单独维护令牌生成逻辑

面试高频考点：漏桶 vs 令牌桶

很多同学容易搞混，核心区别只有一个：

漏桶：控制流出速率，强制平滑，绝对不允许突发
令牌桶：控制流入速率，允许一定程度的突发（最大突发量 = 令牌桶容量）

💡 记忆技巧：

漏桶像景区限流，出来多少人放多少人进去，门外排队（丢弃）。
令牌桶像网红餐厅，一小时放 100 个号，但可以攒 20 个号同时进去坐，只要号够。

适用场景

绝大多数互联网业务场景，比如 API 网关限流、微服务接口限流、爬虫频率控制

四大算法核心对比 📊

算法	核心思想	优点	缺点	适用场景
固定窗口	固定时间内计数	实现简单、性能极高	临界突刺问题	简单内部系统
滑动窗口	滑动时间内计数	解决临界问题、精度高	实现稍复杂、性能略低	开放 API 接口
漏桶	固定速率流出	强制平滑流量	无法应对突发、资源利用率低	消息队列削峰、数据库写入
令牌桶	固定速率生成令牌	平滑 + 支持突发、灵活度	实现复杂	绝大多数互联网场景

Java 生态落地方式 💻

固定窗口：单机用AtomicInteger，分布式用 Redis incr + expire
滑动窗口：Redis zset 实现（时间戳作为 score，删除过期元素后统计数量）
令牌桶：直接使用 Guava 的RateLimiter（支持预热模式，工业级成熟实现）
分布式限流：基于 Redis+Lua 脚本实现，保证多个操作的原子性

🎯 面试官送你两句拔高总结

“计数器是死窗口，滑动是活窗口，漏桶是恒速队列，令牌桶是预支额度。”

如果面试官再深问实现，你要能说出：

滑动窗口用 ZSET 或环形数组 + 时间戳；
令牌桶/漏桶无需后台线程，纯惰性计算（根据时间差算出应补水量/令牌数）；
分布式限流需要 Redis 做中心化计数，需考虑 Lua 原子化操作。

雪花算法原理与实现

面试官您好！雪花算法（Snowflake）是 Twitter 开源的分布式唯一 ID 生成算法，核心解决分布式系统中全局唯一 ID 的生成问题，同时保证 ID 的趋势递增和高性能。

核心原理：64 位 ID 结构 🧱

雪花算法生成的是一个 64 位的 long 型整数，结构如下：

┌─┬──────────────────────────┬────────────┬──────────────┐
│1│        41 位时间戳        │ 10 位机器ID │  12 位序列号  │
│ │      (毫秒级)             │ (5+5)       │              │
└─┴──────────────────────────┴────────────┴──────────────┘
  ↑           ↑                    ↑              ↑
 保留     从固定起始时间       数据中心+机器    同毫秒内自增
          的毫秒偏移量         共1024个节点     每毫秒4096个

详细说明：

位数	名称	作用	取值范围
1 位	符号位	固定为 0（正数）	0
41 位	时间戳	毫秒级时间差	约 69 年
10 位	机器 ID	分布式节点标识	0~1023
12 位	序列号	同一毫秒内的自增序列	0~4095

具体来看每一段的含义 🧐：

第 1 位：保留位，恒为 0。因为最高位是符号位，置 0 保证 ID 是正数，方便数据库索引等。
41 位时间戳：存储的是当前时间距离自定义起始时间（比如 2020-01-01）的毫秒差值。
- 容量：2^41 ≈ 2.2 万亿毫秒，换算成年大约是 69 年，完全够用 ⏰。
10 位机器标识：可以细分为 5 位数据中心 ID + 5 位工作机器 ID，支持 1024 个节点。部署时需保证每个节点这一段的组合唯一。
12 位序列号：同一毫秒内生成的 ID 序号，从 0 开始递增。
- 容量：2^12 = 4096 个/毫秒。这意味着单机每秒理论上限 409.6 万 ID，性能极高 🚀。

💡 关键点：理论上每秒可生成 1000 * 4096 = 4,096,000 个 ID，完全满足绝大多数分布式系统的需求。

Java 实现代码 ✍️

public class SnowflakeIdGenerator {
    // 起始时间戳：2020-01-01 00:00:00
    private static final long START_TIMESTAMP = 1577808000000L;
    
    // 各部分位数
    private static final long MACHINE_ID_BITS = 10L;
    private static final long SEQUENCE_BITS = 12L;
    
    // 各部分最大值
    private static final long MAX_MACHINE_ID = ~(-1L << MACHINE_ID_BITS); // 1023
    private static final long MAX_SEQUENCE = ~(-1L << SEQUENCE_BITS); // 4095
    
    // 各部分左移位数
    private static final long MACHINE_ID_SHIFT = SEQUENCE_BITS;
    private static final long TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS;
    
    private final long machineId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;
    
    public SnowflakeIdGenerator(long machineId) {
        if (machineId < 0 || machineId > MAX_MACHINE_ID) {
            throw new IllegalArgumentException("机器ID超出范围");
        }
        this.machineId = machineId;
    }
    
    public synchronized long nextId() {
        long currentTimestamp = System.currentTimeMillis();
        
        // 处理时钟回拨问题
        if (currentTimestamp < lastTimestamp) {
            throw new RuntimeException("时钟回拨，无法生成ID");
        }
        
        // 同一毫秒内，序列号自增
        if (currentTimestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            // 序列号溢出，等待下一毫秒
            if (sequence == 0) {
                currentTimestamp = waitNextMillis(lastTimestamp);
            }
        } else {
            // 不同毫秒，序列号重置为0
            sequence = 0L;
        }
        
        lastTimestamp = currentTimestamp;
        
        // 拼接各部分生成最终ID
        return ((currentTimestamp - START_TIMESTAMP) << TIMESTAMP_SHIFT)
                | (machineId << MACHINE_ID_SHIFT)
                | sequence;
    }
    
    // 等待下一毫秒
    private long waitNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

✅ 这样生成出来的 ID 是纯数字的 Long，天然在数据库 B+Tree 索引上顺序写入，磁盘顺序 IO，性能极佳。

核心问题与解决方案 ⚠️

1. 时钟回拨问题

问题：服务器时钟回拨会导致生成重复 ID
解决方案：
- 简单方案：直接抛出异常（如上代码）
- 进阶方案：记录回拨时间差，等待时钟追上
- 高级方案：引入备用机器 ID 池，回拨时切换 ID

2. 机器 ID 分配问题

问题：分布式环境下如何保证机器 ID 唯一
解决方案：
- 手动配置：适合节点少的场景
- 基于 IP 哈希：简单但可能冲突
- 使用 ZooKeeper/Redis：自动分配唯一 ID

优缺点总结 📊

优点	缺点
高性能：单节点每秒百万级 ID	依赖系统时钟，存在时钟回拨问题
趋势递增：ID 整体有序，适合数据库索引	机器 ID 分配需要额外机制
无中心化：不依赖第三方服务，可用性高	时间戳只有 41 位，约 69 年后会溢出
可定制：各部分位数可根据业务调整	同一毫秒内最多 4096 个 ID

常见变种 🔄

百度 UidGenerator：优化了时钟回拨处理，支持更高并发
美团 Leaf：提供号段模式和雪花模式两种实现
Sonyflake：使用 16 位序列号，时间精度为 10 毫秒，可用时间更长

在实际大厂落地，还会做以下优化：

动态调整 bit 位分配：根据业务调整，比如不需要那么多数据中心，就少分几位给机器，多分几位给序列号，提升单机并发。
解决 workerId 的自动分配：引入 ZooKeeper 或 etcd 在启动时注册临时节点，自动获取唯一 workerId，避免手动配置。
容器化支持：将 workerId 与 Pod 的 hostname/IP 的哈希绑定，确保同一时刻只有一个实例持有该 workerId。

💎 总结

雪花算法本质就是 “分段存储不同维度的自增信息，用位运算拼装”。它解决了“唯一、递增、纯数字、高性能”四大需求，而对时钟回拨的处理能力，决定了生产环境的可用性。

海量数据处理：Top K 问题、BitMap、Bloom Filter

面试官您好！海量数据处理是互联网大厂的高频考点，核心解决内存不足和计算效率两大痛点。Top K、BitMap、Bloom Filter 是其中最经典的三个方案，我会从原理、实现、优缺点和应用场景逐一说明。

Top K 问题：找出海量数据中出现频率最高的 K 个元素 📊

1. 问题本质

在 10 亿条数据中找出出现次数最多的前 100 个元素，不能一次性加载到内存。

2. 解法对比（时间复杂度 O (n) 级别最优）

解法	时间复杂度	空间复杂度	适用场景	缺点
全排序	O(n log n)	O(n)	小数据量	海量数据直接 OOM
大顶堆	O(n log K)	O(K)	单机小 K	只能找 Top K，不能去重统计
分治 + 哈希 + 小顶堆	O(n log K)	O(n/m)	海量数据	工程实现稍复杂
快速选择	O(n)	O(n)	找第 K 大元素	不稳定，不适合频率统计

2.1 通用解法：小顶堆（Min-Heap）

维护一个大小为 K 的小顶堆（堆顶是当前 K 个元素里的最小值）。
遍历所有数据：
- 堆未满时，直接插入。
- 堆满后，若新元素大于堆顶，则弹出堆顶，插入新元素；否则跳过。
遍历结束，堆中留下的就是 Top K。

⏱ 时间复杂度：O(N log K)，N 为数据总量。K=100 时 logK 极小，几乎线性扫描。

📦 空间复杂度：O(K)，内存只存堆和少量辅助结构，非常省。

2.2 小顶堆维持 Top K 示意图：

2.3 数据量再大怎么办？分治 + 堆

如果连一遍扫描都扛不住（比如 TB 级文件），就用 MapReduce 思想：

按哈希分桶，每个桶统计词频（Map）。
各自桶内用小顶堆求出局部 Top K（Reduce）。
最后合并所有局部 Top K，再用一个全局小顶堆求出最终 Top K。

这就是 分而治之 + 堆合并 的路子。

2.4 特殊场景的“奇技淫巧”

数据范围有限（如年龄、分数 0~100）：直接用计数排序/桶排序，O(N) 横扫，再倒序取 K 个。
需要实时动态 Top K：维护一个平衡二叉搜索树（如 Java 的 TreeMap）或结合堆 + 哈希表，但复杂不少，面试能讲出思路就加分。

📌 面试要点：说清为什么用小顶堆而不是大顶堆，以及空间复杂度 O(K) 的优势。顺带提一下海量数据下需要分治，展示整体架构思维。

3. 工业界标准解法（分治三步法）

4. Java 实现关键点

用HashMap统计频率，PriorityQueue实现小顶堆（默认就是小顶堆）
堆大小固定为 K，当堆元素超过 K 时，弹出堆顶最小元素
分布式场景：MapReduce 思想，Map 阶段分片统计，Reduce 阶段合并结果

BitMap：用 1 个 bit 表示 1 个整数的存在状态 🎯

1. 核心原理

用 bit 位的 0/1 表示某个整数是否存在，1 个 int 占 4 字节 = 32bit，所以 1GB 内存可以表示1GB * 8 = 80亿个整数的存在状态。

2. 核心操作（以整数 x 为例）

// 初始化：10亿个整数需要 10亿/8 ≈ 125MB 内存
BitSet bitSet = new BitSet(1_000_000_000);

// 1. 标记x存在：将第x位设为1
bitSet.set(x);

// 2. 判断x是否存在：检查第x位是否为1
boolean exists = bitSet.get(x);

// 3. 删除x：将第x位设为0
bitSet.clear(x);

3. 优缺点

✅ 优点：空间效率极高，时间复杂度 O (1)，实现简单

❌ 缺点：只能处理整数，不能处理重复数据，存在数据范围限制

4. 经典应用场景

10 亿个整数中查找某个数是否存在
统计不重复元素的个数
两个集合的交集、并集计算
网页爬虫 URL 去重（需先哈希映射到整数）

🗂️ BitMap：用比特位给“整数”去重排序

面试官： “有 5 亿个不重复的 32 位 int 整数，只给你 1GB 内存，怎么排序？”

如果用 int[] 存 5 亿个整数，需要 5亿 × 4 字节 ≈ 2GB，内存超标。💥 这时候 BitMap 就登场了。

1. 核心思想

用一个 bit 表示一个整数是否存在。

32 位整数的范围是 0 ~ 2³²-1（约 42.9 亿），我们需要一个长度为 2³² bit 的数组。

🔢 换算成字节：2³² / 8 = 2²⁹ 字节 = 512MB，完美符合内存限制。

插入数字 n：bitArray[n / 8] |= (1 << (n % 8))
检查是否存在：bitArray[n / 8] & (1 << (n % 8))
排序：遍历 0 ~ 最大值，若对应 bit 为 1 就输出该数字，天然有序。

BitMap 内存节省对比表：

存储方式	5 亿整数占用内存	能否在 1GB 内
`int[]` 原始存储	约 2GB（5亿×4字节）	❌
Java `BitSet` / BitMap	约 512MB（2³² bit）	✅
压缩 BitMap (RoaringBitmap)	更少，几十 MB 到百 MB	✅

2. Java 里的 BitMap 实现

直接用 java.util.BitSet：

BitSet bitSet = new BitSet(Integer.MAX_VALUE); // 2^31-1 范围
// 去重并排序
for (int num : inputNumbers) {
    bitSet.set(num);
}
// 输出有序结果
for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
    System.out.println(i);
}

3. 适用场景与局限

✅ 适用：数据稠密、无重复、非负整数、去重排序、用户在线统计。

❌ 局限：数据稀疏时浪费空间（比如只有两个数 0 和 2³¹-1，照样占 512MB），只能处理整数，需要做数字偏移映射。

📌 面试要点：能立刻算出 2³² bit = 512MB 是加分项。提到稀疏问题时，可以引出 RoaringBitmap 这种变种，展示你的知识广度。

插入：对元素计算 K 个哈希值，把数组对应位置置 1。
查询：同样计算 K 个哈希，若所有位置都为 1 → “可能存在”（有误判）；若任意一位为 0 → “一定不存在”。

2. 关键参数（决定误判率）

n：预计插入的元素总数
m：BitMap 的大小（bit 数）
k：哈希函数的个数

最优公式：当k = (m/n) * ln2时，误判率最低。

例如：n=1 亿，误判率 0.01%，需要 m≈1.44GB，k≈10 个哈希函数。

随着存入元素增多，被置 1 的位越来越多，误判率上升。
无法删除（因为一个位可能被多个元素共用），除非用 Counting Bloom Filter。
公式可以调整：位数组大小 m、哈希函数个数 k、预期元素数量 n，决定误判率 p。

经典参数举例：

n = 100 万，要求 p < 1%：大约需要 m ≈ 960 万 bit（约 1.2MB），k ≈ 7 个哈希函数。
内存极其节省！🎉

3. 优缺点

✅ 优点：空间效率极高（比 BitMap 还省），查询速度 O (k)，支持海量数据

❌ 缺点：存在误判率，不能删除元素（删除会影响其他元素）

4. 工业界应用

Redis 缓存穿透防护（先查布隆过滤器，不存在直接返回）
网页爬虫 URL 去重
垃圾邮件过滤
数据库查询优化（如 HBase 的 BlockCache）

5. Java 实现

直接使用 Guava 提供的BloomFilter类，无需自己实现：

// 创建布隆过滤器：预计插入100万个元素，误判率0.01%
BloomFilter<String> bloomFilter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    1_000_000,
    0.0001
);

// 插入元素
bloomFilter.put("https://baidu.com");

// 查询元素
boolean mightContain = bloomFilter.mightContain("https://baidu.com");

6. 典型应用场景

🛡️ 缓存穿透防护：过滤掉 DB 中不存在的 key。
🕷️ 爬虫 URL 去重：万亿级网页链接，用少量内存判断是否抓取过。
📧 垃圾邮件过滤：黑名单哈希快速初筛。

📌 面试要点：记住口诀“存在不一定真存在，不存在一定不存在”。能说清楚误判率与内存的权衡，给出 Guava 的实际代码，面试官会连连点头。

三者对比与选型总结 📋

技术	核心能力	误判率	支持删除	空间复杂度	典型应用
Top K	统计频率最高的 K 个元素	无	支持	O(n/m)	热搜榜、热门商品
BitMap	判断整数是否存在	无	支持	O(n/8)	整数去重、交集计算
Bloom Filter	判断元素是否可能存在	有	不支持	O(n)	缓存穿透、URL 去重

面试加分项 💯

提到Roaring BitMap：解决传统 BitMap 稀疏问题，空间效率更高，Redis、Elasticsearch 都在用
提到Counting Bloom Filter：用计数器代替 bit 位，支持元素删除
结合实际业务：比如在 Redis 缓存穿透场景中，布隆过滤器的初始化和更新策略
指出边界情况：比如 Top K 问题中如果 K 很大（如 K=100 万），小顶堆法就不适用了，需要用分治排序