腾讯二面：20亿个QQ号码如何去重？

背景

之前找工作在腾讯面试遇到了一个很有意思的面试题，当时我记得现场还没有答出来，后来回家想了一下其实也没有那么难，而且还挺有意思的，今天做个整理分享给大家，希望对你有用

题目如下

文件中有20亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G. 这个题目的意思应该很清楚了，不过为了方便大家理解，我画了一个比较有年代感的动画，希望大家喜欢

方法一

排序去重

其实说到去重，最简单的方法就是先排序，排序之后重复的QQ号码必然在一起，保留第一个，把其余重复的去掉就行，

整个过程如下面动画

虽然这样可以解决问题，排序往往复杂度都很高，所以必定不是最优解

方法二

hashmap

如果排序的复杂对太高，那么直接用hashmap吧，hashmap的复杂度为O(1),思路其实很简单，就是直接把qq号记录到hashmap中，要是php的话直接记录在数组中就可以

hashMap[123] = true
hashMap[456] = true
hashMap[123] = true
hashMap[789] = true

由于hashmap的自动去重性质，所以自动变成了：

hashMap[123] = true
hashMap[456] = true
hashMap[789] = true

很显然，只有123，456，789存在，所以这也就是去重后的结果。

可是，面试官又要问你了：实际要存20亿QQ号码，1G的内存够分配这么多空间吗？显然不行，这样回答你还是无法通过腾讯面试。

方法三

bitmap

来看绝招！我们可以对hashmap进行优化，采用bitmap这种数据结构，可以顺利地同时解决时间问题和空间问题。 如果对bitmap不是很熟悉，可以看看我的这两篇文章

redis中bitmap(位操作)的实际应用

12306抢票算法居然被曝光了！！！居然这么简单

对bitmap有了大概的了解之后，我们直接把存在的qq号码对应的位置标记为1即可，下次查询只要对应的位为1，则为重复的qq号码，因为bitmap是一种非常省空间的数据结构，所以能够满足内存在1G之内的要求。

好了，今天的分享就到这里了，欢迎关注我的公众号，程序员小饭。我们下期见啦~