海量数据算法：Top K、Bitmap、Bloom 与外部排序

重新整理“海量数据算法：Top K、Bitmap、Bloom 与外部排序”时，我先翻了自己以前的错误记录，其中最典型的一条就是：海量数据题里最容易犯的错，是还没估算内存就开始写代码；我以前也总想着把所有数据一次性装进集合。沿着这个问题再看原理和代码，比直接背结论清楚得多。

海量数据题不是考你背多少算法，而是考你能不能在内存、磁盘、精确性和实时性之间做选择。只要数据大到单机内存装不下，问题就从“写代码”变成了“设计处理流程”。

海量数据题先问四个问题

图：海量数据题先判断是否能放进内存，再选择分治、堆、Bitmap、Bloom 或外部排序

四个关键问题：

1. 数据是否能全部放进内存？
2. 结果是否必须精确？
3. 是否需要排序？
4. 是离线批处理，还是实时流式处理？

Top K 高频

如果要从海量日志里找出现次数最高的前 100 个关键词，可以使用：

1. 分桶：按 hash 把数据拆成多个小文件。
2. 统计：每个小文件内部用 HashMap 统计频次。
3. 合并：每个桶取 Top K，再用小顶堆合并全局 Top K。

如果允许近似，可以使用 Count-Min Sketch 这类概率结构，空间更省。

海量整数去重

如果整数范围已知，可以使用 Bitmap。

10 亿个非负整数，如果值域可控：
一个 bit 表示一个数字是否出现过

Bitmap 适合精确判断存在性，但要求值域不要过于稀疏。如果值域巨大且允许误判，可以考虑 Bloom Filter。

外部排序

当数据无法一次放入内存，但需要全量排序时，可以使用外部排序：

1. 分块读取数据。
2. 每块在内存中排序。
3. 写成多个有序小文件。
4. 使用多路归并合并成最终有序文件。

多路归并通常使用小顶堆维护每个文件当前最小元素。

日志去重和 UV 统计

常见方案：

• 精确 UV：HashSet，但内存压力大。
• 大规模精确去重：分桶 + HashSet。
• 近似 UV：HyperLogLog。
• 黑名单判断：Bloom Filter。
• 有限整数范围去重：Bitmap。

我的分析

海量数据题真正考的是取舍。不要一听“10 亿数据”就直接说 MapReduce，也不要一听“去重”就只会 HashSet。先把约束问清楚：内存多大、数据范围多大、能不能近似、是否需要实时。

工程里经常不是一个结构解决全部问题，而是组合：分桶降低规模，哈希表统计，堆维护 Top K，布隆过滤器提前过滤。

面试题

1. 10 亿整数去重，什么时候用 Bitmap，什么时候用分桶？
2. Top K 高频词如何在内存不足时处理？
3. 外部排序的基本流程是什么？
4. Bloom Filter 和 Bitmap 有什么区别？
5. 海量数据题为什么要先问是否允许近似？