布隆过滤器

什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实现原理

与HashMap比较想象，不同之处在于布隆过滤器是存储的Bit位数组，内容值只有1 与 0 非常显著的减少了存储大小。所以布隆过滤器只能判断是否匹配，而无法获取对应匹配值。

了解HashMap数据结构的同学都应该知道HashMap会有概率发生碰撞，在发生碰撞时会生成链表或红黑树来解决，那布隆过滤器是如何解决这个问题的呢？

布隆过滤器数据结构

布隆过滤器数据结构

上图边表示分别存储A、B、C三个值，与下边数组的连接线分别表示不同的Hash值地址。通过过一个写入的值计算多个Hash地址，这样就可以尽量减少碰撞的可能，但绝对无法做到绝对不碰撞。

只能通过增加计算Hash的条数或增加数组长度来减少碰撞可能。

布隆过滤器如何支持删除

根据上边了解到的信息，我们知道因布隆过滤器是使用bit位数组存储的，如果支持删除操作的话，可能会影响其他值的匹配。那么我们还有其他方式来使布隆过滤器支持删除吗？

布隆过滤器支计数

我们可以改变一下数据结构，将数组改为计数形式就可以实现，用空间来换功能。

适用场景

1. 利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。（缓存穿透）

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1ro14ignkt5pb