20 亿手机号判存：先算内存，再谈 Bitmap 还是 Bloom Filter

题面与核心结论

一道经典的海量数据判存题：有约 20 亿个手机号，内存只有 2 GB，要求判断某个手机号是否已经存在。

这道题最忌一上来就答“用哈希表全存”。看到“判存”先想到哈希表本身不算错，错在缺少成本估算；一旦被追问内存，方案不可行的问题马上暴露。

最终结论可以压缩成两句话：

• 如果要求绝对精确，且内存能给到约 1.1 GB，用位图（Bitmap）。
• 如果内存继续被压缩，但允许极小误判，用布隆过滤器（Bloom Filter）。

一、为什么“哈希表存字符串”是送命题

哈希表查询能到达 O (1)，这是它成为直觉答案的原因。问题是哈希表必须把所有 key 放在内存里，而 key 不是纸上算出来的 11 个字符。

在常用编程语言里，一个手机号字符串实际要算上底层对象结构、容器管理、对齐等开销；视频给出的量级是约 80 字节/个。

20 亿个手机号全部用字符串哈希表存储，总内存会到 150 GB 左右。相比之下，题目给的内存只有 2 GB，差距接近两个数量级。

这里还藏着一个常见误解：不要用“一个字符只占一字节”去估算字符串成本。编程语言里字符串的底层结构通常比裸字符数组更重。

二、退一步存 Long：仍然超内存

如果嫌字符串太重，把手机号全部转成长整型数字来存呢？

一个 Long 占 8 字节，20 亿个 Long 仍需要 15 GB 左右的内存。2 GB 的限制依然扛不住。

这一步的意义不是“哪种类型更优”，而是说明：

继续保存号码本身，无论字符串还是 Long，这条路都走不通。

只有放下“保存号码本身”的思路，才可能破局。

三、位图：用 1 bit 表示一个存在状态

位图的核心想法是降维：不再保存号码是什么，只保存号码“是否存在”。

可以把它想象成一排灯泡：

• 每个灯泡代表一个候选手机号；
• 灯泡灭 = 不存在；
• 灯泡亮 = 存在。

国内 11 位手机号基本都以 1 开头，所以候选号码的有效取值范围大约在 100 亿的量级。

这里要特别注意：100 亿不是“库里实际有 100 亿个手机号”，而是“可能被查询的号码空间大约有 100 亿个位置”。位图需要为这个空间里的每一个候选值准备 1 bit，才能做到精确判存。

约 100 亿个 bit 对应的内存大约是 1.1 GB。从 150 GB 级别的哈希表方案，到 1.1 GB 的位图方案，量的变化来自表示方式的转换。

四、写入与查询共用同一条偏移规则

位图的核心操作并不复杂。

1. 先确定基准值：视频中使用的是 100 亿。
2. 写入一个号码时，用“目标号码 − 基准值”算出偏移位置，再把该位置的 bit 置为 1。
3. 查询一个号码时，用同样的减法算出偏移位置，然后直接读取这个 bit。
4. bit 为 1 表示存在，bit 为 0 表示不存在。

整个过程是一次减法加一次位访问，所以位图不仅省内存，查询速度也极快。

五、内存再压缩：布隆过滤器

如果面试官继续加码：连 1.1 GB 也不给，但允许一个极小的误判率，这时位图的精确路线就走不通了。

可以改用布隆过滤器。

布隆过滤器同样不需要保存手机号本身，但它不再只用一个位表示一个号码，而是通过多个哈希函数把一个号码映射到多个位上面。

它的代价是概率性判断：个别不存在的号码可能因为多位碰撞，被误判成“存在”。换句话说，它牺牲了一点精确性，换取了比位图更省的内存结构。

六、易错点与边界

• 不要先答哈希表，而是先算内存。 哈希表在查询速度上没问题，问题在于 2 GB 装不下这么大的集合。
• 不要以为转成整型就能解决。 8 字节一条记录，20 亿条仍然远远超出内存限制。
• 不要把数据量和候选空间混为一谈。 位图位数由“可能出现的号码范围”决定，而不是由“已录入的数量”决定。
• 精确与误判要做取舍。 位图在一个候选号码对应一个唯一 bit 时是精确的；布隆过滤器则接受一定误判来降内存。

七、最终选型与面试启示

这道题真正考察的不是死记某种数据结构，而是遇到海量判存问题时的思考路径：

1. 先做量级估算；
2. 内存不够时，尝试改变表示方式，而不是继续优化单条记录；
3. 根据“是否允许误判”决定走精确方案还是概率方案。

一句话收束：海量数据判存，先看内存够不够；要求精确，想 Bitmap；允许误判，想 Bloom Filter。