海量数据处理

这一篇是你的差异化武器. 海量数据题考的是 “内存放不下时怎么办” 的系统思维: 而你做设备指纹 SDK, 天天和内存约束, 大规模数据, 性能极限打交道. 一般应用开发者答不深, 你能结合底层经验讲透, 这是面试加分点.

核心套路就四招:分治 (哈希拆分), 位图, 布隆过滤器, 堆 / 外部排序.

进度自测

• 哈希分治 (大文件拆小文件)
• 位图 BitMap (去重/排序/查存在)
• 布隆过滤器 (原理/误判/删除问题)
• Top-K (小顶堆 / 分治 / 快速选择)
• 外部排序 (多路归并)
• 经典场景: 40 亿整数判存在 / 10 亿 URL 去重 / Top100 热词

学习目标与章节边界

本章只处理 “单机内存放不下” 的精确或近似计算, 强调容量, 磁盘 I/O 与分桶倾斜. 内存内题解见 LeetCode Hot 100 算法清单, Android 端的采样, 限流和图片解码见 Android 业务算法场景. 完成后应能先列假设, 再给出容量计算, 分阶段算法与失败处理.

一, 核心思想: 内存放不下怎么办

面试给的经典约束:数据量远超内存 (如 40 亿整数, 100GB 日志, 但内存只有 1GB).解题主线:

1. 能不能压缩表示? → 位图 (1 个整数用 1 bit).
2. 能不能拆分? → 哈希分治 (相同 key 必落同一小文件, 分而治之).
3. 只要近似 / 允许误判? → 布隆过滤器 (极省空间).
4. 只要前 K / 排序? → 堆 / 外部多路归并.

C++17 示例前置条件

本章以下标记为 C++ 的代码块均为可组合的教学片段, 不是单独的完整程序. 将某一类复制到独立 C++17 文件时, 先加入以下公共头文件和 using 声明; TwoBitCounter 与 BloomFilter 各自是符号闭合的独立类, kthLargest 是独立函数. 还需由调用方提供 main, 测试数据和错误处理策略.

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>

using std::invalid_argument;
using std::hash;
using std::length_error;
using std::numeric_limits;
using std::out_of_range;
using std::size_t;
using std::string;
using std::swap;
using std::uint8_t;
using std::vector;

二, 位图 BitMap

思想: 用一个 bit 表示一个数是否存在.40 亿个 int 若用 int 数组要 16GB, 用位图只需 40 亿 / 8 ≈ 500MB, 省 32 倍.

判断整数 x 是否存在:
  字节下标 = x / 8,位下标 = x % 8
  set:  bitmap[x/8] |= (1 << (x%8))
  get:  bitmap[x/8] &  (1 << (x%8))

• 应用: 40 亿无符号整数判某数是否存在 / 去重 / 排序 (置位后顺序扫描).
• 进阶 Bitmap (2-bit 图): 每个数用 2 bit, 表示 “出现 0 次 / 1 次 / 多次”, 可解 “找出现一次的数 / 找重复的数”.
• 局限: 只适合整数且范围有限; 数据稀疏时浪费 (此时用哈希或 Roaring Bitmap 压缩位图).
• 联系你的背景: 这正是底层 / SDK 常用的空间压缩手段, 可主动提及 “做指纹去重时用过类似位压缩思路”.

2-bit 位图 C++17 类片段 (值域 [0,maxValue]): 状态 00=未出现, 01=一次, 10=至少两次, 不需要区分第三次以后. 与上方 “C++17 示例前置条件” 代码块组合后, 类定义符号闭合.

