布隆过滤器的口试应用
布隆过滤器的面试应用
http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html，你看看这个文章吧。应该我的理解没有问题，如果你看完了，还是觉的我的理解有问题，请详细赐教一下。
你说的没错。我是没有具体说明前提条件。
如何从存放在A和B中的一亿条URL中找出A中有而B中没有的URL？
布隆过滤器应该以一种比较好的解决方案，而且只用比较一次，查找效率很高。从存储空间上来讲，如果用哈希表，假定网址的平均长度为一百个字符，那么1一亿 个url大概需要20g存储空间。哈希表的存储效率一般只有 50%，所以实际存储空间大概需要40g。布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。也就是需要大概10g以下的空间，也是比较理想的。当然也有麻烦的地方就是有可能不是100%准确。
1 楼
sdh5724
2010-12-31
说明你还是没有理解， 应该不是1/8 1/4吧， 你可以用byte位来表示占用的。
2 楼
nkliuliu
2010-12-31
sdh5724 写道
说明你还是没有理解， 应该不是1/8 1/4吧， 你可以用byte位来表示占用的。
http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html，你看看这个文章吧。应该我的理解没有问题，如果你看完了，还是觉的我的理解有问题，请详细赐教一下。
3 楼
grunt1223
2011-01-22
校长说的对，bloomfilter的精髓应该是“用位来表示是否存在，用多个hash函数来降低false positive”
所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte
所以是8:1
所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte
所以是8:1
4 楼
nkliuliu
2011-03-16
grunt1223 写道
校长说的对，bloomfilter的精髓应该是“用位来表示是否存在，用多个hash函数来降低false positive”
所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte
所以是8:1
所谓八分之一只是某个特例：
hash map：存放8byte的信息签名
bloomfilter：采用8个哈希函数，刚好1byte
所以是8:1
你说的没错。我是没有具体说明前提条件。