前言

在面试过程中，经常会被问到：布隆过滤器有什么缺点？它一般用于哪些场景？布隆过滤器是否支持删除？

• 一个经典场景引出布隆过滤器
• 布隆过滤器原理解析
• 布隆过滤器的优点和缺点
• 布隆过滤器是否支持删除
• 布隆过滤器的经典使用场景
• 布隆过滤器一个简单使用demo

1. 一个经典场景：缓存穿透

日常开发中，一个常见的缓存使用方式是酱紫的：

读请求来了，先查下缓存，缓存有值命中，就直接返回；缓存没命中，就去查数据库，然后把数据库的值更新到缓存，再返回。

graph TD
开始 --> 读请求
读请求 --> 查询缓存
查询缓存 --> 缓存是否命中?
缓存是否命中? ==否==> 查询数据库
查询数据库 --> 数据库中是否存在?
数据库中是否存在? ==是==> 数据保存到缓存
数据保存到缓存 ==否==> 返回响应
返回响应 --> 结束
数据库中是否存在? --> 返回响应
缓存是否命中? ==是==> 返回响应

现在可能存在这么一种情况，就是，我们要查的商品，既不在缓存里，又不在数据库里。于是每次这种读请求来，都会打到数据库，造成数据库压力极大。其实这就是缓存穿透的场景。

缓存穿透 ：指查询一个一定不存在的数据，由于缓存是不命中时需要从数据库查询，查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库去查询，进而给数据库带来压力。

2、布隆过滤器原理解析

什么是布隆过滤器？

布隆过滤器是一种空间效率高和时间效率高的概率型数据结构，用于判断某个元素是否在一个集合中。它通过多个哈希函数将元素映射到一个位数组中，虽然能快速判断元素是否存在，但有一定的误判率，即可能会误认为元素存在，但不会漏掉实际存在的元素。

简单点，你可以认为，布隆过滤器确实是一个很长的二进制向量（位数组）和一系列哈希函数的组合~

布隆过滤器的原理很简单：

当一个元素被添加到集合中时，它会通过m个哈希函数映射到位数组中的m个位置，并将这些位置的值设置为 1。在检查元素是否在集合中时，检查这些位置是否全为 1。如果其中有任何一个位置为 0，则该元素一定不在集合中；如果所有位置均为 1，则该元素可能在集合中。

举个例子:

布隆过滤器

假设现在有3个哈希函数，和一个8位的bit数组。元素a和b，都经过三次哈希函数生成三个哈希值，并映射到位数组的不同的位置，并设置为1。元素a映射的位置是（0,3,7），元素b映射的位置是（2,5,7）.

如果一个元素c过来，我们检查它映射后的三个位置是否全是1，就可以判断元素C是否在当前集合中了。

其实我们可以发现，元素a和元素b映射的位置7都是1，也就是说，位置是可能重叠的。假设当前集合已经有a和b了，但是呢一个元素c过来，它映射的位置为（0,2,7），这时候，它的所有位置都是1，布隆过滤器是认为它可能在集合中，但是我们看到元素c是不在当前集合中的。

也是就说，布隆过滤器是可能存在误判的，通俗点说就是假阳性。

3、 布隆过滤器的优点和缺点

布隆过滤器的缺点，其实就是，存在一定误判。

要降低误判率的话，我们可以：

mindmap
如何降低布隆过滤器误判
    1.增加位数组的大小
    2.增加哈希函数的数量
    3.使用分级布隆过滤器

• 增加位数组的大小：增大位数组的长度可以减少每个位的填充率，从而降低假阳性率。较大的位数组可以容纳更多的元素，并且哈希值的碰撞几率减少。

• 增加哈希函数的数量：使用更多的哈希函数可以进一步分散哈希映射，降低假阳性率。

• 使用分级布隆过滤器：在布隆过滤器前使用一个较小的布隆过滤器作为初步过滤器，只有在初步过滤器确认元素可能存在时，才使用主要布隆过滤器，这可以减少对主要布隆过滤器的查询次数。

而布隆过滤器的优点也很明确，它的空间效率和查询效率，相对与其他一般算法，都有明显优势。正所谓鱼和熊掌，不可兼得，但是它居然不一样，空间和时间效率都不错！

