布隆过滤器

Bertha 。 2022-10-07 00:45 194阅读 0赞

# 布隆过滤器 #

**快速入门Redis的文章，传送地址：[Redis基础知识][Redis]**

### 文章目录 ###

*  布隆过滤器
 *   *  一、介绍
     *  二、添加
     *  三、查询
     *  四、删除
     *  五、优缺点
     *   *  1. 优点
         *  2. 缺点
     *  六、误判率
     *  七、解决Redis缓存穿透问题

## 一、介绍 ##

布隆过滤器是一个二进制数组，它的作用是判断一个数是否存在于这个数组，0表示不存在，1表示存在，如下图所示：

![image-20210607230614426][]

## 二、添加 ##

如果要存入 “你好” 这个字符串，首先会经过n个哈希函数计算，会计算出不同的哈希值，然后将这几个哈希值映射到数组中，对应的位置的二进制数被修改为1，如下图所示：

![image-20210607231336059][]

下标为3、5、7的位置被修改成了1

## 三、查询 ##

比如说查询 “你好” 这个字符串，首先通过n个哈希函数计算出对应的数组位置是3、5、7，这三个位置的二进制数必须都是1才能表示 “你好” 这个字符串存在，这三个位置只要有一个位置不是1，那这个字符串就不存在。

## 四、删除 ##

布隆过滤器对于删除操作存在误删的情况。

比如现在有两个字符串 “你好” 和 “hello”，假如经过了一系列的哈希运算，最终得出二者在数组的位置都是下标为2的位置，那么此时这个下标位置同时表示了两个数据，“你好” 和 “hello”，如下图所示：

![image-20210607233851280][]

当要删除 “你好” 这个字符串时，会把下标为2的位置二进制数改为0，表示删除，但同时也会删除 “hello” 这个字符串，所以布隆过滤器存在误删现象。

## 五、优缺点 ##

### 1. 优点 ###

*  布隆过滤器是由二进制数组组成的，所以占用的空间非常小
 *  查询和插入操作速度快，根据哈希值计算出的位置去数组中寻找即可
    
     *  对应的时间复杂度是O(n)，n取决于哈希函数的个数，如果只有一个哈希函数，那么时间复杂度就是 O(1)
 *  保密性好，存储的都是二进制数据，不存储数据本身

### 2. 缺点 ###

*  删除操作时存在误删情况
 *  由于不同的数据计算出的哈希值可能是相同的，所以存在误判的情况
    
     *  假设 “hello” 和 “你好” 这两个数据计算出的哈希值是相同的，但是此时布隆过滤器中只存在 “你好” 这个数据，当要查询 “hello” 时，计算出的哈希值在数组中寻找位置时发现这个位置是1，布隆过滤器就会告知 “hello” 这个数据是存在的，但实际上是不存在的。

## 六、误判率 ##

在使用布隆过滤器的时候可以设置一个参数误判率：

*  误判率越小，越不容易出现误判，但哈希函数会越多，导致占用的空间就越大
 *  误判率越大，越容易出现误判，但哈希函数会越少，导致占用的空间就越小

**为什么不只使用一个哈希函数，而要使用多个哈希函数呢？**

*  如果只有一个哈希函数，那么不同的数据计算出的哈希值有很大的概率是相同的，容易造成误判
 *  如果使用多个哈希函数，每一个哈希函数使用不用的哈希算法，这样的话，计算出的下标值就不容易相同
    
     *  所以哈希函数越多，计算出的哈希值就越多，误差率就越低，但对应的空间占用越大

## 七、解决Redis缓存穿透问题 ##

*  缓存穿透指的是，请求的数据不存在于Redis中，导致请求直接达到了数据库，数据库无法承载过大的流量导致宕机。
 *  可以使用布隆过滤器存储所有可能访问的 key，不存在的 key 直接被过滤，存在的 key 则再进一步查询缓存和数据库
    
     *  请求到达时首先查找Redis的布隆过滤器，如果没有命中，直接返回（数据不在布隆过滤器就大概率不在数据库），这样大量无效的请求就不会到达数据库
     *  如果命中了，才去Redis和数据库中找

[Redis]: https://blog.csdn.net/weixin_49343190/article/details/113107376
[image-20210607230614426]: /images/20221005/34a03feadb6b44998b07426289d0ea3e.png
[image-20210607231336059]: /images/20221005/1f3cf9d5e2874538ac54ffc3b4c6bc40.png
[image-20210607233851280]: /images/20221005/f9325b18d0f64ecbad638c8a26fb261c.png