概述
本文主要介绍：
- 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
网友评论