布隆过滤器详解

前言

假设有以下需求：在用户注册时，判断输入的用户名是否已被注册？
首先我们想到的是用HashMap存储所有用户名，使得查询操作在O（1）时间复杂度完成，但他的缺点是内存占用过高，当数据量上亿时HashMap对内存要求很高。此时布隆过滤器就可以帮助我们高效的完成该功能。

简介

布隆过滤器（Bloom Filter）是一种节省空间的概率数据结构，由一个很长的二进制向量和一系列随机映射函数组成，主要用于判断一个元素是否在一个集合中。例如，判断用户名是否可能存在于用户名集合中，布隆过滤器为了效率付出的代价是它的本质是概率性的，这意味着它可能会有一些误报结果，误报意味着它可能显示用户名已被占用，但实际并没有。

当一个元素加入集合时，布隆过滤器首先通过k个散列函数将该元素映射成k个点位，然后在底层位数组中将对应的点位上的bit置为1。
当查询一个元素是否存在时，布隆过滤器会用同样的方式计算出点位信息，然后看这些点位是否都为1，如果有任意点位为0，则代表该元素一定不存在，若所有点位都为1，则代表该元素很有可能存在。

布隆过滤器具有以下属性：

• 与标准的哈希表不同的是，固定大小的布隆过滤器可以表示具有任意多元素的集合。
• 布隆过滤器添加元素永远不会失败，但随着元素的添加，误报率也稳步增加，直到过滤器中所有bit都置为1，此时所有查询都会产生肯定结果。
• 布隆过滤器永远不会产生假阴性结果，即在用户名存在时判断为不存在。
• 你无法从布隆过滤器中删除元素，因为如果通过删除k个哈希函数生成的索引处的bit来删除单个元素，则有可能导致其他几个元素也被删除。

底层数据结构

一个空的布隆过滤器是一个m位组成的位数组，全部初始化为0

现在我们想在过滤器中输入"semlinker"，假设过滤器有3个哈希函数分别是h1、h2、h3。
首先，我们将通过哈希函数计算出3个哈希值：

h1("semlinker") % 10 = 2		//余10是因为位数组长度为10
h2("semlinker") % 10 = 4
h3("semlinker") % 10 = 6
1
2
3

然后，我们再向过滤器输入"kakuqo"，经散列其生成点位3，4，7，可以得到如下结果。

此时，我们搜索"fullstack"，计算出其散列点位为2、3、7，从下图可以看出相应位置都为1，与事实不符，这是误报的情形，产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同比特位上。

应用

布隆过滤器的应用场景大致总结为：数据量大、需要去重

• Google Chrome使用布隆过滤器识别恶意url
• Google BigTable、Apache HBase和Apache Cassandra以及Postgresql使用布隆过滤器来减少对不存在的行或列的磁盘查找
• Medium使用布隆过滤器避免推荐给用户已经读过的文章
• Redis中解决缓存穿透问题

优缺点

优点

相比于其他数据结构，布隆过滤器在时间和空间方面都有巨大优势，布隆过滤器存储和插入\查询时间复杂度都是O（k）。另外散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求严格的场景很有优势。

布隆过滤器可以表示全集，其他任何数据结构都不能

若k和m相同，则使用同一组散列函数的两个布隆过滤器的交并运算可以使用位操作进行

缺点

布隆过滤器最大的缺点就是具有误算率，随着插入元素的增加，误算率也随之增加。在降低误算率方面有不少研究，因此出现了很多布隆过滤器的变种。

另外，你不能从布隆过滤器删除元素。布谷过滤器支持元素删除。

实战

1.redis服务器安装RedisBloom插件
2.使用Redission初始化布隆过滤器（需要提前计算好插入数量、误判率）

@Service
public class BloomFilterService {
 
    @Autowired
    private RedissonClient redissonClient;
 
    /**
     * 创建布隆过滤器
     * @param filterName 过滤器名称
     * @param expectedInsertions 预测插入数量
     * @param falseProbability 误判率
     * @param <T>
     * @return
     */
    public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) {
        RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falseProbability);
        return bloomFilter;
    }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.单元测试布隆过滤器是否工作良好

@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class BloomFilterTest {
 
    @Autowired
    private BloomFilterService bloomFilterService;
 
    @Test
    public void testBloomFilter() {
        // 预期插入数量
        long expectedInsertions = 10000L;
        // 错误比率
        double falseProbability = 0.01;
        RBloomFilter<Long> bloomFilter = bloomFilterService.create("ipBlackList", expectedInsertions, falseProbability);
 
        // 布隆过滤器增加元素
        for (long i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
        long elementCount = bloomFilter.count();
        log.info("elementCount = {}.", elementCount);
 
        // 统计误判次数
        int count = 0;
        for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        log.info("误判次数 = {}.", count);
        bloomFilter.delete();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

参考

https://cuizb.top/myblog/article/1644224367
https://blog.csdn.net/qq_14855971/article/details/123650368