问题：对一个包含15亿个QQ号的文件进行去重

算法1：数组解法

将QQ号读入内存，组成一个数组。然后遍历这个数组与其他位置比对，如果遇到重复的号码，则表示存在重复。

该算法时间复杂度n^2, 15亿个号码循环次数为(15亿)^2。

所有QQ号码存入内存中，每个QQ号码占用一个整形，一般为32个bit, 空间需要15亿*32个bit约等于5.59G

算法2: HashMap解法

内存中保存一个HashMap, 遍历所有号码，如果HashMap中存在该号码，则表示存在重复。如果不存在该号码，将号码存入HashMap中。

由于HashMap的存和取在不存在Hash冲突的情况下为O(1)复杂度，所以该算法时间复杂度为O(n)。虽然算法2在时间复杂度上大大优于算法1，但是由于HashMap数据结构占用空间较大，如果15亿个号码都不重复，需存入HashMap中，仅考虑HashMap内数组存储的15亿个Entry的Key需占用空间同样为57220G，再加上存储的15亿个value，空间占用都肯定大于5.59G。

算法3：BitMap解法

我们先把问题简化，15亿个号码简化为10个10以内的号码去重，假设号码分别是

1, 2, 3, 4, 1, 3, 9, 8, 7, 6

我们使用BitMap来标记每个数字是否存在，

BitMap初始化使用一个10位的Bit数组，各位都初始化为0，    则

BitMap为  0000000000

数字1, 取BitMap第1位的值，为0, 表示1不存在重复的值，将BitMap第1位标记为1，则BitMap为 0000000001

数字2, 取BitMap第2位的值，为0，表示2不存在重复的值，将BitMap第2位标记为1，则BitMap为 0000000011

数字3，取BitMap第3位的值，为0，表示3不存在重复的值，将BitMap第3位标记为1，则BitMap为 0000000111

数字4，取BitMap第4位的值，为0，表示4不存在重复的值，将BitMap第4位标记为1，则BitMap为 0000001111

数字1，取BitMap第1位的值，为1，表示1存在重复的值，不标记BitMap，则

BitMap为 0000001111

数字3，取BitMap第3位的值，为1，表示2存在重复的值，  不标记BitMap，则

BitMap为 0000001111

数字9，取BitMap第9位的值，为0，表示9不存在重复的值， 将BitMap第9位标记为1，则BitMap为 0100001111

数字8，取BitMap第8位的值，为0，表示8不存在重复的值， 将BitMap第8位标记为1，则BitMap为 0110001111

数字7，取BitMap第8位的值，为0，表示7不存在重复的值， 将BitMap第7位标记为1，则BitMap为 0111001111

数字6，取BitMap第8位的值，为0，表示6不存在重复的值， 将BitMap第6位标记为1，则BitMap为 0111101111

最终BitMap为0111101111

遍历BitMap的各位，如果该位为1，则表明存在数值为该位位数的数值，这样可以得到去重后的所有数值

为 9,8,7,6,4,3,2,1

该方法推广到15亿个号码去重，则使用的BitMap为15亿位，算法时间复杂度同样为O(n), 占用空间约等于15亿个bit约等于174.62M

可以看出，BitMap在大数据量，重复度不高的数值去重场景的空间占用方面有比较大的优势。

如果数值的重复度比较高,例如存在99.99%的重复，BitMap依然要占用15亿*100%个bit的空间，

而HashMap仅存储不重复的数值，则HashMap解法占用空间将变为原空间的0.01%

这种情况下BitMap与HashMap的空间占用优劣势就需要重新进行衡量。