最近在一篇文章中学到了一个新的知识点【布隆过滤器】，初步了解了下，然后就有了下面这篇文章
基本概念
来自于维基百科的介绍
如何判断一个元素是不是存在于一个集合里面，一般想到的是将集合中的所有元素保存起来，然后通过比较确定。链表、树、散列表（又称哈希表）等等数据结构来完成确定操作。但是随着集合中的元素的增加，需要存储的空间越大，同时检索速度也越来越慢
布隆过滤器的原理是，当一个元素被加入到集合中时，通过K个散列函数将这个元素映射成一个数组中的K个点，把它们置为1，检索时，只要看看这些点是不是都是1就（大约）知道集合中有没有它了：
如果这些点有任何一个0，则被检元素一定不在；
如果都是1，则被检元素很可能在。
这就是布隆过滤器的基本思想。
Bloom Filter有以下几个特点：
- 不存在漏报（False Negative），即某个元素在某个集合中，肯定能报出来。
- 可能存在误报（False Positive），即某个元素不在某个集合中，可能也被爆出来。
- 确定某个元素是否在某个集合中的代价和总的元素数目无关。
优点
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。
布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。另外，散列函数相互之间没有关系，方便由硬件并行实现。
布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
缺点
一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。
然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。
另外计数器回绕也会造成问题。
实现
这里不介绍自己用java方式来实现，我们来看看guava的实现方式
public class BloomFilterTest {
public static void main(String[] args) {
long start = System.currentTimeMillis();
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 10000000, 0.01);
for(int i=0;i<=10000000;i++){
bloomFilter.put(i);
}
System.out.println(bloomFilter.mightContain(1));
System.out.println(bloomFilter.mightContain(2));
System.out.println(bloomFilter.mightContain(10000000));
long end = System.currentTimeMillis();
System.out.println("执行时间：" + (end - start));
}
}
结果：
true
true
true
执行时间：6520
源码分析
来看看guava是如何实现的，先看看构造方法中两个比较重要的参数，一个预计存放多少数据（Demo中存放的是1000W），还一个可以接受的误报率（Demo中的为0.01），源码如下：
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {
Preconditions.checkNotNull(funnel);
Preconditions.checkArgument(expectedInsertions >= 0L, "Expected insertions (%s) must be >= 0", new Object[]{expectedInsertions});
Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", new Object[]{fpp});
Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", new Object[]{fpp});
Preconditions.checkNotNull(strategy);
if (expectedInsertions == 0L) {
expectedInsertions = 1L;
}
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException var10) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", var10);
}
}
Guava会通过你预计的数量以及误报率来帮你计算出应当会使用的数组大小numBits以及需要几次Hash函数numHashFunctions
put写入函数
put函数中有一个重要的方法set
bitsChanged |= bits.set((long)combinedHash % bitSize);
查看源发现set方法尽然是BitArray中的一个函数，BitArray是真正存放数据的底层数据结构
利用一个long[] data 来存放，所以set也是对这个data进行处理
final long[] data;
long bitCount;
boolean set(long index) {
if (!this.get(index)) {
long[] var10000 = this.data;
var10000[(int)(index >>> 6)] |= 1L << (int)index;
++this.bitCount;
return true;
} else {
return false;
}
}
整个set过程分如下几步：
- 在set之前先通过get方法判断这个元素是否在集合中，如果存在则返回false，写入失败
- 如果不存在，则通过位运算进行 位或赋值
- get方法的计算逻辑，只要判断为0就直接返回存在该值
mightContain 是否存在函数
mightContain方法最终调用的还是get方法
boolean get(long index) {
return (this.data[(int)(index >>> 6)] & 1L << (int)index) != 0L;
}
总结
布隆过滤器的应用场景还是蛮多的，比如在防止缓存击穿、爬虫等
特别是需要精确的知道某个数据不存在的时候做业务处理
End，感谢阅读