火了50年的技术—布隆过滤器( 二 ) 原文：火了50年的技术—布隆过滤器前言

二、删除困难到这里我不说大家应该也明白为什么吧，作为你们的暖男老哥，还是讲一下吧。
还是用上面的举例，因为“你好”和“hello”的hash值相同，对应的数组下标也是一样的。
这时候老哥想去删除“你好” ，将下标为2里的二进制数据，由1改成了0 。
那么我们是不是连“hello”都一起删了呀。（0代表有这个数据， 1代表没有这个数据）
到这里是不是对布隆过滤器已经明白了，都说了我是暖男。
文章插图
实现布隆过滤器有很多种实现方式，其中一种就是Guava提供的实现方式。
一、引入Guava pom配置...if (someobject != null) {someobject.doCalc();}...复制代码二、代码实现【火了50年的技术—布隆过滤器】这里我们顺便测一下它的误判率。
import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;public class BloomFilterCase {/*** 预计要插入多少数据*/private static int size = 1000000;/*** 期望的误判率*/private static double fpp = 0.01;/*** 布隆过滤器*/private static BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);public static void main(String[] args) {// 插入10万样本数据for (int i = 0; i < size; i++) {bloomFilter.put(i);}// 用另外十万测试数据，测试误判率int count = 0;for (int i = size; i < size + 100000; i++) {if (bloomFilter.mightContain(i)) {count++;System.out.println(i + "误判了");}}System.out.println("总共的误判数:" + count);}}复制代码运行结果：
文章插图
10万数据里有947个误判，约等于0.01% ，也就是我们代码里设置的误判率：fpp = 0.01 。
深入分析代码核心BloomFilter.create方法
@VisibleForTestingstaticBloomFilter create(Funnel funnel, long expectedInsertions, double fpp, Strategy strategy) {。。。。 }复制代码这里有四个参数：

funnel：数据类型(一般是调用Funnels工具类中的)
expectedInsertions：期望插入的值的个数
fpp：误判率(默认值为0.03)
strategy：哈希算法

我们重点讲一下fpp参数
fpp误判率情景一：fpp = 0.01

误判个数：947

文章插图

占内存大小：9585058位数

文章插图
情景二：fpp = 0.03（默认参数）

误判个数：3033

文章插图

占内存大小：7298440位数

文章插图
情景总结

误判率可以通过fpp参数进行调节
fpp越小，需要的内存空间就越大：0.01需要900多万位数， 0.03需要700多万位数。
fpp越小，集合添加数据时，就需要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。（忘了去看上面的布隆过滤存入数据的过程）

上面的numBits ，表示存一百万个int类型数字，需要的位数为7298440 ， 700多万位。理论上存一百万个数，一个int是4字节32位，需要481000000=3200万位。如果使用HashMap去存，按HashMap50%的存储效率，需要6400万位。可以看出BloomFilter的存储空间很小，只有HashMap的1/10左右