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

海量数据问题基本思路

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

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

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

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

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

海量数据的存在性与去重

哈希映射 hash

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

找出两个巨大文件的共同的关键字

给定 a、b 两个文件，各存放 50 亿个关键字，每个关键字各占 64 字节，内存限制是 4G，找出 a、b 文件共同的关键字。

步骤：

分治与哈希：
- 将文件 a 中的关键字通过哈希映射到 1000 个小文件，每个文件记为 a[i]；将文件 b 中的关键字通过哈希映射到 1000 个小文件，每个文件记为 b[i]。
- 由于哈希映射的特点，相同关键字只会被分到 a[i] 或 b[i] 中。
对每个 i 求相同关键字：
- 将 a[i] 文件中的关键字放入哈希表 H 中；
- 遍历 b[i] 逐个关键字 k 判断是否在哈希表 H 中；
- 如果关键字 k 在 H 中出现，那么将 k 加入结果中。

如果判重允许一定错误率，可考虑布隆过滤器。

字典树 Trie

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

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

对 1000 万字符串进行去重

步骤：

对于大型集合，我们可以先用 Hash 分成小文件；
再用去重方法（Hash、Trie）对小文件去重；
最后综合再去重。

位图 Bit-map

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

统计大文件中不同数字的个数

已知某个文件内包含一些数字号码，每个号码为 8 位数字，统计不同号码的个数。

解法：使用 Bit-map，从 0-99999999 的数字，每个数字对应一个 Bit 位。

找出不重复的整数的个数

2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这 2.5 亿个整数。

解法 1：

按整数范围划分区域，每个单文件代表一个区域。
对每一个区域，使用 Bit-map 的扩展，用 2bit 表示一个数，0 表示未出现，1 表示出现一次，2 表示出现 2 次及以上，在遍历这些数的时候，如果对应位置的值是 0，则将其置为 1；如果是 1，将其置为 2；如果是 2，则保持不变。
或使用两个 Bit-map 进行模拟。

解法 2：

哈希分成多个小文件，在每个小文件中找出不重复的整数，并排序
使用归并，同时注意去除重复元素

使用位图判断存在性

给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？

解决方案：使用位图申请 512M 的内存，一个 bit 位代表一个 unsigned int 值。读入 40 亿个数，设置相应的 bit 位，读入要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在。

布隆过滤器 Bloom Filter

布隆过滤器基于位图。

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

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

优缺点：

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

Counting Bloom Filter 解决布隆过滤器无法删除的弊端

Counting Bloom Filter 将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter）：

在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1
删除元素时给对应的 k 个 Counter 的值分别减 1。

Counting Bloom Filter 通过多占用几倍的存储空间的代价，给 Bloom Filter 增加了删除操作。

看图读原理：

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

使用场景：

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

海量数据的排序

桶排序

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

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

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

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

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

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

海量订单数据的排序

假设有 10GB 的订单金额数据需要排序，金额均为正整数，但我们的内存只有 500MB。应该如何排序？

步骤：

扫描文件，定金额范围：假设最小为 1 元，最大为 10w 元，假设金额均匀分布
订单根据金额划分到 100 个桶：1-1000、1001-2000…
每个桶（每个待排序的文件）存储约 100M 的数据，符合内存要求，可以进行快速排序
按照桶的顺序读取订单的数据

解决订单不均匀分布：

继续划分金额集中分布的区间为更小的区间。如将 1-1000 的区间划分为 1-100、101-200…
如果某个区间数据还是过大，则继续划分，直到所有文件都能读入内存为止。

根据年龄给 100 万用户排序

假设年龄的范围最小 1 岁，最大不超过 120 岁，请根据年龄给 100 万用户排序。

我们可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

同类问题：按照成绩给 50 万考生排序。

计数排序

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

计数排序是稳定的。

算法过程：

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

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

COUNTING-SORT(A,B,k)
	// 初始化额外空间，数组中，可能出现的值的范围为low至low+k
	for i=0 to k
		C[i] = 0
	// 遍历数组 A，统计每个值出现的次数
	for j=1 to A.length
		C[A[j]] +=1
	// 依次计算比i小或与i相等的元素的个数
	for i=1 to k:
		C[i] += C[i-1] // 前缀和
	// 此时得到的C数组表明，如果下标i在A数组中存在的话，i应该是结果的第C[i]个位置

	// B为结果数组，现依据A数组元素逆序，决定该元素应该在结果数组的哪一个位置
	// 注意此时 C 为前缀和数组
	for j = A.length downto 1
		B[C[A[j]]] = A[j] 
		C[A[j]] -=1

案例：计数排序

以输入数组 [95,94,91,98,99,93,91,92] 为例。

