本文为面试笔记整理。以前看八股总是随缘，没有系统的整理。现在秋招，正好有机会把各种八股和以前学过的东西都串联起来，给笔记清清灰。

海量数据问题基本思路

看到海量数据的处理问题，可以按以下思想考虑：

1. 分治。一看到数据量但内存受限的问题首选分治。但是海量数据基本都要分治，可以作为一种基础思想。
2. 哈希。耗内存，但适合快速查找。
3. Bit 位。如位图、布隆过滤器。适用于快速查找、判重。
4. 堆。Top K、最值问题。注意 K 不要过大，需要能放进内存。

本文将针对处理海量数据的不同场景，引出相应的数据结构或算法：

1. 海量数据的存在性与去重：哈希映射、字典树、位图、布隆过滤器
2. 海量数据的排序：桶排序、计数排序、基数排序、堆与堆排序、归并排序
3. 海量数据的 Top K 问题：堆的应用
4. 海量数据的中位数及任意百分位的数据：堆与分片
5. 海量数据的增删改查：索引与倒排索引
6. 海量数据的分布式处理：MapReduce

需要注意的是。对于海量数据的处理，我们会综合使用多种数据结构进行处理，每一种数据结构不一定只会解决同一种问题。

海量数据的存在性与去重

哈希映射 hash

哈希映射的特点就是，同一个关键字将映射到相同的位置。

字典树 Trie

哈希 Map、字典树可以对小型集合的数据进行去重。

Trie 树适合数据量大，重复多，但是数据种类小可以放进内存的情景。

位图 Bit-map

位图是一种特殊的散列表。

布隆过滤器 Bloom Filter

布隆过滤器基于位图。

它的数据结构由两部分组成：

• 二进制向量（位数组）：一个大的 bit 数组来保存所有的数据，数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1
• 一系列随机映射函数（哈希函数）

优缺点：

• 优点：占用空间更少并且效率更高
• 缺点：返回的结果是概率性的。理论情况下，添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

看图读原理：

• 数据加入时：用多个哈希函数得到哈希值，并将位数组对应位置 1。
• 查询存在性：以相同方式得到哈希。全为 1，数据可能在；不全为 1，数据一定不在。

使用场景：

• 判断给定数据是否存在：
  • 判断一个数字是否存在于包含大量数字的数字集中（数字集很大，上亿）
  • 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）
  • 邮箱的垃圾邮件过滤（判断一个邮件地址是否在垃圾邮件列表中）
  • 黑名单功能（判断一个 IP 地址或手机号码是否在黑名单中）
• 去重：
  • 比如爬给定网址的时候对已经爬取过的 URL 去重
  • 对巨量的 QQ 号/订单号去重。
• 集合求交集

海量数据的排序

桶排序

核心思想：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

假设要排序的对象有 n 个，划分到 m 个桶中。时间复杂度 O(n)O(n)：

• 理想情况下，每个桶有 k = n/m 个元素
• 每个桶使用快排算法：O(klog⁡k)O(k \log k)
• m 个桶排序的时间复杂度：m×O(klog⁡k)=O(nlog⁡n/m)m\times O(k \log k) = O(n \log n/m)
  • 当 m 趋于 n 时 log⁡n/m\log n/m 就是一个很小的常量，这时桶排序的时间复杂度为 O(n)O(n)
  • 极端情况下，所有数据被分到一个桶中，时间复杂度退化为 O(nlog⁡n)O(n\log n)

桶排序对要排序数据的要求是非常苛刻：

• 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
• 数据在各个桶之间的分布是比较均匀的。否则桶内数据排序的时间复杂度就不是常量级别。

桶排序适合用在外部排序中。

计数排序

计数排序是由额外空间的辅助和元素本身的值决定的。 计数排序过程中不存在元素之间的比较和交换操作， 根据元素本身的值， 将每个元素出现的次数记录到辅助空间后， 通过对辅助空间内数据的计算， 即可确定每一个元素最终的位置。

计数排序是稳定的。

算法过程：

1. 根据待排序集合中最大元素和最小元素的差值范围， 申请额外空间；
2. 遍历待排序集合， 将每一个元素出现的次数记录到元素值对应的额外空间内；
3. 对额外空间内数据进行计算， 得出每一个元素的正确位置；
4. 将待排序集合每一个元素移动到计算出的正确位置上。

从某些角度来看，计数排序是桶排序的特殊情况。相当于同一个元素值放到 1 个桶中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

COUNTING-SORT(A,B,k)
	
	for i=0 to k
		C[i] = 0
	
	for j=1 to A.length
		C[A[j]] +=1
	
	for i=1 to k:
		C[i] += C[i-1] 
	

	
	
	for j = A.length downto 1
		B[C[A[j]]] = A[j] 
		C[A[j]] -=1   

复杂度分析：

