腾讯二面:1G内存如何对40亿QQ号去重?#腾讯二面

今天给大家分享一道腾讯二面的面试题：1G内存如何对40亿QQ号去重？这里重点有三个。

·第一个重点是40亿个QQ号，这是一个非常大的数量。

·第二个重点也是目标，就是要去重。

所以说到去重，可以用HashSet就可以去重。因为假设是10个QQ号或者是100个QQ号，用HashSet其实很容易就可以去重。因为QQ号本质上面也就是一个数字，把它扔到HashSet里面去，自动最终就去重了。

但是这里有一个限制，就是用的内存不能超过1GB。但是40亿个QQ号，就算用int类型来存QQ号，其实最终40亿个int类型所占用的内存也远远超过了1GB，等会可以来算一下。

所以对于这三个限制条件，就需要采用一些其他的方式来解决这个问题。其实有一些其他的方法，这个视频就来给大家分享这种分治法。因为这种分治法基本上是没有什么缺点的，可能会稍微慢一点了。但是其他的方法虽然也可以，虽然性能上面可能会比分治法更好，但是额外的其实都会有一些其他的限制条件。

所以来看，首先要分析一下，就是QQ号最终要把它存到HashSet里面去重，但是到底是用int类型还是用long类型来表示QQ号？其实在Java里面int类型的最大值是这个数字，它其实是10位。而我的QQ号是9位的，但是我是在20年前申请的。

所以现在刚刚看了一下我的QQ，我的学员的一些微信，一些QQ其实是有10位的QQ号的。所以保险起见，不能用int类型来表示这个号，只能用long类型来表示QQ号。因为万一超过了这个数字，所以一个long类型就会占用8个字节，而40亿个QQ号最终就会占用32GB的内存。所以假设是用int类型也得占16GB，所以不管怎么样都是远远超过了1GB的内存的。

分治法是怎么解决这个问题的？其实整体的思路很简单，就是要把这40亿个QQ号去分成很多的片，分片。所以到底分成多少片也要先来估算一下。

比如每个QQ号假设是long类型，刚才说了一个long类型占8个字节，但是当把这个数字存到hashset里面去的时候可能又需要占用一些其他的对象。所以不妨就假设每一个QQ号到时候再存到HashSet里面去的时候其实要占用20个字节，就往多了算。

如果每个QQ号占用20个字节，1GB的内存大概就只能存5千万个QQ号。1GB的内存能存5千万个QQ号，现在有40亿个QQ号，说白了就要有80个分片，就是每一个分片的内存不能超过1GB，所以这样一算就需要有80个分片。

再往多了算一点就取100个分片，这样子用100个来作为分片数，每一个分片里面最多都可以用1GB，但是肯定最终100个分片，每个分片里面QQ号的数量就还是比较少的，肯定不会超过1GB了。按照估算的思路来，所以这里就取100来作为分片。

具体确定好了分片数之后就要来对40亿个QQ号来真正的进行分片。那么怎么分呢？

·首先需要把这40亿个QQ号先存到一个文件里面，比如说一个TXT里面，然后再利用这样的代码来进行分片。这里的分片其实就是利用这种FileReader的对象，到时候来读取TXT文件。

比如说下面这里有一个while循环，就会去读取40亿个QQ号所在的TXT文件里面的每一行，我们就规定每一行就是一个QQ号，所以一行里面就不能有多个QQ号，所以每一行作为一个QQ号。

取到了QQ号之后，这个地方就因为它是一个数字，就直接去取模，然后就会得到一个分片的ID，然后就把对应的就是当前这个QQ号对应的分片的文件，把它把这个QQ号写进去。所以最终这个代码回头就会产生100个这种分片的TXT文件，每个TXT文件里面其实就是一堆QQ号，对不对？

这样子就对40亿个QQ号首先进行了分片，在这个过程中间，虽然它可能是串行的，可能会运行的稍微久一点，但是它占用的内存是不会超过1GB的。

然后再往下面走，分片文件生成好了之后，接下来就要去重，所以有100个分片，就分别要对这100个分片去进行去重。怎么去重？这里核心也是利用HashSet来进行去重，所以这个地方就不能用并发，因为虽然100个分片原理上面是可以用并发的方式，用开多个线程的方式去进行去重，但是同时开多个线程去重，最终占用的内存可能就超过了1GB。

所以这里严谨一点也只能用单线程，就针对这100个分片文件，依次的来进行去重，这样子才能保证内存占用不超过1GB。

怎么实现？刚刚不是有100个分片文件吗？这个方法表示的是针对某一个分片文件如何去除？这就是分片的ID，然后就取出对应的分片文件，然后就读取分片文件里面的每一行，因为它仍然还是每一行就是一个QQ号，然后再利用HashSet来进行去除，最终去重的结果就保存到另外一个分片对应的TXT文件里面去，所以最终就能得到100个分片去重之后的TXT文件。

得到了去重之后的结果之后就可以把这些都合并起来，就得到一个最终的结果。因为相同的QQ号肯定是在同一个分片的，所以在合并分片文件的时候其实就不需要额外的再去去重了，直接合并其实就可以了。

这就是我对这个问题的解决思路，希望对大家有所收获。大家还有其他的想法可以在评论区留言。当然这里有一个面试题的笔记，我整理的面试题有很多很多，如果想要也可以在评论区留言，也可以看评论区的置顶，谢谢大家。希望能得到大家的点赞，谢谢。