40亿QQ号去重仅用476MB内存 位图技术实现96.8%空间压缩

面对40亿QQ号在1GB内存限制下的去重要求，传统32位整数存储需约14.9GB内存，远超限制。位图（Bitmap）技术通过将每个QQ号映射为1比特标志位，仅需476MB即可完成去重：因QQ号为非负整数且小于2^32，可构建长度为2^32的二进制数组，每位对应一个可能号码，值为1表示存在。插入时置对应位为1，重复插入无效；最终遍历所有位为1的位置即得唯一集合，时间复杂度O(n)，空间复杂度O(N/8)字节。该方案空间压缩率达96.8%，但仅支持存在性判断，无法记录频次或附加信息。若需容忍误判以进一步节省空间，可采用布隆过滤器，但在精确去重场景中标准位图更优。实际应用中，腾讯可能结合分段位图、Roaring Bitmap等优化稀疏性问题，并在不同场景选用内存位图、分布式存储或外部排序策略。类似技术已广泛用于Redis签到统计、ClickHouse聚合及Kafka日志压缩等领域，反映大数据时代对空间-时间-精度三角权衡的持续探索。