• 时间复杂度：O(n+k)O(n+k)。k 表示数据范围，n 表示待排序的数字个数。
• 空间复杂度：O(n+k)O(n+k)。k 表示数据范围，n 表示待排序的数字个数。

计数排序适用于数据范围 k 不大的场景中。计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序 Radix Sort

基数排序是一种非比较型整数排序算法，它是基于关键字各位大小来排序。它的基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。

设长度为 n 的线性表中每个结点 aja_j 的关键字由 d 元组 (kjd−1,kjd−2…,kji,...,kj1,kj0)(k^{d-1}_j,k^{d-2}_{j}\dots,k_{j}^i ,...,k^{1}_j,k^{0}_j) 组成

• 0≤k≤r−10\le k \le r-1。即每个数位范围不超过 r。如十进制数时，r=10r=10。
• 0≤j<n,0≤i≤d−10\le j <n,0\le i \le d-1。
• 其中 kjd−1k^{d-1}_j 为最主位关键字，kj0k^{0}_j 为最次位关键字。

对于不等长的排序数据，可以对数据前/后进行补齐。

算法：

1. 最低位优先（LSD）法。对于一个数据序列的从小到大排序，应采用 LSD。
2. 最高位优先（MSD）法

基数排序是稳定的排序算法。

时间复杂度：O(d(n+r))O(d(n+r))

• 每位进行一趟「分配」和「收集」，共 d 趟
  • 一趟分配需要 O(n)O(n)。使用计数或桶排序（桶排序算法需留意稳定性）。
  • 一趟收集需要 O(r)O(r)。
• 与序列初始状态无关
• 当 r 是常数且 d 较小时，基数排序可在线性时间内完成。

空间效率：O(n+r)O(n+r)

• r 个队列（桶）存储临时结果：r 个队头指针和队尾指针

基数排序适用于对整数或可以表示为固定长度数字序列的对象进行排序。特别是当待排序的数据范围比较固定，且位数相对较少时，它的效率很高：

• 手机号码（11 位数字）
• 身份证号码（18 位数字）
• 日期（将日期转换为数字表示）

二叉堆与堆排序

本小节整理自笔记，更具体的证明与性质详看本地知识库。

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树。

二叉堆的两种形式：

• 最大堆：最大堆的性质：除了根结点以外的所有结点 i 都要满足 A[PARENT(i)]≥A[i]A[PARENT(i)]\ge A[i]
• 最小堆：最小堆的性质：除了根结点以外的所有结点 i 都要满足 A[PARENT(i)]≤A[i]A[PARENT(i)]\le A[i]

我的简记：小顶堆装大数、大顶堆装小数。

对堆（大顶堆）操作算法快速回忆：

归并排序

思想：如果能把原待排序的数组分解成若干个待排序的子数组，而这些子数组可以方便地排好序，并且通过合并这些子数组的解将能得到原问题的解，则整个数组将排好序。

2 路归并排序通过应用分治法解题的三个基本步骤为：

1. divide：把具有 n 个元素的数组分解为二个 n/2 大小的子数组
2. conquer：递归地分解子数组，直到子数组只包含一个元素为止
3. combine：二二合并已排好序的子数组使之成为一个新的排好序的子数组，重复这样二二合并的过程直到得到原问题的解

归并排序不能保证一趟结束后一定有元素放在最终位置上。可以说是基本算法中占用辅助空间最多的排序算法。有方法克服但代价是算法会很复杂，且时间复杂度会增加。

归并排序是一种稳定的算法。平均时间复杂度为 O(nlog⁡n)O(n\log n) 的稳定排序算法只有归并排序。

从单个记录起两两归并的做法不提倡，可以和直接插入排序结合，利用直接插入排序求得较长的有序文件，然后两两归并（两种算法都是稳定的排序算法，结合起来也是稳定的）。

归并排序一般用于外部排序使用。

外部排序

外部排序在排序过程中根据要求不断在内、外存之间移动。

外部排序使用归并排序法：

1. 根据内存缓冲区大小，将外存文件分为若干子文件，依次读入内存，使用内部排序方法进行排序，然后再重新写回外存。这些有序子文件称为归并段或顺串。
2. 对归并段进行逐趟归并，使归并段逐渐由小到大，直到得到整个有序文件。

磁盘 I/O 优化方法——减少排序趟数：

• 多路平衡归并与败者树（增加归并路数 k）
• 置换 - 选择排序（生成初始归并段）（减少初始归并段个数 r）
• 最佳归并树

多路归并

由于内存限制，我们无法一次性将文件读入内存进行排序。解决方法：

• 将 10GB 大文件拆分为 100 个 100MB 的小文件。
• 分别对 100 个小文件进行排序。

解决方法：使用优先队列（小顶堆）进行有序序列的多路归并。

多路归并的过程可以找中位数。

相关算法题目：

• 🟥 23. 合并 K 个升序链表 - 力扣（LeetCode）
• 🟨 373. 查找和最小的 K 对数字 - 力扣（LeetCode）

