前言大家好这里是程序员阿亮今天来跟大家讲解我学习到的一个技术设计“假如现在有 40 亿个 10 位数的 QQ 号服务器限制只能用 1G 内存要求把它们全部去重你怎么做”遇到这个问题很多人心里一喜这不就是送分八股文吗当场脱口而出“用BitMap位图啊一个 bit 代表一个数40 亿个 bit 算下来也就 476MB1G 内存完全绰绰有余”但是“你再仔细算算1G 真的够吗”这道题到底诈在哪里为什么很多人背了八股反而死得更惨一、 暴力解法直接原地升天老规矩咱们先看最容易想到的方案。如果让你不限内存随便搞大家肯定反手就是一个 HashSet 或者直接塞数组里排序。但咱们算一笔账40 亿个 QQ 号哪怕按 4 字节的 unsigned int 来存光数据本身就要40亿×4 字节≈14.9 GB如果你用的是 Java 的HashSetLong那就更热闹了对象头、引用指针再加上哈希槽开销没有个60~100 GB内存根本下不来。面对区区 1G 的内存限制暴力方案直接就被宣判死刑了。二、 救星登场BitMap 的降维打击既然存对象太奢侈那就得把空间压榨到极致。计算机里最小的单位是什么bit比特位。BitMap 的思路极其精妙我不存数字本身我存数字的“位置”。洛琪希最棒了想记录我的 QQ 号 907607222简单直接找到第 907607222 个 bit把它从 0 抹成 1。后面又来了一个重复的 907607222再抹一次它依然是 1天然防重所有数据读完从头到尾扫一遍哪个位置是 1哪个位置对应的下标就是去重后的 QQ 号。这时候很多人掏出计算器开始算40亿个数字×1 bit÷8÷1024÷1024≈476 MB“476M 比 1G 小多了搞定收工”慢着真正的天坑就在这三、 灵魂暴击BitMap 的大小根本不看“个数”请大家把这句话默念三遍BitMap 占多大内存取决于数据的“最大取值范围”而不是“数据的个数”哪怕你全局只有一个 QQ 号如果这个号是 999999999910位的最大值你的位图也必须开到第 9999999999 位我们回头看看题目条件10 位数字的 QQ 号。10 位数字的最大值是 10 个 9也就是近10^10100 亿的可能空间为了能把最大的 QQ 号装进去位图需要多大100亿 bit÷8÷1024÷1024≈1192 MB≈1.16 GB1.16 GB1.0 GB超标了服务当场 OOM 给你看那么如何解决呢有方案的四、 绝杀破局把 1192M 给我“剁成两半”既然整张位图要 1192M放不下怎么办程序员最擅长的事情是什么分治既然一次吃不下那我们就分两次吃。这就是极其优雅的Two-Pass两遍扫描法第一趟只处理前半段我们在内存里只申请50 亿个 bit的位图算下来只需要50亿÷8÷1024÷1024≈596 MB把 40 亿数据从磁盘流式读进来遇到大于等于 5000000000 的直接无视跳过遇到小于 5000000000 的把对应 bit 位置为 1。读完后把所有为 1 的位置刷盘输出然后清空并释放这 596MB 内存。第二趟处理后半段重新开一个 596MB 的位图。再次把数据读一遍遇到小于 5000000000 的跳过遇到大号减去 5000000000 的偏移量后打点记录。扫完输出两批结果拼在一起就是完整的去重结果结果怎样内存峰值永远被死死卡在596 MB完美的在 1G 限制内搞定。虽然把数据读了两遍但顺序磁盘 I/O 速度极快在工程上完全可接受。总结下篇再见我还在研究其他的技术场景 你问我40亿个QQ号限制1G内存如何去重？别一上来就背八股，里面有诈！
前言大家好这里是程序员阿亮今天来跟大家讲解我学习到的一个技术设计“假如现在有 40 亿个 10 位数的 QQ 号服务器限制只能用 1G 内存要求把它们全部去重你怎么做”遇到这个问题很多人心里一喜这不就是送分八股文吗当场脱口而出“用BitMap位图啊一个 bit 代表一个数40 亿个 bit 算下来也就 476MB1G 内存完全绰绰有余”但是“你再仔细算算1G 真的够吗”这道题到底诈在哪里为什么很多人背了八股反而死得更惨一、 暴力解法直接原地升天老规矩咱们先看最容易想到的方案。如果让你不限内存随便搞大家肯定反手就是一个 HashSet 或者直接塞数组里排序。但咱们算一笔账40 亿个 QQ 号哪怕按 4 字节的 unsigned int 来存光数据本身就要40亿×4 字节≈14.9 GB如果你用的是 Java 的HashSetLong那就更热闹了对象头、引用指针再加上哈希槽开销没有个60~100 GB内存根本下不来。面对区区 1G 的内存限制暴力方案直接就被宣判死刑了。二、 救星登场BitMap 的降维打击既然存对象太奢侈那就得把空间压榨到极致。计算机里最小的单位是什么bit比特位。BitMap 的思路极其精妙我不存数字本身我存数字的“位置”。洛琪希最棒了想记录我的 QQ 号 907607222简单直接找到第 907607222 个 bit把它从 0 抹成 1。后面又来了一个重复的 907607222再抹一次它依然是 1天然防重所有数据读完从头到尾扫一遍哪个位置是 1哪个位置对应的下标就是去重后的 QQ 号。这时候很多人掏出计算器开始算40亿个数字×1 bit÷8÷1024÷1024≈476 MB“476M 比 1G 小多了搞定收工”慢着真正的天坑就在这三、 灵魂暴击BitMap 的大小根本不看“个数”请大家把这句话默念三遍BitMap 占多大内存取决于数据的“最大取值范围”而不是“数据的个数”哪怕你全局只有一个 QQ 号如果这个号是 999999999910位的最大值你的位图也必须开到第 9999999999 位我们回头看看题目条件10 位数字的 QQ 号。10 位数字的最大值是 10 个 9也就是近10^10100 亿的可能空间为了能把最大的 QQ 号装进去位图需要多大100亿 bit÷8÷1024÷1024≈1192 MB≈1.16 GB1.16 GB1.0 GB超标了服务当场 OOM 给你看那么如何解决呢有方案的四、 绝杀破局把 1192M 给我“剁成两半”既然整张位图要 1192M放不下怎么办程序员最擅长的事情是什么分治既然一次吃不下那我们就分两次吃。这就是极其优雅的Two-Pass两遍扫描法第一趟只处理前半段我们在内存里只申请50 亿个 bit的位图算下来只需要50亿÷8÷1024÷1024≈596 MB把 40 亿数据从磁盘流式读进来遇到大于等于 5000000000 的直接无视跳过遇到小于 5000000000 的把对应 bit 位置为 1。读完后把所有为 1 的位置刷盘输出然后清空并释放这 596MB 内存。第二趟处理后半段重新开一个 596MB 的位图。再次把数据读一遍遇到小于 5000000000 的跳过遇到大号减去 5000000000 的偏移量后打点记录。扫完输出两批结果拼在一起就是完整的去重结果结果怎样内存峰值永远被死死卡在596 MB完美的在 1G 限制内搞定。虽然把数据读了两遍但顺序磁盘 I/O 速度极快在工程上完全可接受。总结下篇再见我还在研究其他的技术场景 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