确切地说，布隆过滤器的高效和低空间复杂度归功于其使用的哈希函数和位数组。它利用多个哈希函数将数据映射到一个固定大小的位数组中，减少了需要存储的数据量，从而降低了空间复杂度。由于它是基于位操作的，查找操作也非常快，这使得它在处理大量数据时表现出高效性

4、布隆过滤器是否支持删除

标准的布隆过滤器不支持删除操作。

这是因为布隆过滤器通过将多个哈希函数映射的位数组位置设置为 1 来标记元素的存在，但无法撤销这些操作。

即使有些位是由于删除操作而需要重置为 0，这可能会影响其他元素的检测

5、布隆过滤器的经典使用场景

mindmap
不聋过滤器经典使用场景
    1.缓存穿透保护
    2.恶意网址检测
    3.防止消息重复消费

5.1 缓存穿透

布隆过滤器，常常跟我们讨论的缓存穿透出现。它是最经典的使用场景。

缓存穿透保护：在分布式缓存系统中，布隆过滤器可以用来防止缓存穿透。通过在缓存前面加一个布隆过滤器，可以有效地阻止不存在的数据请求直接到达后端数据库，从而减少数据库负载和提高系统性能。

5.2 恶意网址检测

布隆过滤器可以用于网络安全中，例如检测恶意网址。通过将已知的恶意网址存储在布隆过滤器中，可以快速判断一个网址是否可能是恶意的。

5.3 防止消息重复消费

防止消息重复消费：布隆过滤器还可以用于防止MQ消息重复消费。比如说，我们在发送消息时可以对每个消息设置唯一的key，然后呢，在消费者消费处理时，利用布隆过滤器对消息的key检索。如果不存在则进行消费，然后插入布隆过滤器，如果存在则说明消息已经消费过。

但是呢，由于布隆过滤的假阳性，一般要求集合数据库存储已处理消息ID，来进一步减少重复消费的风险。

在消息量大、内存空间有限的情况下，使用布隆过滤器是个很不错的选择。

6、布隆过滤器一个简单使用demo

基于查商品详情的例子，加入布隆过滤器，伪代码如下：

public class GoodsService {

// 初始化布隆过滤器，假设商品ID不会超过100万，误判率为0.01
private BloomFilter<Long> bloomFilter =
BloomFilter.create(Funnels.longFunnel(), 1000000, 0.01);

public Goods queryGoodsById(Long goodsId) {
    // 先从缓存中查询商品
    Goods goods = queryGoodsFromCache(goodsId);
    if (goods != null) {
        return goods;
    }

    // 缓存中没有时，检查布隆过滤器
    if (!bloomFilter.mightContain(goodsId)) {
        // 如果布隆过滤器认为商品ID不存在，直接返回null，避免查询数据库
        return null;
    }

    // 从数据库查询商品
    goods = queryGoodsFromDB(goodsId);
    if (goods != null) {
        // 如果数据库中存在商品，将商品保存到缓存中
        saveGoodsToCache(goodsId, goods);
    } else {
        // 如果数据库中也没有商品，则将ID添加到布隆过滤器中，防止以后再次查询
        bloomFilter.put(goodsId);
    }

    // 返回商品信息
    return goods;
}

在这里呢，需要初始化布隆过滤器，即预加载布隆过滤器，将数据库中的商品ID加入布隆过滤器。如果有新增商品过来，也需要更新到布隆过滤器。

 private void initializeBloomFilter() {
    // 假设从数据库中获取所有商品的ID列表
    List<Long> allGoodsIds = loadAllGoodsIdsFromDB();
    for (Long goodsId : allGoodsIds) {
        bloomFilter.put(goodsId);
    }
}

public void addNewGoods(Long goodsId, Goods goods) {
    // 将新商品添加到数据库
    saveGoodsToDB(goodsId, goods);

    // 更新缓存和布隆过滤器
    saveGoodsToCache(goodsId, goods);
    bloomFilter.put(goodsId);  // 确保新的商品ID被添加到布隆过滤器
}

## 最后
大家在日常开发中，如果遇到缓存穿透的场景。我觉得不用上来就加上布隆过滤器的，除非请求量很大那种。否则，你查询数据库查不到的话，更新一个不存在的标记到缓存就可以啦。