布隆过滤器怎么删除数据（布隆过滤器BloomFilter）

小君 2023-05-16 05:05:56 145

布隆过滤器怎么删除数据（布隆过滤器BloomFilter）3）布隆过滤器的特点如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。可以通过一（多）个Hash函数将一（多）个元素映射成一（多）个位阵列（或者是位图）中的一（多）个点。这样一来，我们计算完哈希值，只要看看对应的点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。以上这些情况，最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个像 Yahoo Hotmail 和 Gmai 那样的

1、布隆过滤器概述

1）布隆过滤器的使用场景：

比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）

在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上

在网络爬虫里，一个网址是否被访问过

以上这些情况，最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。

比如说，一个像 Yahoo Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存。然后将这些信息存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

2）布隆过滤器的思想

如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。可以通过一（多）个Hash函数将一（多）个元素映射成一（多）个位阵列（或者是位图）中的一（多）个点。这样一来，我们计算完哈希值，只要看看对应的点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

3）布隆过滤器的特点

布隆过滤器是一种概率型数据结构，它的特点是高效地插入和查询，能确定某个字符串一定不存在或者可能存在。（注意：能判断一定不存在，但是不能判断一定存在，也就是只能知道100%不在里面，且有一定概率在里面）

布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但是误差可控，同时不支持删除操作（实现删除的思路：设置两个位图，将删除后的添加到删除位图，查询的时候两个位图都查询，如果第一个位图存在，再查删除位图，当删除位图不存在的时候该元素存在，否在表示已经被删除了）

2、布隆过滤器实现形式

1）位阵列形式

布隆过滤器怎么删除数据（布隆过滤器BloomFilter）(1)

标注：如上图所示使用二维数据实现位阵列，其中n = i ∗ 8 j n=i*8 jn=i∗8 j，n表示关键字的哈希值，这里哈希函数是：对64取余。得到哈希值后通过上图所示的计算方法得到i和j，并将对应在位矩阵中的位置标注为1

查找：按上图方法计算查找关键字哈希值，并得到i和j，如果在位矩阵中该位置标记为1表示存在（一定概率存在，因为会有哈希冲突的情况），标注为0表明不存在。

2）位图形式

布隆过滤器怎么删除数据（布隆过滤器BloomFilter）(2)

标注：当一个元素加入位图时，通过 k 个 hash 函数将这个元素映射到位图的 k 个点，并把它们置为 1；如上图所示，str1通过三个哈希函数计算得到三个哈希值，将三个哈希值的映射地址中的bit位置位1（如蓝线所示），str2同理（如红线所示）

查找：当检索时，再通过 k 个 hash 函数运算检测位图的 k 个点是否都为 1；如果有不为 1 的点，那么认为该 key 不存在；如果全部为 1，则可能存在；

为什么不能删除，为什么不知道某个关键字一定存在？

通过上述示例就可以看出为什么不能确实一定存在：如果一个关键字计算得到哈希值的位图位置是4、6、12，并且这些位置都是1，按理说它是存在的，但是这个关键字时不存在的（因为这些位置是str1和str2一起置的1）

在位图中每个槽位只有两种状态（0 或者 1），一个槽位被设置为 1 状态，但不确定它被设置了多少次，也就是不知道被多少个 key 哈希映射而来以及是被具体哪个 hash 函数映射而来；所以不知道谁把这一位置为1了，也不知道置了多少次，直接删除可能会导致很多存在的元素，查找的时候结果却显示不存在。

3、布隆过滤器在数据库中的应用

布隆过滤器通常用于判断某个 key 一定不存在的场景，同时允许判断存在时有误差的情况；常见处理场景：

① 缓存穿透的解决

② 热 key 限流

布隆过滤器怎么删除数据（布隆过滤器BloomFilter）(3)

发生缓存穿透原因：为了减轻数据库（mysql）的访问压力，在 server 端与数据库（mysql）之间加入Redis缓存用来存储热点数据；server端请求数据时，如果这个数据在Redis里面没有，就需要查mysql，最终请求压力全部涌向数据库，导致了缓存的穿透

一般访问步骤如图的2）所示

解决方案：一种是在Redis端存储key值不存value值，查找的时候先在Redis中查，同时给key值设置过期时间，定时清理不存在的key；另一种是在server端设置布隆过滤器，将MySQL中的key放入布隆过滤器中，这样能够先筛选出不存在的数据，避免了黑客用不存在数据攻击数据库，从而造成缓存穿透。

4、布隆过滤器的设计

在实际应用中该如何设计，如该选择多少个 hash 函数？要分配多少空间的位图？预期存储多少元素？允许的查询误差是多少？

设计步骤：