BloomFilter

概述

本文主要介绍：

1. BloomFilter原理
   2.使用Google Guava的BloomFilter

BloomFilter原理

BloomFilter主要用于检索一个元素是否在集合中。优点是空间效率和查询效率比较高。缺点是存在误判率。

实现

1.定义一个位数组
2.添加元素
使用k个哈希函数映射到位数组中，把位数组指定下标设置为1
3.判断元素是否在集合中
对元素使用k个哈希函数计算k个哈希值，检查这些哈希值作为下标对应位数组的位置是否都为1，如果都为1则认为元素在集合中，否则元素不在集合中。这里可能会存在误判。

误判率

定义下参数：
m---位数组的长度
n---加入其中的元素的个数
k---哈希函数的个数
f---误判率

在元素经过一个哈希函数后，某个位置没有设置为1的概率为：
1-1/m
因此，经过k个哈希函数后，该位置还没有设为1的概率为：

插入n个元素后，该位置还没有设置为1的概率为：

所以被设置为1的概率为：

误判率-判断一个元素是否在集合时，经过k个哈希函数后映射到位数组的位置都已经设置为1的概率。

这里需要引入极限：

因此：
误判率为：

两边都取自然对数：

只要g取最小值，p就能取到最小值，由于p＝e^(-nk/m),我们可以将g改写为

根据对称法则，当p＝1/2时，也就是k＝ln2*(m/n)时，g取得最小值，在这种情况下，最小的错误率p＝（1/2）^k≈(0.6185)(m/n)。p＝1/2对应着位数组中0和1各半。换句话说，想保持错误率低，最好让位数组有一半还空着。

位数组大小
在给定n（集合中元素的个数）和错误率（最优函数个数k的的错误率）的情况下，位数组M的大小计算，在最优k的情况下

化简得到：

这意味着在错误率为p的情况下，布隆过滤器的长度为m才能容纳n个元素（以上计算基于n,m->∞）。

使用guava中的BloomFilter

1.引入依赖

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

2.创建BloomFilter对象，需要传入Funnel对象，预估的元素个数，错误率

BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000,0.00001);

注：Funnel 描述了如何把一个具体的对象类型分解为原生字段值，从而写入 PrimitiveSink
3.使用put方法添加元素

filter.put("A");

4.使用mightContain方法判断元素是否存在

filter.mightContain("D");

完整代码：

    @Test
    public void testExist(){
        BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000,0.00001);
        
        filter.put("A");
        filter.put("B");
        filter.put("C");
        
        
        if(filter.mightContain("A")){
            System.err.println("Has Exist A");
        }else{
            System.err.println("No Exist A");
        }
        
        
        if(filter.mightContain("D")){
            System.err.println("Has Exist D");
        }else{
            System.err.println("No  Exist D");
    
        }
    }

总结

BloomFilter主要用于海量数据的处理，它占用空间小，查找的效率高（时间复杂度位O(k),k为哈希函数个数），但是存在一定的误判率。如果数据量较小，可以直接使用Bitmap.

****参考文章
https://blog.csdn.net/lvsaixia/article/details/51503231