布隆过滤器 | Kang`Blog

原理

布隆过滤器：一种数据结构，由一个bit数组和hash Function组成，bit数组可以将其看成一个二进制数组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。

相比于我们平时常用的的 List、Map、Set 等数据结构，它占用空间更少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

优点

由于存储的是二进制数据，所以占用的空间很小
它的插入和查询速度是非常快的，时间复杂度是O（K），可以联想一下HashMap的过程
保密性很好，因为本身不存储任何原始数据，只有二进制数据

添加数据

使用布隆过滤器的哈希函数对Key存储的元素值进行计算，得到哈希值(有几个哈希函数得到几个哈希值)和索引值(哈希值 & n-1)；
根据得到的索引值，在位数组中把对应下标的值置为 1。

判断是否存在于布隆过滤器

对元素再次进行相同的哈希计算；
判断对应数组位置是否为1，如果有一个位置为0，就说明这个值不在布隆过滤器中；如果全部为1，则说明这个值可能在布隆过滤器中

删除数据

布隆过滤器无法删除数据，因为存在不同数据的哈希值相同的情况；
可以使用计数布隆过滤器

为什么是可能存在？

那些被置为 1 的位置也可能是由于其他元素的操作而改变的。比如，数据A 和数据B，这两个数据同时将一个位置变为了 1。在这种情况下，我们就不能判定“数据B”一定存在，这是布隆过滤器存在误判的根本原因。

怎样降低误判率？

增加bit数组长度，但如果太长会浪费资源
增加哈希函数的个数，个数太多会花费过多计算时间

使用

google 的 guava 和 Redission 都实现了布隆过滤器

<dependency>
    <groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>28.2-android</version>
</dependency>

<dependency>
	<groupId>org.redisson</groupId>
	<artifactId>redisson-all</artifactId>
	<version>2.10.0</version>
</dependency>

源码学习

默认false position proportion 判错率=0.03

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03D);
}
@VisibleForTesting
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", expectedInsertions);
    Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", fpp);
    Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", fpp);
    Preconditions.checkNotNull(strategy);
    if (expectedInsertions == 0L) {
        expectedInsertions = 1L;
    }

    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);

    try {
        return new BloomFilter(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException var10) {
        throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", var10);
    }
}

计算bit数组大小

100万个数据，0.03的误判率，大约需要1600万的的bit数组长度

@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
   if (p == 0.0D) {
       p = 4.9E-324D;
   }
   return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D)));
}

计算哈希函数个个数

100万个数据，0.03的误判率，大约需要5个或6个哈希函数

@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
    return Math.max(1, (int)Math.round((double)m / (double)n * Math.log(2.0D)));
}