40 亿 QQ 号去重：1GB 内存下的精确方案

掘金热榜文章《40 亿个 QQ 号，限制 1G 内存，如何去重？》把这道题重新推到台前；这道题也常被整理为互联网大厂后端面试中的海量数据处理题。 真正容易答错的不是 contains 怎么写，而是把“记录总数”“候选值域”和“是否允许误差”混成一件事。

按几种常见的值域口径计算，结果如下：40 亿条 4 字节记录本身为十进制 16GB，按 1024 口径约为 14.9GiB；若候选值只有 40 亿个，位图数组约占 476.83MiB；若覆盖完整的无符号 32 位值域，则约占 512MiB。反过来，若按资料中的约 100 亿上限计算，位图需要约 1.25GB，单独就装不下。 因此，值域有界且足够稠密时，Bitmap 是直接的精确解；值域过大时，应使用分片 Bitmap 或外部排序；布隆过滤器只能承担允许假阳性的预筛或存在性判断，不能独立输出精确结果。

40 亿条记录和 40 亿个可能值是一回事吗？

记录数 (N) 和候选值数量 (U) 不能直接等同。

设输入记录数为 (N=40) 亿，候选值数量为 (U)。如果把每个 QQ 号保存成一个 4 字节 int，原始数组就需要：

[
N \times 4 = 16000000000\ \text{Byte}
]

也就是十进制 16GB，或约 14.9GiB。资料中常直接写成“约 14.9GB”，采用的是 1024 进制。

位图改变了存储维度：它不保存每条记录，而是为每个候选值保留一个状态位。因此，位图容量取决于值域 (U)，而不是记录数 (N)。同一个 QQ 号出现一次还是一百万次，在位图里都只对应同一个 bit。

这也意味着两个成本必须分开计算：

• RAM 主要由值域 (U)、状态位宽和运行时开销决定。
• 磁盘 I/O、输出规模和运行时间主要由记录数 (N) 决定。

如果 40 亿条记录实际上只有几千万种不同 QQ 号，小值域位图所需的空间很小；如果 40 亿条记录几乎全是不同值，而且值域扩展到 100 亿甚至 64 位，那么问题就不再是“记录太多”，而是“值域太大”。

位图究竟要按 40 亿位，还是按最大 QQ 号分配？

位图的基本空间公式是：

[
S=\left\lceil\frac{U}{8}\right\rceil\ \text{Byte}
]

这里的 (U) 是归一化后的候选值数量。如果 QQ 号范围是 ([min,max])，并且可以直接作为下标，那么：

[
U=max-min+1
]

实际下标使用 id - min。如果 ID 从 0 开始，上界为 (M)，则需要 (M+1) 个位置。

值域口径 (U)	位图位数	位数组字节数	十进制 / 二进制口径	1GB 内存下的结论
40 亿个候选值	400 亿 bit	500,000,000 B	500MB / 476.83MiB	位数组名义上可装入
完整无符号 32 位空间	2³² bit	536,870,912 B	536.87MB / 512MiB	位数组名义上可装入，但需核算运行时开销
约 100 亿上限	100 亿 bit	1,250,000,000 B	1.25GB / 1.164GiB	位数组本身就超过预算

资料中出现的“476.83MB”和“512MB”实际上采用的是 MiB 口径；不同资料混用 GB、MB 和 GiB，容易造成看起来只差一点、实际却已经越界的判断。

位图对稠密整数很有效，对稀疏整数则可能浪费空间。资料以只保存 1 和 999 为例：即使只有两个值，位图仍要维护从低位到第 999 位附近的约 999 个位置。 此时如果值域扩展到 64 位，即使实际数据不多，直接位图也没有现实意义。

直接位图如何做到不误删也不漏重？

Bitmap 使用 0/1 状态表达成员关系：初始全为 0，遇到一个 ID 时检查对应位置；如果还是 0，就将其置为 1，并保留这个唯一 ID；如果已经是 1，就说明它此前出现过。

bitmap = 全 0 的位数组

依次读取 id：
    if bitmap[id] == 0:
        bitmap[id] = 1
        emit(id)
    else:
        丢弃本次重复记录

这里不存在哈希碰撞，因为 id 本身就是下标。只要值域边界明确、下标计算正确，Bitmap 的成员判断是零假阳性的。