class TwoBitCounter {
    size_t maxValue_;
    vector<uint8_t> data;
    static size_t bytesFor(size_t maxValue) {
        if (maxValue == numeric_limits<size_t>::max()) throw length_error("maxValue is too large");
        size_t valueCount = maxValue + 1; // 已排除 maxValue + 1 溢出.
        size_t bytes = valueCount / 4 + (valueCount % 4 != 0);
        if (bytes > vector<uint8_t>().max_size()) throw length_error("bitmap is not allocatable");
        return bytes;
    }
    void checkRange(size_t x) const {
        if (x > maxValue_) throw out_of_range("value outside bitmap range");
    }
public:
    explicit TwoBitCounter(size_t maxValue) : maxValue_(maxValue), data(bytesFor(maxValue), 0) {}
    void add(size_t x) {
        checkRange(x);
        size_t byte = x / 4, shift = (x % 4) * 2;
        uint8_t state = (data[byte] >> shift) & 0b11;
        uint8_t next = state == 0 ? 1 : 2;
        data[byte] = static_cast<uint8_t>((data[byte] & ~(0b11u << shift)) | (next << shift));
    }
    bool appearsOnce(size_t x) const {
        checkRange(x);
        return ((data[x / 4] >> ((x % 4) * 2)) & 0b11) == 1;
    }
};

例如值域 40 亿需 2 * 4e9 bit = 1e9 byte, 约 0.93 GiB, 外加对象 / 页对齐开销; 这已接近 1 GiB 内存, 不能忽略运行时余量. 边界: maxValue 必须覆盖输入最大值, 负数需映射或另建结构; 两位计数饱和后不能恢复精确次数.

三, 布隆过滤器 (Bloom Filter)

思想: 位图 + 多个哈希函数. 判断元素 “ 一定不存在 “或” 可能存在 “.极省空间, 代价是有误判率 (false positive).

1. 核心机制与近似公式

插入 x:用 k 个哈希函数算出 k 个位置,全部置 1.
查询 x:k 个位置全为 1 → 可能存在;任一为 0 → 一定不存在.

• 误判率 p 的近似公式: p ≈ (1 - e^(-kn/m))^k
  • m: 位数组的长度 (bit 数)
  • n: 预计插入的元素个数
  • k: 哈希函数的个数
• 最优 k 值的直觉推导: k ≈ (m/n)·ln2 ≈ 0.7·(m/n)
  • 为什么 k 不能太小? 如果哈希函数太少, 位图中会有大量闲置的 0 没被利用, 区分度低, 导致误判率变高.
  • 为什么 k 不能太大? 如果哈希函数过多, 每次插入都会将大量的 bit 置为 1, 位图很快就被填满, 导致后续查询大概率全命中 1, 误判率急剧上升.

2. 空间估算示例 (Android 面试语境)

假设在风控 SDK 中, 我们需要在本地拦截 10 万个恶意设备黑名单 (n = 100,000), 且要求误判率低于 1%(p = 0.01). 根据估算公式 m ≈ -n·ln(p) / (ln2)^2:

• 所需位数组大小 m 约为 96 万 bit.
• 折算成内存: 960,000 / 8 / 1024 ≈ 117 KB.
• 面试话术: “比起把 10 万个 32 字节的 String 设备指纹存入内存 (约 3MB), 使用布隆过滤器可以将黑名单压缩到 100KB 左右, 这对 Android 端内存很友好.” 查询是 O(k), 但这不等于必然适合主线程; 还要在目标设备上测量哈希, 内存访问和调用频率.

3. 删除与计数权衡 (Counting Bloom Filter)

• 不支持删除: 标准布隆过滤器如果将某个位置 0, 可能会影响其他同样映射到该位的元素.

• 解法 (Counting Bloom Filter): 将原本的 1 个 bit 扩展为一个计数器 (例如 4-bit 数组).插入时计数器 +1, 删除时计数器 -1.

• 空间权衡: 虽然支持了删除, 但空间开销直接膨胀 (如 4-bit 计数器使占用翻 4 倍), 且计数器有溢出风险. 需在 “是否必须删除” 与 “内存占用上限” 间做取舍.

• 应用: 缓存穿透防护 (Redis 前挡一层), 爬虫 URL 去重, 垃圾邮件过滤, 判断 key 是否可能在数据库.

