布隆过滤器的原理，优缺点

布隆过滤器是干什么的&＃xff1f;

我们的项目常会用到redis作为缓存&＃xff0c;极大提高数据库的效率&＃xff0c;但是这里有一个问题&＃xff1a;缓存穿透

什么是缓存穿透&＃xff1a;缓存穿透说简单点就是大量请求的 key 根本不存在于缓存中&＃xff0c;导致请求直接到了数据库上&＃xff0c;根本没有经过缓存这一层。举个例子&＃xff1a;某个黑客故意制造我们缓存中不存在的 key 发起大量请求&＃xff0c;导致大量请求落到数据库

布隆过滤器在很大成都上可以解决这种问题

做法大致是&＃xff1a;把所有可能存在的请求的值都存放在布隆过滤器中&＃xff0c;当用户请求过来&＃xff0c;先判断用户发来的请求的值是否存在于布隆过滤器中。不存在的话&＃xff0c;直接返回请求参数错误信息给客户端&＃xff0c;存在的话去redis缓存中查数据

其实布隆过滤器也可能出现误判&＃xff0c;总的来说&＃xff1a; 布隆过滤器说某个元素存在&＃xff0c;小概率会误判。布隆过滤器说某个元素不在&＃xff0c;那么这个元素一定不在。

为什么呢&＃xff1f;

我们先看一下布隆过滤器是如何实现添加和查询数据的

添加数据&＃xff1a;

1. 使用布隆过滤器中的哈希函数对元素值进行计算&＃xff0c;得到哈希值&＃xff08;有几个哈希函数得到几个哈希值&＃xff09;。

2. 根据得到的哈希值&＃xff0c;在位数组中把对应下标的值置为 1。

查询数据&＃xff1a;

1. 对给定元素再次进行相同的哈希计算&＃xff1b;

2. 得到值之后判断位数组中的每个元素是否都为 1&＃xff0c;如果值都为 1&＃xff0c;那么说明这个值在布隆过滤器中&＃xff0c;如果存在一个值不为 1&＃xff0c;说明该元素不在布隆过滤器中。

即使使用多个hash函数来减少hash碰撞了&＃xff0c;但是任然有可能出现hash碰撞&＃xff0c;因为不同的字符串可能哈希出来的位置相同 &＃xff0c;从而导致误判&＃xff0c;了解hashmap源码的同学对这里应该是很好理解的&＃xff0c;不过多赘述了

我的另一篇博客用java实现了非常简单的布隆过滤器&＃xff1a;

用java实现一个非常简单的布隆过滤器_m0_53611007的博客-CSDN博客

优点&＃xff1a;

1.占用内存小

2.增加和查询元素的时间复杂度为&＃xff1a;O(k)&＃xff0c;(k为哈希函数的个数&＃xff0c;一边比较小)&＃xff0c;与数据量大小无关

3.哈希函数相互之间没有关系&＃xff0c;方便硬件并行运算

4.布隆过滤器不需要存储元素本身&＃xff0c;在某些对保密要求比较严格的场合有很大优势

5.数据量很大时&＃xff0c;布隆过滤器可以表示全集

6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点&＃xff1a;

1.误判率&＃xff0c;即存在假阳性(False Position)&＃xff0c;不能准确判断元素是否在集合中(概率较小)

2.不能获取元素本身

3.一般情况下不能从布隆过滤器中删除元素