Java 的 BitSet 内部使用 long[] words 保存位，每个 long 容纳 64 位；通过 bitIndex >> 6 定位数组下标，再使用 get、set 访问状态。 但 BitSet 适合的是已经归一化、可以直接作为下标的整数，而不是任意字符串或对象。

如果还要区分“只出现过一次”和“出现过多次”，可以扩展为 2 bit 状态，例如 00 表示未出现、01 表示一次、10 表示多次。 这种结构仍然不是精确频次计数器：它无法区分出现 2 次、3 次还是 100 次。要得到任意精确频次，需要更宽的计数器，或者在归并阶段直接统计相同键的数量。

直接扫描 Bitmap 的置位还能枚举全部唯一 ID，但扫描成本取决于整个值域，最坏约为 (O(U/64)) 个机器字。值域很大且数据稀疏时，“枚举所有位”本身也可能不划算。

512MB 的位图为什么仍可能超过 1GB 预算？

因为“位数组大小”只是进程内存的一部分。

JVM 的 -Xmx1g 约束的是 Java 堆上限，不是整个进程的物理内存上限。实际运行还要容纳：

• JVM 堆中的位数组及其他对象；
• GC 所需的代际空间和对象对齐开销；
• 输入缓冲、输出缓冲；
• 线程栈、元空间、代码缓存；
• DirectByteBuffer、JNI 或其他 native memory；
• 文件映射和操作系统层面的内存压力。

因此，512MiB 的位数组在 -Xmx1g 下虽然“名义可装”，却不代表整个任务可以稳定运行。如果预算按十进制 1GB 计算，512MiB 位数组只剩约 463MB 的十进制空间；按 1GiB 计算，则剩约 512MiB。两种口径都不能再把全部余量都分配给位图。

资料中的 new BitSet(1L << 32) 只能作为完整 32 位容量的示意，不能直接作为可编译的 Java 代码。 BitSet 的构造参数是 int nbits，1L << 32 本身是 long；即使强转为 int，也会发生截断。完整无符号 32 位范围应拆成多个 BitSet 段，或者改用自管数组、文件映射等实现。

此外，“1GB 内存”要明确指 JVM 堆、容器内存上限，还是进程 RSS。三者不是同一个约束。

值域太大时，256 个分桶怎样把峰值压下来？

分桶的核心不是简单地把数据切成 256 份，而是同时解决两个问题：怎样让每个桶只处理一部分值，以及怎样把桶内值重新映射到足够小的位图。

假设 ID 已归一化为非负整数，值域上界为 (U)，取 (K=256)。可以用：

bucket = id & 0xFF
local  = id >>> 8

因为：

[
id=local\times256+bucket
]

这个映射是可逆的，不存在哈希碰撞。桶内下标 local 的范围约为 (0) 到 (\lceil U/256\rceil-1)，所以单个桶的理论位图空间是：

[
S_{bucket}\approx\frac{U}{256}\ \text{bit}
]

而不是“桶内记录数乘以一个字节”。记录数和值域必须分开计算。

值域 (U)	单桶位图理论容量	二进制大小
40 亿	15,625,000 bit	约 1.86MiB
2³²	16,777,216 bit	2MiB
约 100 亿	39,062,500 bit	约 4.66MiB

分桶方案通常分两遍处理。

第一遍读取原始输入，根据 id & 0xFF 把原始 ID 写入 256 个临时文件。此时不必创建完整大位图。

for id in input:
    bucket = id & 0xFF
    write(bucket_file[bucket], id)

40 亿条记录平均分到 256 个文件时，每个文件约 1562.5 万条，但这是平均值，不是最大值。真实数据可能集中到少数桶，容量规划不能把平均值当成硬上限。

第二遍每次只加载一个桶，用一个约 (U/256) bit 的小位图去重：

for bucket in 0..255:
    bitmap = 清空当前桶的小位图

    for id in bucket_file[bucket]:
        local = id >>> 8
        if bitmap[local] == 0:
            bitmap[local] = 1
            记录该唯一 ID

这样，峰值内存由“大位图”变成了“一个小位图加输入输出缓冲”。代价是一次完整的临时写和一次完整的临时读，临时空间至少接近一份原始 ID 数据；文件数量、文件句柄、页缓存和磁盘吞吐也都要纳入预算。

