日期：2026-07-11
标签：#面试 #八股 #后端 #系统设计 #场景题
一句话答案
若 QQ 号可映射到有限整数范围，使用位图：每个号码只占 1 bit；但 1GB 只有约 86 亿 bit，必须先确认号码上界和输入规模含义。
面试口语版
这题要先问清 QQ 号取值范围、是否只判断重复还是要输出去重结果，以及 1GB 是纯数据预算还是总进程内存。如果号码可转为不超过约 40 亿的非负整数，位图只需 40 亿 bit，约 500MB，完全可放下。读取一个号码 x，就检查 bitmap[x]，为 0 则置 1 并输出或计数，为 1 则说明重复。若号码范围远大于 86 亿，即使只有 40 亿条输入，也不能按最大值直接开位图，可按高位分桶到磁盘，再逐桶用位图或排序去重。
原理拆解
- 40 亿 bit ÷ 8 ≈ 5 亿 byte，约 477 MiB。
- 位图精确去重，时间复杂度 O(n)，但空间取决于值域而非数据条数。
- Bloom Filter 空间更省，但存在假阳性，不能用于要求完全精确的去重结果。
- 外部分桶：按哈希或号码高位写入多个文件，保证单桶可放内存，桶内再排序/Hash/位图去重。
关键细节
- Java
int最大约 21.47 亿，若号码可到 40 亿，解析和索引计算要使用long，位图分段下标再转int。 - 1GB 若包含 JVM 开销，不能直接申请接近 1GB 的单数组；应使用分段位图、堆外内存或内存映射文件。
- 如果题目其实是“40 亿个号码中找重复”，输入条数与号码值域是两个不同概念。
面试官追问
- Bloom Filter 为什么不能精确去重？
- 位图如何支持删除？
- 值域是 64 位整数怎么办？
- 如何并行处理并保证分桶不漏不重？
面试官追问参考答案
1. Bloom Filter 为什么不能精确去重？
多个元素会把同一组 bit 置 1，因此查询“可能存在”包含假阳性：一个从未出现的号码也可能被判断出现过。它保证“判断不存在时一定不存在”，适合前置过滤，但直接去重会误删真实新数据。
2. 位图如何支持删除？
普通 bit 清零会误删与同一位置相关的状态，在一值一位的直接位图中如果元素不重复则可直接清零；若要支持重复计数，应使用计数位图/Counting Bloom Filter，为每个位置保存计数，删除时递减，但空间明显增加并需防计数溢出。
3. 值域是 64 位整数怎么办？
不能按整个 64 位值域开位图。可按高位或哈希分桶落盘，使每桶数据量可控，再逐桶排序或使用 HashSet 精确去重；也可用外部排序后线性去重。要求近似判断时才考虑 Bloom Filter。
4. 如何并行处理并保证分桶不漏不重？
使用确定性分区函数，例如 hash(value) mod N，同一个值必定进入同一桶，每条输入只写一个桶。每个桶可独立并行去重；写入使用可校验的分片文件和任务清单，失败按输入分区重试，最终核对记录数、校验和及桶范围。
Maintained by · YihuiEdit on GitHub