原译：使用Bloom Filters

trt2008

Thanks!

zhlong8

算法简单，不过应用非常有意思

墨迹哥

仙子，请教下关于容量的问题。
本来打算开一个帖子来请教你。
但是论坛搜索到了，就直接问了，说的不到位的话请包涵。。

我很好奇的一个问题是Bloom Filters的容量问题。
基本上Bloom Filters的功能我理解了，但是其中容量是一个必须限制的数字。
那么如果我的数字是一个不可预知的情况下，那怎么办呢？

正好比我在微薄上提问云舒的。

1. 
   
2. 墨迹哥
   
3. 其实我想问个问题，Bloom::Filter 这玩意设置了容量以后，一旦超出就异常了。那怎么办呢？是否能设置成一个N，永远不会有超出异常呢？@云舒 因为我没有办法知道目标网站链接有多少。

复制代码

对此我想请教下你，对于会容量超出的情况，仙子的解决方法是什么呢？

兰花仙子

墨迹哥 发表于 2013-08-05 12:14
仙子，请教下关于容量的问题。
本来打算开一个帖子来请教你。
但是论坛搜索到了，就直接问了，说的不到位 ...

晕啊 我好久没用这种算法了，要重新看下。BF相对于LRU而言，更高效，但是碰撞的概率也大些。

rubyish

兰花得太精彩了，先收藏，有时间学习学习。

墨迹哥

回复 14# 兰花仙子


    {:3_186:}   难道有比这个更好的算法？。。主要超出容量会出错。。- - #

laputa73

不能设一个很大的capacity? 1M,10M,100M? 一个网页的链接数总是有限的。
或者，可以监控key_count ，接近capacity就动态再创建一个新filter. 每次多检查一个filter。。。
或者，按26个字母，建26个filter  (感觉没必要，不如一开始直接加大26倍)
总是有办法的。

墨迹哥

回复 17# laputa73


    突然发现你这个回复，非常接近我的需求。

    但是怎么实现还是个问题。

qq27898

好强大！