- 首先初始化了一个 int 数组。
- 写入数据的时候进行三次
hash运算，同时把对应的位置置为 1。
- 查询时同样的三次
hash运算，取到对应的值，一旦值为 0 ，则认为数据不存在。
实现逻辑其实就和上文描述的一样。
下面来测试一下，同样的参数：
-Xms64m -Xmx64m -XX:+PrintHeapAtGC
@Test public void bloomFilterTest(){ long star = System.currentTimeMillis(); BloomFilters bloomFilters = new BloomFilters(10000000) ; for (int i = 0; i < 10000000; i++) { bloomFilters.add(i + "") ; } Assert.assertTrue(bloomFilters.check(1+"")); Assert.assertTrue(bloomFilters.check(2+"")); Assert.assertTrue(bloomFilters.check(3+"")); Assert.assertTrue(bloomFilters.check(999999+"")); Assert.assertFalse(bloomFilters.check(400230340+"")); long end = System.currentTimeMillis(); System.out.println("执行时间：" + (end - star)); }
执行结果如下：
只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。
当让我把数组长度缩小到了 100W 时就出现了一个误报，400230340 这个数明明没在集合里，却返回了存在。
这也体现了 Bloom Filter 的误报率。
我们提高数组长度以及 hash 计算次数可以降低误报率，但相应的 CPU、内存的消耗就会提高；这就需要根据业务需要自行权衡。
Guava 实现
刚才的方式虽然实现了功能，也满足了大量数据。但其实观察 GC 日志非常频繁，同时老年代也使用了 90%，接近崩溃的边缘。
总的来说就是内存利用率做的不好。
其实 Google Guava 库中也实现了该算法，下面来看看业界权威的实现。
-Xms64m -Xmx64m -XX:+PrintHeapAtGC
@Test public void guavaTest() { long star = System.currentTimeMillis(); BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 10000000, 0.01); for (int i = 0; i < 10000000; i++) { filter.put(i); } Assert.assertTrue(filter.mightContain(1)); Assert.assertTrue(filter.mightContain(2)); Assert.assertTrue(filter.mightContain(3)); Assert.assertFalse(filter.mightContain(10000000)); long end = System.currentTimeMillis(); System.out.println("执行时间：" + (end - star)); }
也是同样写入了 1000W 的数据，执行没有问题。
观察 GC 日志会发现没有一次 fullGC，同时老年代的使用率很低。和刚才的一对比这里明显的要好上很多，也可以写入更多的数据。
源码分析
那就来看看 Guava 它是如何实现的。
构造方法中有两个比较重要的参数，一个是预计存放多少数据，一个是可以接受的误报率。 我这里的测试 demo 分别是 1000W 以及 0.01。
Guava 会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小 numBits 以及需要计算几次 Hash 函数 numHashFunctions 。
这个算法计算规则可以参考维基百科。
put 写入函数
真正存放数据的 put 函数如下：
- 根据
murmur3_128方法的到一个 128 位长度的byte[]。
- 分别取高低 8 位的到两个
hash值。
- 再根据初始化时的到的执行
hash的次数进行hash运算。
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
其实也是 hash取模拿到 index 后去赋值 1.
重点是 bits.set() 方法。
其实 set 方法是 BitArray 中的一个函数，BitArray 就是真正存放数据的底层数据结构。
利用了一个 long[] data 来存放数据。
所以 set() 时候也是对这个 data 做处理。
- 在
set之前先通过get()判断这个数据是否存在于集合中，如果已经存在则直接返回告知客户端写入失败。
- 接下来就是通过位运算进行
位或赋值。
get()方法的计算逻辑和 set 类似，只要判断为 0 就直接返回存在该值。
mightContain 是否存在函数
前面几步的逻辑都是类似的，只是调用了刚才的 get() 方法判断元素是否存在而已。
总结
布隆过滤的应用还是蛮多的，比如数据库、爬虫、防缓存击穿等。
特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。