海量数据 Top K 问题

根据集合的特点，将 Top K 问题分成两类：

• 静态数据集合 Top K。在事先确定且不会变动的数据集合中求 Top K。
• 动态数据集合 Top K。集合事先不确定，且有动态的数据加入到集合中。在这种集合上求 Top K。

Top K 问题可以的狭义理解可以理解为：

• Top 1：求数据集合中最大的元素。
• Top N：求排好序的数据集合。

使用堆：小型静态数据集合 Top K

适合数据量小的数据集合。

在一个包含 n 个数据的静态数组中，查找前 K 大数据。

ME：小堆装大数，让大的下沉保留。

这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。每次查询花费 O(nlog⁡k)O(n \log k)。

使用堆：动态数据集合 Top K

要想知道实时 Top K，需要进行两个操作：

• 添加数据
• 查询当前 Top K

如果查询 Top K 时使用静态数据集合的方法，那么每次查询将花费 O(nlog⁡k)O(n \log k)。

更高效的步骤：

我们可以沿用使用堆处理动态数据集合 Top K 方法：

• 先构建大小为 K 最小堆；
• 再把剩余数据一个个以相似的方式插入堆即可。

求词频 Top K

步骤：

• 使用哈希算法取模分片，分到 10 个文件中，保证相同的词都放在一个文件里。注意不叫分桶，因为桶排序中桶与桶之间是有序的！
• 每片分别读入内存，通过散列表、平衡二叉查找树、红黑树、Trie 树等数据结构记录词频。
• 每片词频排序方法：
  • 使用动态数据集合 Top K 方法排序：建小顶堆。
  • 求 Top N 或数据量小时：建小顶堆或快速排序。
• 组合每片的词频进行最后的排序：
  • 把每片的 Top K 进行多路归并（使用堆），再取 Top K 即可。
  • 求 Top N 或数据量小时：直接合在一起，再用快速排序。或归并排序。

在前一个问题中，我们使用哈希算法取模分片保证了相同的词只会放在同一个小文件中。本问题稍微有些不同：一开始每个关键词可能分布于多个文件中。

解决方法：

• 方法 1：遍历一遍所有数据，重新哈希取模分片，并沿用上一个问题的解决步骤进行问题求解。
• 方法 2：暴力法。直接统计统计每个文件中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出 Top K。

海量数据的中位数或任意百分位的数据

使用堆求中位数或任意百分位的数据

静态数据的中位数是固定的，我们可以先排序，再直接取。对于动态数据集合，如果每次查询中位数前都要排序则效率不高。

正确的方法为利用两个堆：大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

元素动态添加时：

• 如果新加入的数据小于等于大顶堆的堆顶元素，加入大顶堆
• 否则加入小顶堆

查询中位数前，需保证大顶堆元素和小顶堆元素数量比例正确：

• 我们需要保证：前半部分数据放大顶堆，后半部分数据放小顶堆。如果 n 为奇数，多出的一个放大顶堆中。
• 如果查询前两个堆的元素个数不满足条件，则将某一个堆的元素插入到另一个堆中，直到条件满足。

取出中位数的方式 O(1)O(1)：

• 如果 n 是偶数，大顶堆堆顶元素和小顶堆的堆顶元素即为所求。
• 如果 n 是奇数，大顶堆堆顶元素即为所求。

如果要求任意百分位的数，原理是相似的。

通过分片统计求中位数

海量数据的增删改查

数据库索引

适用范围：大数据量的增删改查

基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

倒排索引 Inverted index

适用范围：搜索引擎，关键字查询。

倒排索引是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

1
2
3
4
5
6
7
8
9
10
11
12

# 下面是被索引的文本
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"


# 下面是反向文件索引
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

常见问题：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

海量数据的分布式处理

可以看成大量数据被分为小文件的场景。

MapReduce

类似归并排序。

MapReduce 是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。

任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。

相关问题：

• 海量数据分布在 100 台电脑中，想个办法高效统计出这批数据的 Top 10。

本文参考

• 研究生课程《算法设计与分析》课程内容，以及课后实验二：典型排序算法训练
• 《算法导论》第 6 章
• 《王道 2023 408》思维导图解耦
• 《算法与数据结构之美》王争-极客时间专栏
• 全面解析基数排序：定义、原理、复杂度、稳定性及实现步骤详解 - 软件职业规划 - 博客园
• 为什么基数排序只有从最低位开始才是“稳定的排序算法”？？ - 知乎
• 布隆过滤器 | JavaGuide
• 海量数据问题的处理-六种解决思路 - Garrett_Wale - 博客园
• 多路归并算法从理论到应用（易懂）-CSDN博客
• Counting Bloom Filter 的原理和实现-腾讯云开发者社区-腾讯云
• 海量数据处理面试题集锦-CSDN博客
• 45 位图：如何实现网页爬虫中的URL去重功能？ - 极客时间文档 - 王争 - 数据结构之美与算法之美