并行处理时，内存预算取决于同时活跃的桶数：如果 256 个桶同时各加载一个位图，总位空间又接近完整的 (U) bit。分桶降低的是单进程峰值；所有桶的总内存开销仍然存在。内存预算应按“同时活跃的桶数 × 单桶位图大小”计算，并为每个 worker 单独计算堆、缓冲和 native memory。

输入不能重读或没有临时磁盘时还能精确去重吗？

能否精确去重，取决于输入能否重读、能否落盘以及输入是否有序。

如果输入只能扫描一次，但允许使用临时磁盘，分桶落盘仍然可行。第一遍虽然不能重读原始输入，却已经把必要状态保存到了 256 个桶文件中，之后可以逐桶精确处理。

如果输入已经有序，则不需要位图或临时文件。相邻两个值相同就保留一个，内存可以保持常数级。问题在于，题面通常没有给出“输入有序”这一条件。

如果既不能重读、不能落盘，输入又无序，而且值域任意，就无法对 40 亿个不同值保证精确去重。要在后面输出所有唯一 ID，系统必须保存“哪些值已经出现”的状态；这个状态既不能装入 1GB，又不能写到外部介质，就只能依赖值域足够小、足够稠密，或者依赖会引入假阳性的压缩结构。

允许重读但禁止临时磁盘时，还可以采用值域分窗：每次只给一个 Bitmap 窗口分配内存，然后反复扫描输入，处理落在该窗口内的 ID。这个方案精确，但扫描次数会随窗口数量增长。它适合范围已知、窗口数量可控的场景，不适合把 40 亿条无序数据反复扫描很多遍。

对字符串、对象或超过 64 位范围的值，也不能简单选择一个哈希值作为 Bitmap 下标，否则哈希碰撞会把两个不同键合并。要保持精确性，就必须保留原值并在冲突时校验，或者回到外部排序。

分桶后仍然很稀疏时，外部排序怎样保证精确？

外部排序不依赖值域大小，核心是把“无法一次装入内存的排序”改造成“内存排序块加磁盘归并”。

第一阶段，在固定内存预算内读取一批记录，在内存中排序，然后写成一个有序段。内存块需要为排序辅助数组、对象开销和序列化缓冲预留空间。

第二阶段，对所有有序段做多路归并。归并时只比较当前各段的最小值；相同键连续出现时，只保留一个，或者统计其精确出现次数。

内存块排序 → 写出有序段 run-1、run-2、run-3……
          → 多路归并
          → 合并相邻相同键
          → 输出唯一键或键频次

它的优势是键类型更自由：整数、long、字符串和普通对象都可以按可比较规则处理；也不会因为值域稀疏而浪费大量空 bit。 代价是磁盘 I/O：所有记录至少要经历排序块的写出和归并读取，还要管理有序段数量、归并缓冲和失败恢复。

如果要求保留“首次出现顺序”，需要在每条记录中附带原始序号。归并同一键时取最小序号，得到它第一次出现的位置；如果最终仍要按首次出现顺序输出，还需要对去重后的“键—首次序号”再做一次外部排序。

精确频次也可以在归并相邻相同键时直接得到。这里必须区分“至少出现两次”和“精确出现 37 次”：2 bit 饱和状态只能表达前者，不能替代完整计数。

布隆过滤器为什么不能单独完成精确去重？

布隆过滤器通过多个哈希函数把一个键映射到位数组中的多个位置。插入时把这些位置全部置为 1；判断时，只有这些位置全部为 1，才认为键“可能存在”。

因此，标准布隆过滤器的判断结果是：

• 任一位置为 0：一定不存在；
• 所有位置为 1：可能存在，也可能是假阳性。

在元素没有被错误删除、哈希函数满足基本均匀性假设的前提下，标准布隆过滤器不会产生假阴性，但会产生假阳性。 这也是它不能独立承担精确去重的原因。

假设输入流中有两个不同 ID，而它们的部分哈希位置发生重叠，第二个 ID 可能被误判为已经出现。如果程序据此直接丢弃第二个 ID，那么唯一列表就缺少了一个真实成员。

此外，标准布隆过滤器不能枚举全部唯一值。它只保存一组 bit，不保存原始键，也不知道某个 bit 对应哪个 ID。即使误判率很低，也不能据此保证结果精确。

它适合两类任务：

