布隆过滤器

什么是布隆过滤器？

布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。

对于布隆过滤器而言，它的本质是一个位数组：位数组就是数组的每个元素都只占用1bit ，并且每个元素只能是0或者1。

布隆过滤器除了一个位数组，还有K个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

使用K个哈希函数对元素值进行K次计算，得到K个哈希值
根据得到的哈希值，在位数组中把对应下标的值置为1。

如果布隆过滤器判断某个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。总结就是：

布隆过滤器说某个元素在，可能会被误判
布隆过滤器说某个元素不在，那么一定不在

Google布隆过滤器

引入依赖

    <dependencies>
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>19.0</version>
        </dependency>
    </dependencies>

使用

public class BloomFilterTest {
    private static int size = 1000000;//预计要插入多少数据
    private static double fpp = 0.01;//期望的误判率
    private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), size, fpp);
    public static void main(String[] args) {
        //插入数据
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i+"");
        }
        int count = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i+"")) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("总共的误判数:" + count);
    }
}

Redis布隆过滤器

Redis 官方提供的布隆过滤器到了Redis4.0提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

布隆过滤器有二个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add只能一次添加一个元素，如果想要一次添加多个，就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到 bf.mexists 指令。

Redis 提供了自定义参数的布隆过滤器，需要在add之前使用bf.reserve指令显式创建。如果对应的key已经存在，bf.reserve会报错。bf.reserve有三个参数，分别是key,error_rate和initial_size。错误率越低，需要的空间越大。initial_size参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升。如果不使用bf.reserve，默认的error_rate是 0.01，默认的initial_size是100。

空间占用估计

//hash 函数的最佳数量 k
k=0.7*(l/n)  # 约等于
//错误率
f=0.6185^(l/n)  # ^ 表示次方计算，也就是 math.pow

位数组相对越长 (l/n)，错误率 f 越低;
位数组相对越长(l/n)，hash函数需要的最佳数量也越多，影响计算效率;
当一个元素平均需要1个字节(8bit)的指纹空间时(l/n=8)，错误率大约为 2%;

对比

Google布隆过滤器的缺点:

基于JVM内存的一种布隆过滤器
重启即失效
本地内存无法用在分布式场景
不支持大数据量存储

Redis布隆过滤器:

可扩展性Bloom过滤器：一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器
不存在重启即失效或者定时任务维护的成本;
基于Google实现的布隆过滤器需要启动之后初始化布隆过滤器

缺点：

需要网络IO，性能比Google布隆过滤器低

Redis-10丨布隆过滤器