可以解决什么问题？

存在50亿个电话号码（或者ip、黑名单、url），给10万个电话号码，如何快速准确判断这些号码是否存在？

基本概念

布隆过滤器是一个很长的二进制数组+一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。

能高效的插入和查询，占用空间少，返回的结果是不确定性的。一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在时则一定不存在。 布隆过滤器可以添加元素但是不能删除元素，因为删掉元素会导致误判率增加。误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判。

使用场景

1、主要是解决缓存穿透问题

• 把已存在的数据的key存在布隆过滤器中，相当于在redis前面挡了一层布隆过滤器。
• 当有新的请求时，先到布隆过滤器中查询是否已经存在；
• 如果布隆过滤器中不存在该数据则直接返回；
• 如果布隆过滤器中已存在，才去查询缓存redis，如果redis里没有查到则到MySQL数据库中查询。

2、黑名单校验

原理

初始化：创建一个位数组（通常是一个二进制数组）并将所有位初始化为 0。位数组的长度（或大小）取决于预期要存储的元素数量和所能容忍的误判率。

添加key时：使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数会得到一个不同的位置，将这几个位置都置1就完成了add操作。

这也是布隆过滤器为什么不能删除，因为无法保证hash之后的位置没有别的key在使用（难免会出现hash冲突，多个key共用某些hash位置）。如果删除了，那么别的key也会受影响。这样会导致误判率增加。

查询key时：向布隆过滤器查询某个key是否存在时，先把这个key通过相同的多个hash函数进行运算，查看对应的位置是否都为1，只要有一个位置是0，则表明不存在，如果这几个位置都为1，则说明可能存在。（因为这些位置的1可能是其他的key导致的）

使用布隆过滤器时，最好不要让实际元素数量远大于初始化数量。当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进行。

优化

虽然布隆过滤器具有高效的插入和查询操作，但由于其设计原理的限制，存在一定的误判率。以下是一些方法可以降低布隆过滤器的误判率：

• 增加位数组的大小：通过增加位数组的大小，可以提供更多的位来表示元素的存在情况，从而降低误判率。较大的位数组可以提供更多的空间来存储哈希值，减少不同元素之间的冲突。

• 使用更多的哈希函数：布隆过滤器使用多个哈希函数来生成多个哈希值，用于设置位数组中的位。增加哈希函数的数量可以增加布隆过滤器的准确性，并降低误判率。但需要注意的是，增加哈希函数的数量也会增加计算的开销。

• 组合多个布隆过滤器：通过使用多个独立的布隆过滤器并进行逻辑组合，可以降低误判率。例如，可以使用多个布隆过滤器，每个过滤器使用不同的哈希函数集合或位数组大小。查询时，只有当所有布隆过滤器都返回存在时，才判断元素存在于集合中，从而降低误判率。

• 结合其他数据结构：将布隆过滤器与其他数据结构结合使用，可以进一步降低误判率。例如，可以将布隆过滤器作为预过滤器，将可能存在的元素进一步验证。对于预测为存在的元素，再使用精确的数据结构进行验证，以确保准确性。

• 动态调整参数：根据实际使用情况和误判率要求，动态调整布隆过滤器的参数。例如，可以根据系统的负载和数据量变化来动态调整位数组大小、哈希函数数量等参数，以达到最优的误判率和性能平衡。

当然降低误判率通常会带来一些额外的开销，例如更大的位数组、更多的哈希函数或组合多个过滤器。因此，在选择具体的降低误判率方法时，需要综合考虑应用的实际需求、系统的资源和性能要求。