布隆过滤器原理、特性及短信黑名单过滤业务实现方案

一、 什么是布隆过滤器？（作用、组成、添加元素流程、查询元素的流程、特点（误判、不支持删除）

布隆过滤器（Bloom Filter）是由Burton Howard Bloom于1970年提出的。我们可以把它看作由位数组和一组哈希函数组成的数据结构,它占用空间少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

换句话说是一种用来检查元素是否存在于指定集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。

组成：位数组+多个哈希函数组成

添加元素流程：首先对需要存入的元素进行不同的哈希函数运算，生成不同的哈希结果，然后将每一个哈希值对应到位数组的位置，并且将对应的位置下标从0改成1。

查询元素的流程：对于待查询元素，使用和添加元素完全相同的个数哈希函数进行计算，算出若干个哈希值，映射得到位数组上对应位置的下标进行比对，只要有任意一个位置的值为 0，说明该元素一定没有存入布隆过滤器；如果所有的值均为 1，则无法确定元素一定存在，只能判定元素大概率存在，因为存在误报可能性。

特点：1、误判性

2、不支持删除

二、布隆过滤器的优点和缺点有哪些？

优点：

1、存储空间高效：仅使用 bit 数组存储标记，不存放原始数据，同等数据量下内存远小于 List、Set、Map；

2、读写性能高：插入与查询只需要多次哈希运算，效率很高；

3、数据本身不存储，增强安全性：没有保存原始元素，无法直接从过滤器中还原数据；

缺点：

1、存在误报问题：有可能把不存在的元素判定为存在，元素数量越多，误报概率越高；

2、难以删除元素：多个元素会共享比特位，直接置 0 会影响其他元素判断；

3、无法获得实际元素；

三、 发送业务通知短信前，要判断手机号码是否在黑名单（1000w），实现思路

针对 1000 万级别的手机号码黑名单判断场景，使用布隆过滤器（Bloom Filter）来实现，具体实现思路如下：

1、数据初始化

把数据库中的1000万个黑名单手机号全部取出，依次通过哈希函数将所有黑名单手机号都添加到布隆过滤器中。

2、业务收到发送请求，先用手机号查询布隆过滤器：

使用相同哈希函数，进行查询；

如果过滤器判定不存在：则手机号不在黑名单，允许发送短信；

如果过滤器判定存在：则有可能在黑名单里，因为布隆过滤器存在误判的可能，所以需要进行二次查询来确定是否真的在黑名单里。