• 联系你的背景: 风控 / 反作弊里黑名单判断, 设备去重就常用布隆过滤器, 这是你能讲实战的点. 可落地链路: 10 万黑名单 → 布隆 117 KB → 误判标定 → 回源精确表; 端侧判定场景详见 Android 业务算法场景・设备指纹相似度与本地风控.

Bloom Filter C++17 类片段 (双重哈希模拟 k 个散列, 非对抗安全哈希):与上方 “C++17 示例前置条件” 代码块组合后, 类定义符号闭合; 要成为可执行程序仍须由调用方提供 main.

class BloomFilter {
    vector<bool> bits; size_t k;
    size_t index(const string& s, size_t i) const {
        size_t h1 = hash<string>{}(s), h2 = hash<string>{}("#" + s) | 1;
        return (h1 + i * h2) % bits.size();
    }
public:
    BloomFilter(size_t bitCount, size_t hashes) : bits(bitCount), k(hashes) { if (!bitCount || !hashes) throw invalid_argument("positive m/k required"); }
    void add(const string& key) { for (size_t i = 0; i < k; ++i) bits[index(key, i)] = true; }
    bool mightContain(const string& key) const { for (size_t i = 0; i < k; ++i) if (!bits[index(key, i)]) return false; return true; }
};

这里的 mightContain=true 只能作为后端精确表查询前的候选, 不能据此拒绝合法用户. std::hash<string> 的结果只适用于同一进程的内存态过滤器, 不应当作持久化, 跨进程或分布式协议; 这些场景必须固定散列算法, 种子和格式版本. 边界: m=0/k=0 显式拒绝; 预计 n 增长超过设计值时误判率升高, 应按目标 n,p 重建过滤器.

四, 哈希分治 (分而治之)

思想: 大文件按 hash(key) % N 拆成 N 个小文件, 相同 key 必进同一小文件. 每个小文件能进内存后单独处理, 再汇总.

模板流程:

1. 遍历大文件, 按哈希把记录分到 N 个小文件.
2. 对每个小文件单独用哈希表 / 堆处理 (统计频次, 去重, Top-K).
3. 合并各小文件的结果 (如各自 Top-K 再归并出全局 Top-K).

• 应用: 10 亿 URL 去重, 统计每个词的频次, 求两个大文件的交集.
• 要点: 分治的前提是 “相同 key 落同一桶”, 所以必须用 key 的哈希分, 不能随便切.

容量数字示例: 100 GiB URL 日志, 估计可用内存 512 MiB, 单桶处理期望只用 256 MiB. 先按放大系数 1.5 预留哈希表, 字符串和负载因子开销, 桶数至少为 ceil(100 * 1.5 / 0.25)=600; 实际选 1024 个桶以方便掩码分桶并留倾斜余量. 掩码分桶只有桶数为 2 的幂时才等价于取模, 且要求哈希低位质量足够; 否则应用 % bucketCount 或先混合散列. 分桶阶段读取约 100 GiB, 写约 100 GiB, 共约 200 GiB, 桶内读取和临时结果另计. 若某桶超过 256 MiB, 不是 “哈希分治失败”, 而是继续对该桶用另一种盐二次分桶, 并记录热点 key / 恶意输入证据.

五, Top-K 问题

三种解法按场景选:

• 小顶堆 (数据流 / 超大数据):维护大小为 K 的小顶堆, 堆顶是第 K 大, O (n log K) 时间, O (K) 空间.海量数据首选 (不用全载入).
• 快速选择 (数据能进内存):基于快排分区, 平均 O (n) 找第 K 大, 但会修改 / 需载入数据.
• 哈希分治 + 堆 (数据放不下):先哈希分治统计频次, 各桶取局部 Top-K, 再归并.

→ Top-100 热搜词: 哈希分治统计词频 + 每桶小顶堆 + 归并.

