本篇将对布隆过滤器的相关问题进行拆解。首先我们需要明确的问题是什么是布隆过滤器作用、组成、添加元素流程、查询元素的流程、特点【误判、不支持删除】布隆过滤器Bloom Filter是一种由位数组和一组哈希函数组成的数据结构主要用于判断一个元素是否在一个集合中。相比于我们平时常用的List、Map、Set等集合它在空间利用率上拥有明显优势这种优势源于它的使用过程中不需要像前文提到的常见集合那样保存数据本身——导致内存空间的大量占用它只需要存储0和1。然而它也并非没有缺点其一返回的结果是概率性的而不全然准确——这源于不同字符串哈希运算后的位置可能相同其二无法删除元素标准的布隆过滤器并不支持删除操作。在此基础上我们可以由此展开从布隆过滤器的添加元素流程、以及查询元素流程详细了解它的优点以及缺点添加元素时首先要使用布隆过滤器中的一组哈希函数对元素值进行计算得到相对应的哈希值。在此过程中需要适量增加哈希函数的个数以防止误判率过高。根据得到的哈希值在位数组中把对应下标的值置为1其余下标依旧为0。查询元素时首先要对给定元素再次进行相同的哈希计算计算出的索引值与上一个添加步骤中的索引值一一比对其中若任意一位为0则100%确定该元素绝对不存在于集合中若所有位都为1则可能存在于集合中——因为需要考虑误判风险。误判风险指的是在哈希计算的过程中可能存在哈希冲突的问题即在哈希函数将无限大的输入空间映射到有限的位数组空间时极易出现某些元素对应的哈希值下标指向同一个位置的情况。这也就详细地对上文中“返回的结果是概率性的”说法作出了解释。而上文中提到的第二个缺点无法删除元素。这指的是若在某些元素中同时存在两个不同的元素下标指向同一个位置即其下标置1。那么就不可能因为想要删除某一个元素贸然将下标置0而不考虑其他元素的情况所以标准布隆过滤器无法完成删除操作。如果非要删除可以考虑计数布隆过滤器。在前文中我们充分了解了布隆过滤器的作用、组成、添加元素流程、查询元素流程以及特点。那么如何在具体的案例中使用布隆过滤器在此我们将以黑名单的实现这个典型例子来讲解。假如在发送业务通知短信前要判断手机号码是否在黑名单1000w条号码具体的实现思路如下第一步初始化预热在服务启动时将数据库中现有的1000w黑名单手机号需要全部导入布隆过滤器中。第二步拦截阶段——本文着重提到的核心逻辑当短信请求到达时先查询布隆过滤器——利用需查询的号码哈希计算后的下标位置进行比对。 情况A布隆返回不存在可以直接放行发送短信。因为“不存在”是绝对准确的。情况B布隆返回可能存在为了避免误判导致“未存在于黑名单中的用户”被拦截不能直接拒绝。此时需要回源进行二次确认。第三步最后的确认如果数据库查询结果为“不在黑名单”则正常发送对布隆过滤器误判的修正。如果数据库查询结果为“在黑名单”则拦截发送。