浅谈布隆过滤器（Bloom Filter）

什么是布隆过滤器

简介

布隆过滤器是一个很长的二进制向量和一系列随机映射函数。可以用于检索一个元素是否在一个集合中。
布隆过滤器其内部维护了一个全为 0 的 bit 数组，需要说明的是，布隆过滤器有一个误判的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间多少。

布隆过滤器的优点

1. 时间复杂度低，增加和查询元素的时间复杂为$O(N)$，（N为哈希函数的个数，通常情况比较小）。
2. 保密性强，布隆过滤器不存储元素本身。
3. 存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）。

布隆过滤器的缺点

1. 有一定的误判率，但是可以通过调整参数来降低。
2. 无法获取元素本身。
3. 无法删除元素。

布隆过滤器的原理

数据结构

以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。

• 一个大型位数组（二进制数组）：
  

• 多个无偏hash函数：无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1。

1. 通过k个无偏hash函数计算得到k个hash值。
2. 依次取模数组长度，得到数组索引。
3. 将计算得到的数组索引下标位置数据修改为1。

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1。

如下图所示：

查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：

1. 通过k个无偏hash函数计算得到k个hash值。
2. 依次取模数组长度，得到数组索引。
3. 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

使用场景

数据去重

• 场景描述： 在一些需要对大量数据进行去重的场景，例如用户提交表单、数据同步等，布隆过滤器可以迅速判断某个数据是否已存在，避免重复插入。
• 应用实例： 在用户提交表单时，使用布隆过滤器判断该用户是否已经提交过相同的数据，从而防止重复提交。

缓存穿透问题的解决

• 场景描述：当缓存中不存在某个数据，而用户频繁查询该数据时，可能导致缓存穿透问题。布隆过滤器可以在缓存层之前迅速过滤掉不存在的数据，减轻数据库的压力。
• 应用实例： 在缓存中存储热门商品的ID列表，并使用布隆过滤器判断某个商品ID是否存在于列表中，从而决定是否查询数据库获取数据。

项目实战

springboot集成

使用springboot的redisson创建布隆过滤器，由redis的bitset（位图）作为存储结构。

application.yml配置redis

spring:
  application:
    name: bloom
  redis:
    host: 127.0.0.1
    port: 6379

创建布隆过滤器 Bean

@Configuration
public class BloomFilter {

    @Autowired
    private RedissonClient redissonClient;

    private RBloomFilter<String> bloomFilter;

    @PostConstruct
    public void initBloomFilter() {
        bloomFilter = redissonClient.getBloomFilter("userIdFilter");
        // 初始化参数：预期元素数量为100000，误判率为1%
        bloomFilter.tryInit(100000L, 0.01);
    }

    public void addUserId(String userId) {
        // 预加载数据
        bloomFilter.add(userId);
    }

    public boolean checkUserId(String userId) {
        return bloomFilter.contains(userId);
    }
}

使用布隆过滤器

@Service
@Slf4j
public class UserService {

    @Autowired
    private BloomFilter bloomFilter;

    // 代替数据库存到缓存
    private List<User> users = new ArrayList<>();

    public User selectUserId(Integer userId) {
        if (bloomFilter.checkUserId(String.valueOf(userId))) {
            User user = getUser(userId);
            log.info("user id: {} is selected. User: {}", userId, user);
            return user;
        }
        log.info("user id: {} not found", userId);
        return null;
    }

    public void addUsers() {
        String name = "peter";
        Integer age = 20;
        for (int i = 1; i <= 100; i++) {
            users.add(new User(i, name + i, age));
            bloomFilter.addUserId(String.valueOf(i));
        }
    }

    public User getUser(Integer userId) {
        for (User user : users) {
            if (user.getId().equals(userId)) {
                return user;
            }
        }
        return null;
    }
}

测试代码

@SpringBootTest
class BloomApplicationTests {

    @Autowired
    private UserService userService;

    @Test
    void testBloomFilter() {
        userService.addUsers();
        assert userService.selectUserId(10) != null;
        assert userService.selectUserId(100) != null;
        assert userService.selectUserId(200) == null;
        assert userService.selectUserId(300) == null;
    }

}

执行日志

2025-03-23 12:27:16.275  INFO 15908 --- [    Test worker] com.example.bloom.service.UserService    : user id: 10 is selected. User: User(id=10, name=peter10, age=20)
2025-03-23 12:27:16.280  INFO 15908 --- [    Test worker] com.example.bloom.service.UserService    : user id: 100 is selected. User: User(id=100, name=peter100, age=20)
2025-03-23 12:27:16.282  INFO 15908 --- [    Test worker] com.example.bloom.service.UserService    : user id: 200 not found
2025-03-23 12:27:16.283  INFO 15908 --- [    Test worker] com.example.bloom.service.UserService    : user id: 300 not found

redis存储结构

查询redis key

127.0.0.1:6379> keys "*userIdFilter*"
1) "{userIdFilter}:config"
2) "userIdFilter"

查询key类型

127.0.0.1:6379> type "{userIdFilter}:config"
hash
127.0.0.1:6379> type "userIdFilter"
string

遍历hash

127.0.0.1:6379> HGETALL "{userIdFilter}:config"
1) "size"
2) "958505"
3) "hashIterations"
4) "7"
5) "expectedInsertions"
6) "100000"
7) "falseProbability"
8) "0.01"

hash字段含义

expectedInsertions = 100000      # 预期处理10万用户ID
falseProbability = 0.01         # 允许1%的误判率
hashIterations = 7               # 自动计算出的哈希函数数量
size = 958505                   # 所需位数组长度约95.8万位（约117KB）

查看bitmap置1数

127.0.0.1:6379> BITCOUNT userIdFilter
(integer) 700

我们存了100个userId，7个hash函数给我们置了700个1。

查看bitmap存储长度

127.0.0.1:6379> strlen userIdFilter
(integer) 119734

使用了119734个字节，119734 * 8 = 957872位，与size = 958505接近。

• 个人小游戏