【随笔记】Redis（三）布隆过滤器BloomFilter面试知识点

青旅半醒 2023-01-19 03:24 11阅读 0赞

> 由简入繁，水滴石穿。

## BloomFilter ##

> 它是一个很长的二进制向量和一系列随机映射函数，主要用于检索一个元素是否在一个集合内。优点很明显，就是空间效率和查询时间都比其他的算法快，缺点同样明显，就是有误识别率和删除困难。

例如：当一个元素X\{a,b,c,d,e\}加入集合，每个元素通过K各Hash函数将这个元素映射成一个阵列（Bit array）中的K个点，并把他们置为1.检索的时候我们只需要看这些K点是不是都等于1就可以知道集合中有没有这个元素了。如果这些K点的任何一个是0，那么这个被检索的元素一定不在，如果都是1，则元素可能在。

![avatar][]

从上面的例子可以看出，BloomFilter能判断出f可能存在，但是无法判断出f一定存在，这就是误识别率；

但是很多时候我们在实际使用中，不需要知道这个元素一定存在，更多的是需要判断出这个元素一定不在，例如防止雪崩这件事，就是需要判断出g一定不在。

## BloomFilter 的缺点 ##

> 就像上面的例子一样，之所以能再去时间上和空间上效率特别高，它牺牲的是准确性和删除的便利性。

*  误判：就像上面例子中f元素一样，他的几个K值位置都是1，所以就会误判存在。
 *  删除困难：一个放入容器的元素映射到bit数组的K个位置上是1，删除的时候不能简单的直接置为0，因为还有其他的元素。

## guava实现布隆过滤器 ##

*  引入Guava包

<dependency>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
                <version>23.0</version>
     </dependency>

*  用例

public class TestBloomFilter { 
            private static int total = 1000000;
            private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
    
            public static void main(String[] args) { 
                // 初始化1000000条数据到过滤器中
                for (int i = 0; i < total; i++) { 
                    bf.put(i);
                }
                // 匹配已在过滤器中的值，是否有匹配不上的
                for (int i = 0; i < total; i++) { 
                    if (!bf.mightContain(i)) { 
                        System.out.println("有坏人逃脱了~~~");
                    }
                }
                // 匹配不在过滤器中的10000个值，有多少匹配出来
                int count = 0;
                for (int i = total; i < total + 10000; i++) { 
                    if (bf.mightContain(i)) { 
                        count++;
                    }
                }
                System.out.println("误伤的数量：" + count);
            }
        }

> 错误率越大，所需要的空间和时间就越小，反之错误率越小，需要的空间和时间就越大。
> 
> 所以BloomFilter的实现在于对错误率的容忍程度，可以在过滤一些非常规的请求，垃圾短信，垃圾邮件等场景使用。

[avatar]: