布隆过滤器的面试应用

     如何从存放在A和B中的一亿条URL中找出A中有而B中没有的URL？

 

 

      布隆过滤器应该以一种比较好的解决方案，而且只用比较一次，查找效率很高。从存储空间上来讲，如果用哈希表，假定网址的平均长度为一百个字符，那么1一亿 个url大概需要20g存储空间。哈希表的存储效率一般只有 50%，所以实际存储空间大概需要40g。布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。也就是需要大概10g以下的空间，也是比较理想的。当然也有麻烦的地方就是有可能不是100%准确。

 

评论

4 楼 nkliuliu 2011-03-16  

grunt1223 写道

校长说的对，bloomfilter的精髓应该是“用位来表示是否存在，用多个hash函数来降低false positive”

所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte

所以是8:1

你说的没错。我是没有具体说明前提条件。

3 楼 grunt1223 2011-01-22  

校长说的对，bloomfilter的精髓应该是“用位来表示是否存在，用多个hash函数来降低false positive”

所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte

所以是8:1

2 楼 nkliuliu 2010-12-31  

sdh5724 写道

说明你还是没有理解， 应该不是1/8 1/4吧， 你可以用byte位来表示占用的。

http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html，你看看这个文章吧。应该我的理解没有问题，如果你看完了，还是觉的我的理解有问题，请详细赐教一下。

1 楼 sdh5724 2010-12-31  

说明你还是没有理解， 应该不是1/8 1/4吧， 你可以用byte位来表示占用的。