一、 什么是布隆过滤器作用、组成、添加元素流程、查询元素的流程、特点误判、不支持删除布隆过滤器Bloom Filter是由Burton Howard Bloom于1970年提出的。我们可以把它看作由位数组和一组哈希函数组成的数据结构,它占用空间少并且效率更高但是缺点是其返回的结果是概率性的而不是非常准确的。理论情况下添加到集合中的元素越多误报的可能性就越大。并且存放在布隆过滤器的数据不容易删除。换句话说是一种用来检查元素是否存在于指定集合中的数据结构这种数据结构是高效且性能很好的但缺点是具有一定的错误识别率和删除难度。并且理论情况下添加到集合中的元素越多误报的可能性就越大。组成位数组多个哈希函数组成添加元素流程首先对需要存入的元素进行不同的哈希函数运算生成不同的哈希结果然后将每一个哈希值对应到位数组的位置并且将对应的位置下标从0改成1。查询元素的流程对于待查询元素使用和添加元素完全相同的个数哈希函数进行计算算出若干个哈希值映射得到位数组上对应位置的下标进行比对只要有任意一个位置的值为 0说明该元素一定没有存入布隆过滤器如果所有的值均为 1则无法确定元素一定存在只能判定元素大概率存在因为存在误报可能性。特点1、误判性2、不支持删除二、布隆过滤器的优点和缺点有哪些优点1、存储空间高效仅使用 bit 数组存储标记不存放原始数据同等数据量下内存远小于 List、Set、Map2、读写性能高插入与查询只需要多次哈希运算效率很高3、数据本身不存储增强安全性没有保存原始元素无法直接从过滤器中还原数据缺点1、存在误报问题有可能把不存在的元素判定为存在元素数量越多误报概率越高2、难以删除元素多个元素会共享比特位直接置 0 会影响其他元素判断3、无法获得实际元素三、 发送业务通知短信前要判断手机号码是否在黑名单1000w实现思路针对 1000 万级别的手机号码黑名单判断场景使用布隆过滤器Bloom Filter来实现具体实现思路如下1、数据初始化把数据库中的1000万个黑名单手机号全部取出依次通过哈希函数将所有黑名单手机号都添加到布隆过滤器中。2、业务收到发送请求先用手机号查询布隆过滤器使用相同哈希函数进行查询如果过滤器判定不存在则手机号不在黑名单允许发送短信如果过滤器判定存在则有可能在黑名单里因为布隆过滤器存在误判的可能所以需要进行二次查询来确定是否真的在黑名单里。