复杂度分析：

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

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

基数排序 Radix Sort

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

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

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

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

算法：

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

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

基数排序一般使用 LSD 对数据进行排序的原因

因为数字大小本身就是高位的权重更大，排序轮数越靠后，相当于其权重越高。
可以使用 MSD，不过会更加复杂。使用 MSD 时，需要按照高位分桶。每个桶继续分小桶，形成递归。

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

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

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

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

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

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

二叉堆与堆排序

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

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

二叉堆的两种形式：

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

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

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

堆的操作	时间复杂度	算法概述
堆化	$\Theta(\lg n)$	对一个结点进行「下沉」
建堆	$O(n)$	从中间往前，进行堆化
弹出堆顶	$O(\log n)$	弹出后，最后一个元素放堆顶，再堆化，防止空洞
插入堆		放最后，「上浮」
更新堆键值		更新键后，「上浮」
堆排序	$O(n\lg n)$	建堆；一个个弹出。原址排序的话，弹出位置放堆后，堆大小减减即可。

归并排序

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

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

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

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

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

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

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

外部排序

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

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

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

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

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

多路归并

大文件排序

假定现在有一包含大量整数的文本文件存放于磁盘中，其文件大小为 10GB，而本机内存只有 1GB。如何对文件内容进行排序？

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

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

中间问题：有序小文件合并为有序大文件

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们如何将这些 100 个小文件合并成一个有序的大文件？

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

步骤	时间复杂度
从 100 个文件各取一个字符串，放入数组并建小顶堆。	$O(k), k = 100$
弹出堆顶元素，放入大文件中。	$O(\log k)$
再从堆顶元素所属的文件中取出字符串插入小顶堆	$O(\log k)$

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

海量数据 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(k)$
顺序遍历数组	$O(n)$
- 如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中	$O(\log k)$
- 如果比堆顶元素小，则不做处理，继续遍历数组。	$O(1)$

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

此处可以使用快速排序。

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

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

添加数据
查询当前 Top K

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

更高效的步骤：

步骤	时间复杂度
如果一开始没建堆，则维护一个大小为 K 的小顶堆	$O(k)$
当有数据被添加到集合中时，我们就拿它与堆顶的元素对比	-
- 如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中	$O(\log k)$
- 如果比堆顶元素小，则不做处理	$O(1)$

使用有序数组维护 Top K 列表不会更加高效

使用有序数组维护 Top K 列表并不比堆高效。

如一开始没构建有序数组，那么它的构建时间为 $O(k\log k)$
插入数据时，二分方式找到插入的位置为 $O(\log k)$ ，移动元素需 $O(k)$

相对于有序数组而言，堆的主要优势在于插入和删除数据效率较高。

相似问题：巨型数据集合 Top K

100w 个数中找出最大的 K 个数。

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

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

改进版的快速排序算法不会比堆高效

采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 K 多的时候，采用传统排序算法排序，取前 K 个。

时间复杂度： $O(N*k)$

求词频 Top K

求一个大文件中的 Top K 关键词

现有一个包含 10 亿个关键词的日志文件，可用内存为 1G。求 Top 10 频数最多的关键词。

对应的 Top 1 问题：在海量数据中找出重复次数最多的一个关键词。
对应的 Top N 问题：词频排序。

步骤：

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

求分布在不同文件中的 Top K 关键词

现有多个不同的存储关键词的文件，每个关键词可能分布于多个文件中。求不同文件中的 Top K 关键词。

相似问法：不同机器中的 Top K 关键词

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

解决方法：

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

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

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

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

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

元素动态添加时：

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

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

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

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

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

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

快速求接口的 99% 响应时间

如果将一组数据从小到大排列，这个 99 百分位数就是大于前面 99% 数据的那个数据。

做法：维护两个堆，一个大顶堆，一个小顶堆。假设当前总数据的个数是 n，大顶堆中保存 n⨯99% 个数据，小顶堆中保存 n⨯1% 个数据。数据的插入和查询前的调整规则类似前面中位数的要求。最后，每次查询大顶堆堆顶的数据就是我们要找的 99% 响应时间。

通过分片统计求中位数

从海量整数中找到中位数

求 5 亿个 int 的中位数。

步骤：

将 int 划分为 $2^{16}$ 个区域，然后读取数据统计落到各个区域里的数的个数。
根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。
第二次扫描我们只统计落在这个区域中的那些数即可。

如果整数的范围更大，我们可以进行多层次的划分，使每个区域降到可接受的程度。

海量数据的增删改查

数据库索引

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

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

倒排索引 Inverted index

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

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

# 下面是被索引的文本
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）。

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

本文参考

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

关于海量数据的若干问题