海量数据去重

一个文件中有40亿条数据，每条数据是一个32位的数字串，设计算法对其去重，相同的数字串仅保留一个，内存限制1G.

方法一：排序

对所有数字串进行排序，重复的数据传必然相邻，保留第一个，去除后面重复的数字串即可。

缺点是排序时间复杂度太高，并且显然是需要内排序+外排序一起的。优化的方法有扫雪机模型。

方法二：哈希表 + 文件分割

当然还有一种方法，取32位的前n位做一个哈希，然后把哈希值一样的数据串放到一个文件里面。然后每次将一个文件load到内存中，然后对这个文件中的数据做个排序 or 哈希去重即可。

这样的缺点是磁盘IO较多。

方法三：位图

用512MB的unsigned int数组来记录文件中数字串的存在与否，形成一个bitmap。

然后从0到2^32-1开始遍历，如果flag为1，表明该数存在。这样就自动实现了去重。

这个思路很好了。