图 1：本文封面，点明题目与位图思路。
先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料，与任何公司的当前招聘无关。海量数据题是数据处理方向的经典门类，这道「40 亿个整数判断存在性」又是其中出镜率最高的一道——它考的不是算法技巧，是「内存不够时如何表示一个巨大集合」的思维方式。
想象面试现场，面试官给出题面：有 40 亿个不重复的 32 位整数，给定任意一个整数，如何快速判断它在不在这批数据里？机器内存有限。
第一步，先算内存账，把直存的路堵死。
40 亿个 32 位整数，每个 4 字节，全部读进内存大约需要 15 GiB——普通的面试设定里，这条路直接被内存卡死。用哈希表存更贵：每个元素除了值本身，还有指针、负载因子的冗余，实际开销是值本身的好几倍，比直存死得更透。
关键转念在这里：题目要的不是「存下这批数据」，而是「回答在不在」。这是一个集合的表示问题——只要能标记每个可能的取值在不在，数据本身一个字节都不用存。
第二步，位图：一个取值一个比特。
32 位整数的取值空间是 2 的 32 次方，约 43 亿个。给每个可能的取值分配 1 个比特：值 n 出现过，就把第 n 位置 1，没出现过就是 0。总共 2 的 32 次方个比特，折合约 512 MiB——单机内存轻松容纳，比直存省约 32 倍。这不是纸上数字：Redis 官方文档讲位图时就用了同一个例子，用 512 MB 记住 40 亿个用户各一个比特的信息。
定位规则一句话：值 n 落在第「n 除以 8」个字节的第「n 模 8」位。比如 n=10，落在第 1 号字节的第 2 位，置 1 表示存在。写入和查询都是一次位移加一次位运算，O(1)，零误判。
第三步，写出可运行的代码。
下面这份实现真的分配一块 512 MiB 的位图，验证存在性判断与定位规则，用 Node.js 22.15.0 直接运行（node bitmap.js）即可：
'use strict';
class Bitmap {
constructor(maxN) {
this.bytes = new Uint8Array(Math.ceil((maxN + 1) / 8));
}
add(n) {
this.bytes[Math.floor(n / 8)] |= 1 << (n % 8); // 第 n/8 个字节的第 n%8 位
}
has(n) {
return (this.bytes[Math.floor(n / 8)] & (1 << (n % 8))) !== 0;
}
}
// 先算内存账：位图按取值空间给每个可能的整数分 1 个比特
const FULL = 2 ** 32; // 32 位整数的全部取值个数
const ARRAY_BYTES = FULL * 4; // 全量直存 32 位整数
const BITMAP_BYTES = FULL / 8; // 每个取值 1 比特
console.log(`按全部 2^32 个取值算：数组直存约 ${(ARRAY_BYTES / 2 ** 30).toFixed(0)} GiB`);
console.log(`位图：${BITMAP_BYTES} 字节 = ${(BITMAP_BYTES / 2 ** 20).toFixed(0)} MiB，压缩 ${(ARRAY_BYTES / BITMAP_BYTES).toFixed(0)} 倍`);
// 真实分配 512MiB 位图，40 亿个不重复整数全部放得下
const bm = new Bitmap(FULL - 1);
const samples = [2, 10, 1_000_000_000, 3_999_999_999];
for (const n of samples) bm.add(n);
console.log('存在性判断：');
for (const n of [2, 3, 10, 11, 3_999_999_999, 4_000_000_000]) {
console.log(` ${n} 在不在：${bm.has(n)}`);
}
// 随机查询 100 万次计时，验证 O(1) 手感
const t0 = performance.now();
for (let i = 0; i < 1_000_000; i++) bm.has(Math.floor(Math.random() * FULL));
console.log(`100 万次随机查询耗时：${(performance.now() - t0).toFixed(0)} ms`);
实测输出如下：
按全部 2^32 个取值算：数组直存约 16 GiB
位图：536870912 字节 = 512 MiB，压缩 32 倍
存在性判断：
2 在不在：true
3 在不在：false
10 在不在：true
11 在不在：false
3999999999 在不在：true
4000000000 在不在：false
100 万次随机查询耗时：75 ms
512 MiB 的位图真实分配到内存里，四个采样值写入后查询全部正确，超出取值空间的 40 亿被正确判为不在；一百万次随机查询几十毫秒跑完——O(1) 不是嘴上说说。
图 2：位图的内存账、定位规则与适用边界。
可能的追问。
「数据稀疏怎么办？」这是位图的命门——它按取值空间付账，不按实际数据量付账。40 亿个值稀疏分布在巨大范围里，或者干脆是字符串，位图就不划算了，该换布隆过滤器：用一点误判率换极小空间（那道题单独讲，这里只划边界）。「要统计每个数出现几次呢？」一个比特不够，可以每个值配多个比特做计数位图，或换哈希计数。「两个这样的集合求交集呢？」两块位图按位与，一次扫描完成，这也是 Redis 里 BITOP 的直接用途。
易错点清单。
一，上来就建哈希表，内存账算都不算。二，把位图的空间账按「数据量」算成 40 亿比特——位图按取值空间 2 的 32 次方付账，想清楚再开口。三，字节内位序、字节序号讲错——落笔写定位公式（n 除以 8、n 模 8）最稳妥。四，声称位图万能，讲不出稀疏数据与字符串场景的边界。
回到面试现场，建议的答题节奏：先算内存账堵死直存，再点破「要的是集合表示不是数据存储」这个转念，给出位图方案与 512 MiB 的账，最后主动交代适用边界。已采集 URL 判定、训练样本去重、特征 ID 存在性检查，都是位图的经典落地——AI 数据管道里它几乎天天上岗。
你在工作里用位图或布隆过滤器解决过什么实际问题？欢迎分享你的场景。