40亿个号码如何去重？——大数据处理中的bitmap应用
40亿个号码如何去重？——大数据处理中的bitmap应用
在处理海量数据时，如何在有限的内存条件下完成数据去重是一个常见的技术挑战。本文以40亿个QQ号码的去重问题为例，探讨了多种解决方案，从最简单的排序方法到更高效的hashmap、文件切割，最终介绍了bitmap这种空间和时间效率都非常高的解决方案。
40亿个号码如何去重？
假设我们有一个包含40亿个QQ号码的文件，需要设计一个算法对这些号码进行去重，相同的QQ号码仅保留一个，且内存限制为1GB。
方法一：排序
最直观的方法是对所有QQ号码进行排序，重复的号码必然相邻，保留第一个，去掉后面的重复项。但是这种方法的时间复杂度较高，对于40亿个号码来说效率很低。
方法二：hashmap
考虑到直接排序的时间复杂度太高，可以使用hashmap。具体思路是将QQ号码作为键存储到hashmap中：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[123] = true
mapFlag[890] = true
由于hashmap的去重性质，实际存储结果会自动变成：
mapFlag[123] = true
mapFlag[567] = true
mapFlag[890] = true
但是，实际要存储40亿个QQ号码，1GB的内存是不够分配这么多空间的。
方法三：文件切割
这是处理海量数据的常见方法，通过将数据切割成多个文件来避免内存溢出。但是，这种方法涉及大量的文件操作，效率不高。
方法四：bitmap
bitmap是一种非常高效的数据结构，可以同时解决时间和空间问题。在很多实际项目中都有应用。
bitmap原理
bitmap的基本思想是用一个位数组来表示某个范围内数字的存在性。例如，一个unsigned char类型的数据可以表示0~7这8个整数的存在与否：
上图表示的unsigned char值为255，表示0~7这些数字都存在。
上图表示的unsigned char值为254，表示1~7这些数字存在，而数字0不存在。
应用到QQ号码去重
由于QQ号码的理论最大值为2^32 - 1（约43亿），我们可以使用512MB的unsigned int数组来记录这些号码的存在性：
bitmapFlag[123] = 1
bitmapFlag[567] = 1
bitmapFlag[123] = 1
bitmapFlag[890] = 1
实际上会变成：
bitmapFlag[123] = 1
bitmapFlag[567] = 1
bitmapFlag[890] = 1
然后从小到大遍历所有正整数（4字节），当bitmapFlag值为1时，就表明该数是存在的。
扩展练习
1. 排序40亿个互不相同的QQ号码
直接使用bitmap标记这40亿个QQ号码的存在性，然后从小到大遍历正整数，当bitmapFlag的值为1时，就输出该值，输出后的正整数序列就是排序后的结果。
2. 求40亿个互不相同的QQ号码的中位数
直接使用bitmap排序，然后根据排序结果直接计算中位数。
3. 求40亿个互不相同的QQ号码的top-K
直接使用bitmap排序，然后根据排序结果直接获取top-K。
4. 判断80亿个QQ号码是否存在相同号码
根据抽屉原理，由于QQ号码的个数是43亿左右（理论值2^32 - 1），所以80亿个QQ号码必然存在相同的QQ号码。