BloomFilter简介

墨蓝 2022-01-22 00:49 202阅读 0赞

### 一.简介 ###

BloomFilter底层是一个位图（位数组）的数据结构，通过k个hash函数将这个元素映射到位数组的k个点，将他们设置为1。检索时，我们查看这k个点是否都为1就能够判断元素是否在BloomFilter中（会有一定的误差率）；如果k个点有一个点不为1，那么这个元素肯定不在BloomFilter里面。大致的数据结构：  
![在这里插入图片描述][20190604171935786.]

### 二.使用场景 ###

1.海量数据的去重  
2.处理缓存穿透的场景，用于校验请求的key是否存在

### 三.使用demo ###

guava的BloomFilter包

package com.vip.learn.guava;
    
    import com.google.common.hash.BloomFilter;
    
    import java.nio.charset.Charset;
    
    /**
     * Created by andrew.huang on 2019/6/3
     */
    public class BloomFilterMain {
    
    	public static void main(String[] args) {
    		BloomFilter<String> bloomFilter = BloomFilter.create((from, into) -> {
    				into.putString(from, Charset.defaultCharset());
    		}, 32 * 1024 * 1024L, 0.01d);
    
    		for(int i = 0;i < 10;i++){
    			bloomFilter.put(Thread.currentThread().getName() + i);
    		}
    
    		System.out.println(bloomFilter.mightContain("1"));
    		System.out.println(bloomFilter.mightContain(Thread.currentThread().getName() + "1"));
    	}
    }

输出结果：  
![在这里插入图片描述][20190604174628670.]

### 四.guava bloomFilter原理 ###

1.BloomFilter.create()  
（1）先看看官方api文档对create四个方法的解释  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70]  
主要的三个参数：  
\*funnel:你要怎么插数据到bloomFilter  
\*expectedInsertions：期待bloomfilter里面包含的元素个数  
\*fpp（false positive probability）:错误容忍率

（2）探索下底层bloomfilter根据这几个参数是怎么处理的  
![在这里插入图片描述][20190604175926452.]  
可以看到BloomFilter这里使用了一个BloomFilterStrategies.MURMUR128\_MITZ\_64的策略类  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 1]  
里面的获取numBits和numHashFunctions都是依据数学理论计算出来，有兴趣可以了解https://blog.csdn.net/v\_JULY\_v/article/details/6685894

2.BloomFilter.put()方法  
![在这里插入图片描述][20190604182311764.]  
可以看到BloomFilter实际上是通过strategy类去实现，真正的put方法是  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 2]  
点进去可以看到，这个类主要是通过一个murmur3\_128的hash函数去获取hash，根据hash函数的个数，去执行k次hash算法将值put进去

3.BloomFilter.mightContains()方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 3]  
可以看到通过k个hash算法，只要有一个BitArray.get()得到的返回值不为true（也就是在那个元素位置上不为1），那么就会返回false

4.guava BloomFilter的缺点  
不能删除元素，必须在预估好容量之后再去设置BloomFilter

### 五.总结 ###

BloomFilter的实现关键在于位数组容量的大小，容错率的数值和hash函数的选择，在可以容忍一定概率的错误率情况下，能够高效的处理海量数据的去重和判重。

from:andrew.huang

[20190604171935786.]: /images/20220122/6601ded5e0f445b38a087504432ee394.png
[20190604174628670.]: /images/20220122/66cc2a9d90674da886545cc2a08d63fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70]: /images/20220122/e54022b4e76048e09a52d1e0096a38e2.png
[20190604175926452.]: /images/20220122/bdcb72dc27c149829b5d6c56a98e61a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 1]: /images/20220122/ea54e84f26b44fdcbca0fd2a140236e3.png
[20190604182311764.]: /images/20220122/cc8ce40a7dcf44f2a91104b481fdf310.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 2]: /images/20220122/a74ecc46134b4f26b30abb8e9580aacd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpcHNob3BfZmluX2Rldg_size_16_color_FFFFFF_t_70 3]: /images/20220122/aff819dd78834958a13afaa5ac8fb070.png