布隆过滤器（Bloom Filter）

1. 什么是布隆过滤器布隆过滤器是 1970 年由 Burton Howard Bloom 提出的。它用来判断一个元素是否属于某个集合。1.1 作用快速拦截一定不存在的请求检查元素是否存在指定集合中例如判断一个数字是否存在数字集合中5亿个数缓存穿透防护、爬虫 URL 去重、垃圾邮的过滤、黑名单拦截等。1.2 组成布隆过滤器由以下两部分组成位数组位数组通常初始化为0多个哈希函数哈希函数用于将元素映射到位数组中的位置。1.3 添加元素的流程向布隆过滤器中添加一个元素时执行以下步骤使用 多个哈希函数分别对该元素计算哈希值得到 多个位数组下标。将位数组中这些下标对应的位全部置为 1。例如添加元素 App 时6 个哈希函数分别计算出下标 2、5、7、9、11、13则将位数组的第 2、5、7 、9、11、13位设为 1。1.4 查询元素的流程当查询一个元素是否在集合中时使用相同的多个哈希函数对该元素计算哈希值得到多个位数组下标。检查位数组中这些个下标对应的位如果任意一位为 0则该元素一定不在集合中。如果所有位都为 1则该元素可能在集合中存在误判可能。1.5 特点误判率布隆过滤器存在误判即可能将不在集合中的元素误判为在集合中。误判率与位数组长度 、哈希函数个数以及已添加元素数量有关。通过合理选择位数组长度和哈希函数数量可以将误判率控制在可接受范围内。不支持删除元素布隆过滤器无法安全地删除元素。因为多个元素可能映射到同一位直接将该位清零会导致其他元素被误判为不存在。2. 布隆过滤器的优点和缺点2.1 优点空间效率极高布隆过滤器只需要一个位数组占用内存非常少只存布特位不存原始数据。查询和插入速度快添加和查询操作都只涉及 k 次哈希计算和位数组访问时间复杂度为 O(k)与集合大小无关。安全性好布隆过滤器不存储元素本身只存储哈希映射后的位信息因此无法从位数组中还原原始数据适合保护敏感数据。易于并行化多个哈希函数可以并行计算位数组的读写操作也可以并发执行。2.2 缺点存在误判率无法做到 100% 准确可能将不在集合中的元素误判为存在。误判率无法降为 0只能通过增加位数组长度来降低。无法删除元素标准布隆过滤器不支持删除操作。无法获取元素本身布隆过滤器只能回答是否存在无法像哈希表那样返回元素的值或关联数据。误判率随元素数量增加而上升当已添加元素数量接近或超过设计容量时误判率会急剧上升需要提前规划好容量。3. 黑名单场景实战判断手机号码是否在黑名单3.1 场景描述发送业务通知短信前需要判断手机号码是否在 1000 万条黑名单中。布隆过滤器非常适合这种大量数据、允许少量误判、追求高性能的场景。3.2 实现思路整体方案采用布隆过滤器 数据库的双层架构初始化阶段从数据库中读取全部 1000 万条黑名单手机号码逐个添加到布隆过滤器中。布隆过滤器加载到内存中常驻。查询阶段发送短信前先用布隆过滤器判断手机号码如果布隆过滤器返回不存在某位为 0则直接放行无需查询数据库。如果布隆过滤器返回可能存在所有位为 1再回源数据库做精确查询确认是否真的在黑名单中。