快速选择 C++17 函数片段 (数据可完全装入内存): 与上方 “C++17 示例前置条件” 代码块组合后, 函数定义符号闭合; 要成为可执行程序仍须由调用方提供 main. 分区后只迭代包含目标下标的一侧, 期望线性, 但最坏仍 O(n^2), 会改写数组.

int kthLargest(vector<int>& a, int k) {
    if (a.empty() || k < 1 || k > static_cast<int>(a.size())) throw invalid_argument("k out of range");
    int target = static_cast<int>(a.size()) - k, lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int pivot = a[hi], i = lo;
        for (int j = lo; j < hi; ++j) if (a[j] <= pivot) swap(a[i++], a[j]);
        swap(a[i], a[hi]);
        if (i == target) return a[i];
        if (i < target) lo = i + 1; else hi = i - 1;
    }
    throw invalid_argument("k out of range");
}

边界: k 必须在 [1,n]; 重复值不影响第 k 大的数值定义; 流式数据不能使用此法, 因为它需要保留全部元素.

六, 外部排序

思想: 数据放不下内存时的排序.分块 + 多路归并:

1. 把大文件切成能进内存的小块, 各块在内存排序后写回磁盘 (生成 “顺串”).
2. 用多路归并 (K 路败者树 / 小顶堆) 把有序小块合并成全局有序.

• 应用: 100GB 日志按时间排序, 超大文件去重后排序.
• 联系: 归并排序的磁盘版, 体现你对 I/O 与内存权衡的理解.

I/O 推演示例: 100 GiB 输入, 每次可排序 256 MiB, 先产生约 400 个顺串. 若内存可给每个输入缓冲 1 MiB, 输出缓冲 1 MiB, 则一次 128 路归并约需 129 MiB 缓冲, 可在两轮完成 (400→4→1).每一轮都读取 100 GiB, 写入 100 GiB, 共 200 GiB; 初始生成加两个归并轮共约 600 GiB 顺序 I/O. 临时磁盘至少要容纳输入外加一轮输出. 打开 fd 数, 磁盘带宽, 压缩比和记录大小会改变这个估算.

七, 经典场景速答

八, 先写容量与误差假设

海量数据题先声明 key 空间, 数据量, 可用内存, 磁盘, 机器数, 是否允许误判 / 漏判, 输出是否精确以及时限. 位图的 500 MB 只是 40 亿 bit 的理论量级, 还需考虑索引范围, 元数据和实现开销. Bloom Filter 要给 n/m/k 与目标误判率, 哈希函数相关性和对抗性输入会影响结果. 哈希分治必须处理倾斜和碰撞, 外排要估算读写轮次, 临时空间, 块大小和归并路数. 未给这些假设时, “用位图/布隆/分治” 只是候选名, 不是完整方案.

面试怎么讲 (结合你的优势)

回答海量数据题时, 先问清约束 (数据量, 内存, 是否允许误判, 要精确还是近似), 再选招式, 最后说权衡. 这套 “先问约束再设计” 的思路本身就是工程素养.

你可以主动关联:

“我做设备指纹 SDK 时, 设备去重和黑名单判断都涉及大规模数据 + 内存约束. 用过位压缩做去重, 布隆过滤器做快速存在性判断, 对空间/时间/误判率的权衡有实战体会.”

这一句话就把算法题变成了你的项目亮点, 是普通应用开发者给不出的答案.

主题练习与预期证据

1. 以 10 亿个, 值域 40 亿的非负整数为假设, 分别算 1-bit 与 2-bit 位图的理论字节数; 预期约 477 MiB 与 0.93 GiB, 注明 MB/GiB 口径.
2. 为 Bloom Filter 设计 add("a") 后查询 "a" 的用例, 预期为可能存在; 再说明为什么测试不能证明无误判.
3. 用上述 100 GiB 外排假设画出顺串轮次, 预期证据是给出路数, 轮数和临时空间, 而不是只写 “多路归并”.