• 允许少量误判的快速存在性查询，例如缓存预筛、爬虫 URL 判重等；
• 作为精确存储之前的预筛器，最终仍由 Bitmap、哈希表或排序结果决定是否重复。

“布隆过滤器＋精确存储”可以保持整体精确，但精确存储仍要容纳真正需要的唯一键。布隆过滤器不会自动解决唯一列表的容量问题。

1GB 内存下，布隆过滤器的空间和误判率如何取舍？

布隆过滤器的理论空间近似为：

[
m\approx-\frac{n\ln p}{(\ln 2)^2}
]

其中 (n) 是预计插入的不同元素数量，(p) 是目标误判率。较优的哈希函数个数约为：

[
k\approx\frac{m}{n}\ln 2
]

这里的 (n) 应该是预计的唯一元素数，而不是未经统计的原始记录数。若有 40 亿条输入，但实际只有 10 亿个不同 ID，按 10 亿个唯一元素估算更合理；直接按 40 亿估算会浪费空间。

把 (n=40) 亿代入，并假设整个 1GB 都用于过滤器位数组，可以得到以下理论边界：

位空间预算	总位数 (m)	每元素位数 (m/n)	理想连续最优误判率下界
1GB 十进制	80 亿 bit	2 bit	约 38.25%
1GiB	8,589,934,592 bit	2.1475 bit	约 35.65%

这些数字已经是把所有内存都交给位数组，并假设哈希理想均匀、计算开销为零的结果。真实系统还要扣除精确存储、索引结构、哈希状态、输入输出缓冲和运行时开销，实际误判率只会更高。

如果希望误判率达到更低的水平，空间需求会迅速上升：

目标误判率 (p)	40 亿唯一元素所需位数	位数组大小	理论最优 (k)
1%	约 383.4 亿 bit	约 4.79GB / 4.47GiB	约 6.64
0.1%	约 575.1 亿 bit	约 7.19GB / 6.70GiB	约 9.97

资料中的“容量 50 亿、误判率 0.1%”只是一个配置示例，不能据此证明它能在 1GB 内运行。 对 40 亿至 50 亿个唯一元素，0.1% 的目标本身就需要远大于 1GB 的理论位空间。

因此，在 1GB 总预算下，布隆过滤器通常只适合“允许较高误判率”的预筛。如果目标是精确唯一列表，不能把节省下来的几亿 bit 当作最终答案空间。

需要计数或删除时，概率过滤器还能怎么选？

普通布隆过滤器适合只插入、不删除的成员判断。它不能精确计数，也不能安全删除，因为一个 bit 可能由多个元素共同置位，贸然清零会影响其他元素。

Counting Bloom Filter 将每个 bit 换成计数器，插入时递增，删除时递减，因此可以支持近似频次和删除。但计数位宽、溢出和并发更新都会影响准确度，计数溢出后也可能产生额外误判。

Cuckoo filter 为每个元素保存指纹和候选位置，通过搬迁机制解决位置冲突，通常支持近似计数和删除。它的成员判断仍是概率性的，也不能直接枚举精确唯一列表。

这些结构可以配合分桶使用：先按桶保存过滤器，再逐桶加载和处理，从而降低峰值内存。但如果任务要求输出精确唯一值或精确频次，最终仍要在每个桶内使用精确位图、排序或计数结构。概率过滤器只能降低部分查询成本，不能替代最终的真值存储。

只想判重、要唯一列表、要频次时，方案有什么不同？

方案	成员判断	RAM 需求	磁盘 I/O	能否枚举唯一结果	适用键类型
直接 Bitmap	精确，零假阳性	约 (U/8) 字节	无临时文件	可以，扫描置位	有界整数
分片 Bitmap	精确，零假阳性	单桶约 (U/K) bit，加缓冲	一轮落盘、一轮回读	可以，逐桶输出	有界整数
外部排序	精确	排序块加归并缓冲	写有序段并归并	可以	任意可比较键
布隆过滤器	可能存在，有假阳性	约 (m) bit，加实现开销	成员查询通常不需要	不可以精确枚举	可哈希的键
布隆过滤器＋精确存储	精确存储决定最终结果	两者成本相加	取决于精确存储	取决于精确存储	取决于精确结构

如果只是判断某个 ID 是否出现过，允许误判可以选择布隆过滤器；要求零假阳性且值域有界，Bitmap 更直接。

