前言
「海量数据」通常指一个具体情况：数据量超过可用内存，或者超过单次遍历能承受的时间。比如「40 亿个整数、1 GB 内存，判断某个数是否存在」。这类问题的解法并不神秘，真正需要的是把「存不下」拆成几个能分别处理的小问题。
常见的思路只有五类：分而治之（哈希分桶、外部排序）、位图、布隆过滤器、堆（求 Top K）、近似统计结构。每一类都有明确的适用条件，选错的代价往往不是慢一点，而是结果错误或内存直接爆掉。本文按这个顺序逐一梳理，代码都是单机、标准库范围内的实现。
一、先把问题的量算清楚
动手之前先算三个数：数据总量、可用内存、单个元素占多少字节。这一步能直接排除掉一半的错误方案。
举几个典型规模：
| 场景 | 数据量 | 原始存储 | 关键观察 |
|---|
40 亿个uint32 | 4×10⁹ 个 | 约 16 GB | 每个值只有 2³² 种可能 |
| 10 亿个字符串（平均 32 字节） | 10⁹ 个 | 约 32 GB | 无法枚举全部取值 |
| 100 GB 日志求 Top 10 | 未知 | 100 GB | 只需要维护 10 个候选 |
| 判断某元素是否出现过 | 未知 | 未知 | 允许假阳性时可用位图/布隆 |
第一行是位图的经典场景：取值范围有限（2³²），用 1 bit 表示一个值是否出现，总共 2³² bit = 512 MB，1 GB 内存放得下。第二行取值范围几乎无限，位图不可行，只能分桶或使用布隆过滤器。第三行根本不需要保存全部数据，用一个大小为 10 的容器即可。第四行要看是否允许误判。
规模决定了数据结构，而不是反过来。先算数，再选结构。
二、分而治之：哈希分桶
当数据无法整体放入内存时，最通用的办法是按某个规则把它切成若干份，使每一份都能独立处理。
哈希分桶的做法是：对每个元素计算hash(x) % N，根据结果写入第 N 个文件。同一个元素一定进入同一个桶，因此「统计每个元素出现次数」「去重」这类按元素聚合的操作可以在单个桶内完成。桶的数量选得让每个桶都能装进内存即可。
// 适用于 C++17
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <functional>
#include <string>
#include <vector>
// 把输入文件按哈希分成 bucketCount 个临时文件
void splitByHash(const std::string& inputPath,
const std::string& outputPrefix,
std::size_t bucketCount) {
std::vector<std::ofstream> outs;
outs.reserve(bucketCount);
for (std::size_t i = 0; i < bucketCount; ++i) {
outs.emplace_back(outputPrefix + std::to_string(i) + ".txt",
std::ios::binary);
}
std::ifstream in(inputPath, std::ios::binary);
std::string line;
const std::hash<std::string> hasher;
while (std::getline(in, line)) {
const std::size_t bucket = hasher(line) % bucketCount;
outs[bucket] << line << '\n';
}
}两个要点：桶的数量要留余量，通常让单桶大小控制在可用内存的一半左右；哈希函数要均匀，std::hash的具体实现由标准库决定，跨进程持久化时应自己指定算法。分桶之后，每个桶可以单独做「排序 + 去重」「哈希计数」「求 Top K」，结果再合并。
三、外部排序：多路归并
对 100 GB 数据排序、内存只有 2 GB 时，做法是两步：每次读入一块能放进内存的数据，用std::sort排好写回临时文件；再对所有有序临时文件做多路归并，每轮从各文件头部取最小值。
// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <fstream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
// 假设每个临时文件每行一个整数，且已内部有序
void kWayMerge(const std::vector<std::string>& files,
const std::string& outputPath) {
struct Item {
int value;
std::size_t fileIndex;
bool operator>(const Item& other) const { return value > other.value; }
};
std::vector<std::ifstream> ins;
ins.reserve(files.size());
for (const auto& f : files) {
ins.emplace_back(f, std::ios::binary);
}
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> heap;
for (std::size_t i = 0; i < ins.size(); ++i) {
int v = 0;
if (ins[i] >> v) {
heap.push(Item{v, i});
}
}
std::ofstream out(outputPath, std::ios::binary);
while (!heap.empty()) {
const Item top = heap.top();
heap.pop();
out << top.value << '\n';
int next = 0;
if (ins[top.fileIndex] >> next) {
heap.push(Item{next, top.fileIndex});
}
}
}std::priority_queue默认是大顶堆，第三个模板参数传std::greater<Item>后变成小顶堆。这样堆顶就是当前所有文件头里的最小值。每次弹出后，从同一个文件补一个元素进来。
复杂度：设总元素数为 n、路数为 k，归并阶段每次操作 O(log k)，总共 O(n log k)。k 不能太大——每个文件都要占用一个打开的文件描述符和一个输入缓冲区，k 受系统限制。k 很大时应当分级归并。
四、位图：取值有限时的 O(1) 判重
位图（bitmap）用一个二进制位表示一个整数是否出现过。对uint32取值范围，需要 2³² 位，即 512 MB。
// 适用于 C++17
#include <cstddef>
#include <cstdint>
#include <vector>
class Bitmap {
public:
explicit Bitmap(std::size_t bitCount)
: words_((bitCount + 63) / 64, 0) {}
void set(std::size_t index) {
words_[index / 64] |= (std::uint64_t{1} << (index % 64));
}
bool test(std::size_t index) const {
return (words_[index / 64] >> (index % 64)) & 1u;
}
private:
std::vector<std::uint64_t> words_;
};底层用std::uint64_t而不是std::vector<bool>：后者是按位压缩的特化版本，operator[]返回代理对象，行为和普通容器不同；自己按 64 位字操作，语义也更清晰。
位图的局限很明确：
- 只能表示「整数在某个范围内是否出现」，不能存出现次数，也不能存字符串；
- 范围越大内存越大，
uint64范围需要 2 EB，不可能； - 稀疏数据浪费空间：几百万个数散布在 2⁶⁴ 范围内时完全不可行。
需要记录出现次数时，可以把每个计数扩展到 2 位、4 位，代价是内存成倍增长。
五、布隆过滤器：允许误判的判重
布隆过滤器（Bloom filter）解决的问题是：在内存远小于数据量的前提下，判断一个元素「可能出现过」还是「一定没出现过」。
结构是一个长度为 m 的位数组和 k 个独立的哈希函数：
- 插入 x：对 x 计算 k 个哈希值，把对应位置 1；
- 查询 x：检查这 k 位是否都为 1。有任意一位为 0，则 x一定没有插入过；全为 1，则 x可能插入过。
它只有假阳性（false positive），没有假阴性（false negative）。这个性质非常适合「先挡一层」：请求先过布隆过滤器，判定「一定不存在」的直接拒绝，剩下的再查真正的存储。这样可以用很小的内存挡掉绝大部分无效查询。
// 适用于 C++17
#include <cstddef>
#include <cstdint>
#include <functional>
#include <string>
#include <vector>
class BloomFilter {
public:
BloomFilter(std::size_t bitCount, std::size_t hashCount)
: bits_((bitCount + 63) / 64, 0), hashCount_(hashCount) {}
void add(const std::string& key) {
for (std::size_t i = 0; i < hashCount_; ++i) {
setBit(position(key, i));
}
}
bool maybeContains(const std::string& key) const {
for (std::size_t i = 0; i < hashCount_; ++i) {
if (!testBit(position(key, i))) return false;
}
return true;
}
private:
// 用「哈希 + 序号」组合出多个位置，避免写 k 个独立哈希函数
std::size_t position(const std::string& key, std::size_t i) const {
const std::size_t h1 = std::hash<std::string>{}(key);
const std::size_t h2 = std::hash<std::string>{}(key + "#" + std::to_string(i));
return (h1 + i * h2) % (bits_.size() * 64);
}
void setBit(std::size_t pos) {
bits_[pos / 64] |= (std::uint64_t{1} << (pos % 64));
}
bool testBit(std::size_t pos) const {
return (bits_[pos / 64] >> (pos % 64)) & 1u;
}
std::vector<std::uint64_t> bits_;
std::size_t hashCount_;
};这段代码是教学用的简化实现：position里拼接字符串再哈希，只为构造第二个哈希值，开销不小；std::hash不保证跨进程一致，所以结果不能持久化后换程序读。标准库至今没有提供布隆过滤器（<bit>提供的是位操作工具），生产环境应使用成熟库或固定哈希算法自行实现，参数 m、k 按预期元素数量和可接受的误判率估算。
六、Top K：最小堆
求「最大的 K 个元素」时，不需要保存全部数据。维护一个大小为 K 的最小堆：
- 堆未满时直接插入；
- 堆满后，若新元素大于堆顶，弹出堆顶并插入新元素；否则丢弃。
扫描结束后，堆里就是最大的 K 个元素。时间 O(n log K)，空间 O(K)。
// 适用于 C++17
#include <functional>
#include <queue>
#include <vector>
std::vector<int> topK(const std::vector<int>& data, std::size_t k) {
if (k == 0) return {};
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int x : data) {
if (minHeap.size() < k) {
minHeap.push(x);
} else if (x > minHeap.top()) {
minHeap.pop();
minHeap.push(x);
}
}
std::vector<int> result;
result.reserve(minHeap.size());
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result; // 升序返回
}这里必须用最小堆而不是最大堆。最大堆的堆顶是当前 K 个里最大的，替换掉它等于丢掉最有价值的元素，方向正好相反。这是 Top K 最常见的错误。
如果 K 大于数据量，堆永远不满，函数返回全部元素，不需要额外处理。
当数据分散在多个文件或机器上时，先在每个分片内求 Top K，再把各分片的候选合并求一次 Top K。这个做法成立的前提是：全局前 K 名中的任一元素，在其所在分片内也一定排在前 K 名。
七、去重与计数
「海量数据去重」分两类，取决于是否允许近似。
精确去重：分桶后对每个桶用哈希集合去重，或者排序后去重。精确解的内存下界与不同元素个数成正比，没有更省的办法。
近似去重：只关心「大约有多少个不同元素」时，可用基数估计结构，用固定大小的内存给出概率意义上的近似值，误差可以估计但不能消除。具体算法和误差保证以原始论文或库文档为准。
频次统计：分桶后使用std::unordered_map精确计数；元素种类极多时可用 Count-Min Sketch 一类结构，代价是计数可能偏高。
选择精确还是近似，取决于业务能否接受误差，以及漏判和误判哪一侧后果更严重。
八、工程上的取舍
| 方法 | 时间 | 空间 | 结果 | 适用条件 |
|---|
| 哈希分桶 | O(n) | 单桶可放入内存 | 精确 | 按 key 聚合 |
| 外部排序 | O(n log n) | O(块大小) | 精确 | 需要有序输出 |
| 位图 | O(n) | 与取值范围成正比 | 精确 | 整数范围有限 |
| 布隆过滤器 | O(k) 每次查询 | 与元素数成正比，可远小于原始数据 | 有假阳性 | 允许误判的判重 |
| 最小堆 Top K | O(n log K) | O(K) | 精确 | 只关心前 K 名 |
| 哈希计数 | O(n) 平均 | 与不同元素数成正比 | 精确 | 单桶可放入内存 |
几条实践原则：
- 先估算，再选方案。把数据量、内存、取值范围写在纸上，很多方案会自然被排除。
- I/O 往往是瓶颈。外部排序中磁盘读写次数比比较次数更关键，顺序读写远快于随机读写。
- 不要把「近似」当成「精确」用。过滤器说「可能存在」时必须回查真实数据，说「一定不存在」时才可以直接下结论。
- 先做正确，再做快。分布式、并行、压缩都建立在对单机算法理解正确的前提上。
常见坑点
1. 用位图存字符串
❌ 试图用Bitmap对任意字符串做去重 ✅ 字符串用哈希分桶或布隆过滤器；位图只适用于整数范围
位图的下标必须是整数。字符串要先映射成整数，而映射本身就可能冲突，冲突后位图无法区分两个不同字符串。
2. 布隆过滤器判「存在」就直接返回
❌if (filter.maybeContains(x)) return cachedValue(x);✅maybeContains为真后，仍要到真实存储中确认
布隆过滤器有假阳性。把「可能」当成「一定」，会把不存在的元素误判为存在。
3. Top K 用最大堆
❌priority_queue<int>（默认大顶堆）维护 K 个元素 ✅priority_queue<int, vector<int>, greater<int>>
大顶堆的堆顶是当前 K 个中最大的，遇到更大的元素时替换掉堆顶等于丢掉了正确答案。求最大 K 个要用最小堆。
4. 分桶后对每个桶分别取 Top K 再直接拼接
❌ 把各桶的 K 个结果直接拼起来当作最终结果 ✅ 拼接后再做一次全局 Top K
每个桶的 K 个候选加起来是 N×K 个，其中只有全局前 K 名是答案。直接拼接会多出大量无关元素。
5. 桶数按「刚好装满内存」来定
❌ 可用内存 2 GB，就按每个桶 2 GB 切分 ✅ 让单桶大小控制在可用内存的一半左右
哈希分布不是完全均匀的，加上程序本身还要占用内存，按上限切分很容易在个别桶上失败。
6. 用 std::hash 的结果做持久化分桶
❌ 把std::hash<string>的结果写入文件，下次换平台继续用 ✅ 指定固定的哈希算法和种子
标准没有规定std::hash的具体算法，不同标准库、不同版本的结果可能不同。跨进程读取会导致同一个 key 落到不同桶。
7. 把「数据量大」等同于「必须分布式」
❌ 几百 MB 的数据也上分布式框架 ✅ 先看单机能否用分桶、位图、外部排序解决
多数所谓海量数据在单机上就能处理，分布式的复杂度和出错概率远高于单机方案。
总结
| 主题 | 核心结论 |
|---|
| 问题共性 | 数据超过内存，需要切分或压缩表示 |
| 分治 | 哈希分桶保证同一 key 进同一桶，各桶独立处理 |
| 外部排序 | 块内排序 + 多路归并，瓶颈在 I/O |
| 位图 | 1 bit 表示一个整数是否存在，空间与取值范围成正比 |
| 布隆过滤器 | 只有假阳性，适合做前置过滤 |
| Top K | 大小为 K 的最小堆，O(n log K) |
| 精确去重 | 内存下界与不同元素个数成正比 |
| 近似统计 | 内存固定，结果有误差，需按业务确认可接受性 |
海量数据处理的方法论其实只有一句话：在内存约束下，用「切分」换取空间，用「近似」换取空间，或者用「只保留必要信息」换取空间。分桶和外部排序属于切分，位图和布隆过滤器属于压缩表示，Top K 属于只保留必要信息。真正容易出错的地方不在算法本身，而在边界：假阳性被当成确定、堆的方向搞反、桶的大小卡在上限、哈希结果跨平台不一致。
