海量数据处理

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

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

进度自测

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

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

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

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

二、位图 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 常用的空间压缩手段,可主动提及“做指纹去重时用过类似位压缩思路“。

三、布隆过滤器(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 是否可能在数据库。

• 联系你的背景:风控/反作弊里黑名单判断、设备去重就常用布隆过滤器,这是你能讲实战的点。

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

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

模板流程:

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

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

五、Top-K 问题

三种解法按场景选:

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

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

六、外部排序

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

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

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

七、经典场景速答

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

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

你可以主动关联:

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

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