> For the complete documentation index, see [llms.txt](https://gists.lanlance.cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gists.lanlance.cn/cs/al.md).

# 数据结构与算法

## 1. 1 亿个 IP 地址，如何去取 Top3

首先，将 1 亿个 IP 地址按照哈希函数的值分成 1024 个桶，每个桶里面存储的是对应哈希值的 IP 地址。然后，对于每个桶，用哈希表统计桶内每个 IP 的出现次数，并取出该桶内出现次数最多的 3 个 IP 作为候选（注意：不能只取每个桶的 Top1，因为全局 Top3 可能集中在同一个桶内，那样会漏掉真正的 Top3；取每桶 Top3 就已足够，因为全局 Top3 的每个元素必然位于它所在桶的前三名）。最后，将所有桶取出的候选 IP 按出现次数合并排序，取出前三个即可。

## 2. 七大排序时间复杂度与稳定性

七大排序算法的时间复杂度和稳定性如下：

| 排序算法 |       时间复杂度      | 稳定性 |
| :--: | :--------------: | :-: |
| 冒泡排序 |      O(n^2)      |  稳定 |
| 选择排序 |      O(n^2)      | 不稳定 |
| 插入排序 |      O(n^2)      |  稳定 |
| 希尔排序 | O(nlogn)\~O(n^2) | 不稳定 |
| 快速排序 | O(nlogn)\~O(n^2) | 不稳定 |
| 归并排序 |     O(nlogn)     |  稳定 |
|  堆排序 |     O(nlogn)     | 不稳定 |

## 3. 快速排序、归并排序、堆排序

* 快速排序：快速排序是一种基于分治思想的高效排序算法。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
* 归并排序：归并排序是一种基于分治思想的高效排序算法。它的基本思想是将待排元素分成大小大致相等的两个子集合，分别对这两个子集合进行递归处理，直到子集合中只有一个元素为止，然后将两个子集合合并成一个有序序列。
* 堆排序：堆排序是一种基于堆结构的高效排序算法。它的基本思想是将待排元素构造成一个堆，然后依次取出堆顶元素（最大或最小），再将剩余元素重新构造成一个堆，重复上述操作直到所有元素都被取出。

## 4. 令牌桶算法原理

令牌桶算法是一种流量整形算法，它可以平滑地限制数据的传输速率，同时允许一定的突发流量。令牌桶算法的原理是系统会以一个恒定的速率往桶里放入令牌，桶有容量上限（超过则丢弃新令牌），而如果请求需要被处理，则需要先从桶里获取一个令牌；桶里有令牌时请求可以被立即处理（突发时桶内积攒的令牌可以一次性消耗），当桶里没有令牌可取时，请求则需要排队等待或被丢弃（依实现而定）。

## 5. 红黑树、avl 的复杂度

红黑树和 AVL 树都是常用的平衡二叉树，它们查找、插入、删除的时间复杂度都是 O(logn)。AVL 树是严格平衡的（任意节点的左右子树高度差不超过 1），树更矮，因此查找效率略高于红黑树；红黑树是近似平衡（平衡条件更宽松），插入和删除时所需的旋转和重新着色次数比 AVL 树更少（具体来说，AVL 树插入最多 2 次旋转，但删除最多可能需要 O(logn) 次旋转；红黑树插入最多 2 次、删除最多 3 次旋转，额外代价主要在 O(logn) 次重新着色），因此维护成本更低，在频繁插入和删除的场景下统计性能更好。（注：上述为传统主流观点；2024 年基准研究 arXiv:2406.05162 表明，在某些工作负载下 AVL 树的插入/删除反而更快，两派结论均有实验支撑。）

## 6. 红黑树简介

红黑树是一种自平衡的二叉搜索树，它在计算机科学中被广泛应用。它的名称来自于树中节点的颜色，每个节点要么是红色，要么是黑色。红黑树具有以下特性：

1. 根节点是黑色的。
2. 每个叶子节点 (NIL 节点，空节点) 都是黑色的。
3. 如果一个节点是红色的，则它的两个子节点都是黑色的。
4. 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点，这个数量称为该节点的**黑高度**。
5. 由上述性质可推出平衡保证：从任意节点到其叶子节点的所有简单路径中，最长路径的长度不超过最短路径的两倍（每条路径上黑色节点数量相同，且红色节点不能连续出现，因此最长路径上的红色节点数至多等于黑色节点数）。

这些特性保证了红黑树的平衡性，使得它的高度始终保持在可接受的范围内。红黑树的高度是 O(logn)，其中 n 是树中节点的数量。

红黑树的自平衡性是通过在插入和删除操作后进行调整来实现的。插入和删除操作可能会破坏红黑树的特性，但通过一系列的旋转和重新着色操作，可以保持红黑树的平衡性。

红黑树在许多领域都有广泛的应用，特别是在需要高效地进行插入、删除和搜索操作的场景中。它的时间复杂度在平均和最坏情况下都是 O(log n)，使得它成为一种非常有效的数据结构。

## 7. 哈希查找时间复杂度

哈希查找的时间复杂度通常被认为是 O(1)。这是因为哈希表利用哈希函数将键映射到数组的特定位置，使得对于任意给定的键，可以通过哈希函数快速计算出其对应的存储位置。在平均情况下，哈希表的搜索、插入和删除操作的时间复杂度都是 O(1)。然而，在最坏情况下，如果发生大量的哈希冲突，哈希表的性能会退化成 O(n)。

## 8. 快排为什么不稳定

当快速排序中的枢纽元与其他元素进行交换时，可能会改变相同键值的元素的相对顺序。例如，如果有两个相同的元素 A 和 B，且 A 在 B 的前面，但在排序过程中，A 被移动到了 B 的后面，那么相同键值的元素的相对顺序就发生了改变。这就是快速排序不稳定的一个例子。一个具体反例：序列 \[2a, 2b, 1]（2a、2b 值相同），用 Lomuto 划分法取末尾元素 1 作枢纽元，第一趟会把 1 与 2a 交换得到 \[1, 2b, 2a]，两个相等元素的相对顺序就被改变了。

## 9. 跳表原理

跳表基于链表实现，通过在原始链表的基础上建立多层索引来加速查找操作。跳表的原理是通过每两个节点抽出一个节点，建立索引层，从而减少查找路径，降低查找时间复杂度。具体原理如下：

1. 遍历有序链表时，需要从头节点开始逐个节点遍历，直到找到目标节点。这种遍历方式的时间复杂度是 O(n)。
2. 跳表的思想是每两个节点抽出一个节点，建立第一层索引。第一层索引的节点个数是原始链表节点个数的一半。
3. 在第一层索引的基础上，再每两个节点抽出一个节点，建立第二层索引。第二层索引的节点个数是第一层索引节点个数的一半。
4. 以此类推，建立多层索引，直到达到某个条件（如节点个数小于等于 2）为止。
5. 当需要查找数据时，从最高层索引开始，逐层向下查找，直到找到目标节点或者找不到为止。
6. 在每一层索引中，通过比较节点的值，确定下一步的查找方向，可以快速缩小查找范围。
7. 如果在某一层索引中找到目标节点，则返回该节点；如果在最底层索引中仍然找不到目标节点，则表示数据不存在。

跳表的查询时间复杂度平均为 O(log⁡(n))（期望复杂度；随机化结果最差时可能退化为 O(n)），其中 n 是原始链表的节点个数。跳表的插入和删除操作也可以通过类似的方式进行实现，时间复杂度也是 O(log⁡(n))。跳表的优势在于可以在不使用平衡树的情况下，实现高效的查找、插入和删除操作。

## 10. 有哪些常见的二叉树

1. **满二叉树**：
   * 每个非叶子节点都有两个子节点，且所有叶子节点都在同一层。（注：" 满二叉树 " 存在两种定义，另一种定义为 " 每个节点要么没有子节点、要么有两个子节点 "，不要求叶子节点在同一层；两种定义在不同教材中均有使用。）
2. **完全二叉树**：
   * 除了最后一层外，每层的节点数都达到最大，且最后一层的节点集中在最左边。
3. **二叉搜索树（Binary Search Tree, BST）**：
   * 对于每个节点，左子树的所有节点值小于该节点，右子树的所有节点值大于该节点。中序遍历该树会得到一个有序序列。
4. **平衡二叉树**：
   * 也称 AVL 树，要求每个节点的左右子树高度差不超过 1，确保树的高度保持在对数级别，从而提高查找效率。（注：严格说「平衡二叉树」是泛指，AVL 树是最典型的一种；红黑树属于近似平衡，也归入平衡二叉搜索树。）
5. **红黑树**：
   * 一种自平衡的二叉搜索树，每个节点有颜色属性（红或黑），并遵循特定的性质以保持树的平衡。
6. **哈夫曼树**：
   * 一种带权路径长度最小的二叉树，通常用于数据压缩。

## 11. 跳表和红黑树的优劣对比

### 时间复杂度

* **查询**：跳表和红黑树的平均时间复杂度均为 O(log⁡n)，但在最坏情况下，跳表的查询复杂度可能达到 O(n)，而红黑树则保持在 O(log⁡n)。
* **插入和删除**：跳表的插入和删除操作相对简单，通常只涉及指针的调整，时间复杂度为 O(log⁡n)。红黑树的插入和删除则需要进行复杂的平衡调整，旋转和着色操作，因此实现较为复杂，但时间复杂度同样为 O(log⁡n)。

### 空间复杂度

跳表的空间复杂度较高，因为它需要额外的指针来维护多层结构，通常为 O(n)。相比之下，红黑树的每个节点只需要存储颜色信息和指向父节点的指针，整体上占用的内存较少。（注：这一对比存在争议：跳表每个节点平均约需 2 个前向指针，而红黑树每个节点需要 left/right/parent 共 3 个指针外加颜色位，实际两者内存开销差异不大，甚至红黑树可能更高，具体取决于实现。）

### 实现复杂度

* **跳表**：实现较为简单，易于理解和调试，尤其适合快速开发和原型设计。跳表的结构类似于链表，插入和删除操作相对直接。
* **红黑树**：实现复杂，需要处理多种情况以保持树的平衡，涉及旋转和颜色调整，增加了开发和维护的难度。

### 并发性能

在并发环境下，跳表的更新操作相对较少，锁的竞争较低，因此在多线程环境中表现良好。而红黑树在并发操作时，由于其复杂的平衡调整，可能会导致更多的锁竞争。

### 应用场景

* **跳表**：由于其简单性和良好的性能，跳表常用于需要快速插入、删除和查找的场景，如 Redis 的有序集合（zset）实现中。
* **红黑树**：适用于对性能要求较高且需要频繁查找的场景，如许多标准库中的集合实现（C++ 的 std::map/std::set、Java 的 TreeMap/TreeSet、Linux 内核的 epoll 与 CFS 调度器），特别是在插入/删除频繁、又只需近似平衡（而不是 AVL 那样的严格高度平衡）时。

## 12. 哈希冲突有哪些常见的解决方法

1. **链地址法（拉链法）**：每个桶挂一条链表存放冲突元素。Java HashMap 在链表长度超过 8 且桶数组长度 ≥ 64 时会转成红黑树，把最坏查询从 O(n) 降到 O(logn)。
2. **开放寻址法**：按探测序列找下一个空槽，包括线性探测、二次探测、双重散列。装载因子过高时性能急剧退化，必须控制装载因子并及时扩容（如 Java 的 ThreadLocalMap 用线性探测）。
3. **再哈希法**：用第二个哈希函数重新计算位置，直到找到空槽（可能失败）。
4. **建立公共溢出区**：冲突的元素统一放进溢出区。

## 13. 快速排序的最坏情况与优化

* 最坏情况：每趟划分都极度不平衡时（例如数组本就有序，却固定取第一个/最后一个元素作枢纽元），递归深度退化成 O(n)，时间复杂度变成 O(n^2)，递归栈还可能溢出。
* 常用优化：① 三数取中或随机选取枢纽元，避免有序输入退化；② 小区间（如长度 < 15）改用插入排序；③ 三路划分（< 、= 、> 三段，即荷兰国旗问题），大量重复元素时也能保持高效；④ 先递归处理较短的一侧，把递归栈深度控制在 O(logn)。
* 平均时间复杂度 O(nlogn)，空间复杂度 O(logn)（递归栈），原地排序但不稳定。

## 14. 如何求 TopK / 第 K 大元素

* **小顶堆**：遍历数据维护一个大小为 K 的小顶堆，堆顶就是当前第 K 大，遍历完得到结果。时间 O(nlogK)、空间 O(K)，适合 n 很大、K 很小的场景（也适用于数据流）。
* **快速选择（QuickSelect）**：基于快排的划分，每趟只递归包含目标的那一半，平均 O(n)、最坏 O(n^2)（随机化枢纽元可避免）；BFPRT（中位数的中位数）能把最坏情况也做到 O(n)。
* **海量数据（内存放不下）**：先哈希分治到多个文件，每个文件各自求 TopK，再合并归并（见第 1 题）。

## 15. 二叉树的遍历方式

* 深度优先：前序（根左右）、中序（左根右）、后序（左右根），递归写法最简单，非递归写法用显式栈模拟；中序遍历二叉搜索树得到的是有序序列。
* 广度优先：层序遍历用队列实现，按层输出时可以在每轮循环里先记录当前队列长度。
* Morris 遍历：借助叶子节点的空指针临时指向中序前驱，实现 O(1) 空间的中序遍历，代价是遍历中会临时改写树的结构（遍历结束前恢复）。

## 16. LRU 与 LFU 缓存淘汰算法

* **LRU（最近最少使用）**：哈希表 + 双向链表，哈希表负责 O(1) 定位节点，双向链表维护访问顺序（新访问的移到头部），淘汰时删除尾部节点，get/put 均为 O(1)。缺点是偶发的批量扫描会把热点数据全部挤出去。
* **LFU（最不经常使用）**：按访问频次淘汰，频次相同时再按最近使用淘汰；O(1) 实现通常是「哈希表 + 频次桶（每个频次一条双向链表）」，但要额外处理历史热点的频次老化问题。
* 工程上更常见的是近似实现：Redis 采用「近似 LRU + 随机采样」，而不是严格 LRU。

## 17. 布隆过滤器

* 原理：一个位数组 + k 个哈希函数。插入时把 k 个哈希位置置 1；查询时只要有一位是 0 就一定不存在，全为 1 则是「可能存在」。
* 特点：不存原始元素，空间效率极高，查询 O(k)；但存在误判（假阳性），且不支持删除（要删除需换成计数布隆过滤器）。
* 参数：位数组大小 m、元素个数 n 时，最优哈希函数个数 k = (m/n)·ln2，此时误判率约为 (0.6185)^(m/n)。
* 典型用途：缓存穿透拦截、爬虫 URL 去重（Guava 的 BloomFilter、Redis 的 RedisBloom 模块）。

## 18. 位图 BitMap：海量数据去重与排序

* 位图用一个 bit 标记某个数是否出现过，1 亿个整数（值域 0 \~ 1 亿）只需约 12.5 MB。
* 用位图可以对大整数集合做 O(n) 的去重与排序（按 bit 顺序扫描输出）；40 亿个整数找出一个不存在的数，用约 512MB 的位图按区间分段处理即可。
* 局限：只适合值域集中的整数，稀疏数据会浪费空间，稀疏场景可用 Roaring Bitmap 或哈希分片替代。

## 19. KMP 字符串匹配

* 核心是用模式串自身的 next（前缀）数组记录每个前缀的最长相等前后缀长度：匹配失败时主串指针不回溯，模式串指针回退到 next\[j]，把朴素匹配的 O(mn) 降到 O(m+n)。
* next 数组的求法与匹配过程同构，相当于模式串「自己和自己匹配」；空间复杂度 O(m)。