漫画：什么是布隆过滤器

vlambda
2021-04-20

漫画：什么是布隆过滤器

来源：架构师进化论

———— / 面试中 / ————

———— / 第二天 / ————

布隆过滤器的数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：

如果我们要把一个key映射到布隆过滤器中，就需要利用所有哈希函数对这个key进行映射，得到一系列的哈希值，把这些哈希值当成数据下标，把下标对应的数组元素置为1。

假设现在对对肯德基的菜单进行构建布隆过滤器：

首先，现在我们把“汉堡”这个key映射到布隆过滤器中，通过哈希函数映射的结果为1和7，我们现在把对应的bit元素标志为1。

Ok，我们现在再存一个值 “鸡腿”，如果哈希函数返回2和5的话，图继续变为：

接着我们想要查询某个key是不是在布隆过滤器中，只需要再通过哈希函数或者一系列的哈希值，然后把这些哈希值作为数组下标查看对应的元素是否为1。

这里有两种情况：

1. 不是所有位置都为1，肯定不在布隆过滤器中

瞧，如果我们要查询“可乐“这个key是否在布隆过滤器中的时候，发现通过哈希函数2映射的结果6对应的bit位是0。

因为如果“可乐”这个key如果在过滤器中的话，下标为2和6的bit位肯定都是1.所以我们可以很肯定的说，”可乐”这个key不在布隆过滤器中。

2.所有位置的bit位都是1，可能在布隆过滤器中

如果我们要查询“鸡肉卷”这个key是不是在布隆过滤器中的时候，发现通过哈希函数获得的哈希值所对应的bit都被置为1了，那这个值是不一定在布隆过滤器中的，为什么呢？

布隆过滤器的缺点

因为哈希函数可能是存在冲突的。在发生冲突的情况下，如果刚好所有的值都被置为1了，就会产生误判。为了能做到在时间和空间上的高效率，布隆过滤器牺牲了判断的准确率。所以对于不能接受误判的业务场景，通常需要在通过布隆过滤器之后再做一层判断。

另外布隆过滤器还有一个缺点就是删除比较困难，假如要删除一个key的话，不能简单的把这个key映射到的bit位都简单的置为0，因为哈希冲突的情况下，会影响其它key的判断。如果要删除的话，可以参考 Counting Bloom Filter。

如何控制布隆过滤器的准确率

首先。布隆过滤器如果太小的话， bit 很快就会被全置为1，不论查询什么，结果都是“可能存在”，就起不到过滤效果了。所以布隆过滤器的长度会直接影响准确率，长度越长，准确率越高。

另外，哈希函数的个数也会影响布隆过滤器的准确率。哈希函数越多的话，对每个key进行映射的时候，被置为1的bit位也就越多，也会很快就把布隆过滤器打满。

假设我们的预估数据量为n，期望的误判率为fpp的话，bit数组大小和哈希函数个数k可以通过以下公式计算得到：

（数组大小m的计算公式）

(哈希函数个数k的计算公式）

实战：使用Guava提供的布隆过滤器

首先需要引入依赖，在pom里面加上：

  
    
    
  
   
     
     
   <!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
   
     
     
   <dependency>
   
     
     
    <groupId>com.google.guava</groupId>
   
     
     
    <artifactId>guava</artifactId>
   
     
     
    <version>29.0-jre</version>
   
     
     
   </dependency>

然后测试一下误判率：

  
    
    
  
   
     
     
   import com.google.common.hash.BloomFilter;
   
     
     
   import com.google.common.hash.Funnels;
   
     
     
   

   
     
     
   public class BloomFilterTest {
   
     
     
    public static void main(String[] args) {
   
     
     
    int total = 100000; //总数量
   
     
     
   

   
     
     
    BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
   
     
     
    // 初始化数据到布隆过滤器中
   
     
     
    for (int i = 0; i < total; i++) {
   
     
     
    bf.put(i);
   
     
     
    }
   
     
     
    // 判断值是否存在过滤器中
   
     
     
    int count = 0;
   
     
     
    for (int i = total; i < total + 10000; i++) {
   
     
     
    if (bf.mightContain(i)) {
   
     
     
    count++;
   
     
     
    }
   
     
     
    }
   
     
     
    System.out.println("误判的数量 ～ " + count);
   
     
     
    }
   
     
     
   }

漫画：什么是布隆过滤器

可以看到测试结果中，有286个元素不在布隆过滤器中，却被误判了。误判率= 281/10000 = 0.0281。

翻一下源码，可以看到误判率的默认值为0.03，和我们的测试结果差不多。

  
    
    
  
   
     
     
   public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
   
     
     
    return create(funnel, expectedInsertions, 0.03D);
   
     
     
   }

然后我们修改误判率为0.01，再进行测试：

  
    
    
  
   
     
     
   import com.google.common.hash.BloomFilter;
   
     
     
   import com.google.common.hash.Funnels;
   
     
     
   

   
     
     
   public class BloomFilterTest {
   
     
     
    public static void main(String[] args) {
   
     
     
    int total = 100000; //总数量
   
     
     
   

   
     
     
    BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.01);
   
     
     
    // 初始化数据到布隆过滤器中
   
     
     
    for (int i = 0; i < total; i++) {
   
     
     
    bf.put(i);
   
     
     
    }
   
     
     
    // 判断值是否存在过滤器中
   
     
     
    int count = 0;
   
     
     
    for (int i = total; i < total + 10000; i++) {
   
     
     
    if (bf.mightContain(i)) {
   
     
     
    count++;
   
     
     
    }
   
     
     
    }
   
     
     
    System.out.println("误判的数量 ～ " + count);
   
     
     
    }
   
     
     
   }