昨天的一个面试题：如何从存放在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中的出现次数，所需内存也很可观。

 

大家一起讨论下。。。。

评论

1 楼 shansun123 2011-05-11  

如果在查找时可用内存有限且准确度不要求太高的话，我觉得可以尝试用Bloom Filter。