昨天的一个面试题：如何从存放在A和B中的一亿条URL中找出A中有而B中没有的URL

A和B中各存放着一亿条不重复的URL，URL存放时无序的，且URL是没有特征的，A和B可以试任意数据结构，也可以是存在数据库中。

如何找出A中有而B中没有的URL。

我当时给出的思路是：

依次遍历A和B，把从A和B里取出来的URL进行hashcode变换，把每条URL转换成key。相同的URL转换成相同的hashcode，然后用这个hashcode充当数组的下标或者map的key，数组的元素或map的value就是URL在A和B中的出现次数。

 

当时面试官说这是个可行的办法之一。所以我觉得应该还有更好的办法，因为要把url做 hashcode，而且要做到不冲突，那么需要的数字就要很大很大。。。就算是用byte数组或者boolean数组来存放在URL在A和B中的出现次数，所需内存也很可观。

 

大家一起讨论下。。。。

首先遍历A和B，把URL按照HOST或者字母开头分类。

再做比较这样的速度会快很多，同时可以减少内存的消耗。

楼上的做法差不多，不过要hash后分类，不然很难做到平均切割

我觉得按照Host分类也不会有什么帮助。比如把来自http://www.iteye.com的url分类，因为我要找的是A中有，而B中没有的，要比较的就是每个URL的所有字符，把URL分类的话，无非就是把URL的比较拆成了两部分，Host一部分和剩下的部分。

刚和一个朋友聊了下，觉得还有一个思路

把B的URL存成3层N叉树，然后依次遍历A中URL，将其到存放B的URL的3层N叉树种去查找，如果存在的话，最多三次就可以找到。

是的，因为URL的模式可循，所以这样做起来比较方便。

呵呵，可惜面试的时候只想到了hashcode那个思路，觉得这个3层N叉树应该要好过hashcode的那个。  还好面试通过了。。。。

3层N叉树？？什么结构
怎么放，有点不懂，有人帮忙解释下不？

其实就是把B的内容进行数据库的索引。使用B+树的索引。
然后遍历A中的内容，一条一条根据B的索引进行比较。

由于B+树是M叉树，2叉树需要的时间是log2 n， M叉树是logM n。
每次比较的次数根据书上说基本不会超过7次。
当然根据数据量的大小和数据之间的差异程度分布有关。
但是可以肯定的是查找次数远小于N。

因此A中的个数 X 每次在B的索引中查询的logM n。
结果是O(N logN)的时间就可以了。

用hashcode的方式当然速度更快，在保证足够大的内存放入hashcode的结果的前提下。

hashcode的比较是O(1)，永远比logN的速度快。
所以要得到hashcode的速度，要保证hashcode环境的正确性。

布隆过滤器。前一段时间看到别的帖子有人给出大数据量比对是否存在用这个。虽然有一定的误差，但是速度和内存都不错。