python网站开发入门超级外链工具

前几天发现一个有趣的文章 “40亿个QQ号，限制1G内存，如何去重？”，发现很有意思，就想着用代码实现一下，下面是分析和实现过程

一、审题分析

• 一个 QQ 号现在最长有 11 位，因为 int 是四字节，数值范围是2的31次方，因此得使用 long 存储，但考虑到实现，使用 int 存储（10位QQ）；
• 40亿 QQ 文件存储至少在 4000000000 * 4(字节) / 1024 / 1024 / 1024 ~= 14.9G, 所以不可能将文件全部加载到内存中；
• 在进行去重时需要将之前的记录存储在内存中，上面分析到如果将QQ全部存储是不可能的，通过将 40亿QQ 分到不同文件中，但实际也是绕不过存储到内存中，分成多个文件只能加快读取（多线程读取），怎么办呢？
• 仔细探究了一番，之前我们做项目的时候，为了去除百万级的数据重复问题，我们用了布隆过滤器；这次这个问题的话，需要从它下手。想了想它的原理“存在，可能存在；不存在，一定不存在”。得从“位”下手。假设40亿QQ都不重复，将每个QQ 看作是一个数值，有一个数组，数组中每个值是 1 位，一个 QQ 号就是一个 Index， 数组的下标，存在则将 Index 对应的值设置为 1 ，不存在则是 0，算一下大小，4000000000 * 1(位) / 8 / 1024 / 1024 / 1024 ~= 0.48G ，算完这个队列可以呀，不到 1g&#x