如果需要输出全部唯一 ID，有界整数适合直接 Bitmap 或分片 Bitmap；值域未知、数据稀疏或键为字符串时，外部排序更稳妥。

如果需要精确频次，应使用外部排序归并计数，或者为值域内每个键维护足够宽的计数器。2 bit 饱和状态只能回答“是否超过一次”。

如果需要保留首次出现顺序，分桶时必须携带原始序号，外部排序时也必须保存序号；单纯扫描 Bitmap 得到的是下标顺序，不是首次出现顺序。

对于持续更新和删除场景，固定值域 Bitmap 的成员更新成本很低，但删除语义需要结合重复次数处理；普通布隆过滤器不适合删除，Counting Bloom 和 Cuckoo Filter 提供的是近似能力。

Java 代码、分桶文件和输出流会踩哪些具体问题？

Java 代码首先要处理 int 的符号性。Java 的 int 能保存 32 位 bit pattern，但有符号解释范围只有 (-2^{31}) 到 (2^{31}-1)。如果输入中的原始值是无符号 32 位整数，应先转换：

long id = Integer.toUnsignedLong(rawInt);

完整无符号 32 位可以用分段 Bitmap 承载：

private static final int SEGMENT_BITS = 1 << 30;
private static final int SEGMENT_COUNT = 4;

private static final BitSet[] BITS = new BitSet[SEGMENT_COUNT];

static {
    for (int i = 0; i < SEGMENT_COUNT; i++) {
        BITS[i] = new BitSet(SEGMENT_BITS);
    }
}

static int segmentOf(long unsignedId) {
    return (int) (unsignedId >>> 30);
}

static int bitOf(long unsignedId) {
    return (int) (unsignedId & ((1L << 30) - 1));
}

这四段的位数组总量是 512MiB，仍然没有包含 JVM 和任务的其他开销。超过无符号 32 位的 long ID 不能直接套用这四段实现，需要缩小分桶数量、改用范围分区，或者采用外部排序。

使用哈希函数决定桶号时，还要处理哈希碰撞。桶文件里必须保留原始 ID，最终比较的也必须是原值。若直接把哈希值当成 Bitmap 下标，哈哈希碰撞会把不同 ID 错判为同一个键，精确性随之失效。对于 long、字符串和对象尤其如此。

40 亿条记录的序列化成本也不能忽略。按 4 字节 ID 计算，仅原始载荷就是约 16GB 十进制空间；改用 8 字节 long 则约为 32GB。 临时文件若采用文本格式、逐行 JSON 或带额外对象头，体积和解析成本还会继续放大。固定宽度二进制格式通常更适合这种规模，但传输协议、校验和、序号等字段也要计入磁盘预算。

文件和任务状态需要单独设计。256 个桶不意味着必须同时打开 256 个文件句柄。文件句柄上限、同时打开数量和写入吞吐都应纳入设计，通常使用有限数量的文件句柄分批写入。任务重启时，可以为每个桶记录完成标记，并把唯一结果先写入独立分段文件；全部完成后再拼接或发布，避免重试时重复输出。

并行预算和布隆过滤器监控也要纳入设计。每个 worker 都要单独满足内存限制，不能只看单桶位图大小。布隆过滤器则应监控位数组占用率和实际误判率，实际误判率可以用留出的真实样本测量，而不是只看配置中的目标值；哈希种子或哈希函数变化后，也需要重新评估。

去重后的几十亿个 ID 怎样写出去？

唯一结果不能先构造成一个 List<Long> 或 List<Integer>，否则刚解决完输入去重，又会在输出阶段耗尽内存。

对于 bucket = id & 0xFF、local = id >>> 8 的分桶方案，可以在每个桶处理完后扫描小位图，并利用下面的关系还原原始 ID：

[
id=local\times256+bucket
]

for bucket in 0..255:
    加载并扫描当前桶的小位图
    对每个置位位置 local：
        id = local * 256 + bucket
        将 id 写入输出流

输出应采用流式写入，二进制格式通常比十进制文本更节省空间，也减少格式化开销。这个桶号与局部下标的组合会产生按桶分组的顺序，不一定是全局数值有序；如果业务要求全局递增，可以改用连续值域分桶，或者在去重后增加一次外部排序。

任务的结束条件是所有桶处理完成，且最后一个唯一 ID 已经写出。