Bloom Filter 是一个二进制bit数组，初始为 0

用于快速查找一个集合中是否存在某个元素。尤其是大数据量中快速查找判断是否存在的问题。

布隆过滤器能记录一个元素可能存在或肯定不存在。它非常节省内存，但有一定概率会给出错误的“存在”结果，即可能出现哈希冲突，通常会使用多个不同哈希函数，对同一个值得出一组哈希值，并将这组值写入Bloom数组中，这样来降低哈希冲突的概率，如何预测误报的概率？

比如在缓存穿透场景中，当大量不存在key请求攻击时，可以使用Redis的Bloom Filter来解决。

Bloom Filter 采用位存储数据结构，节省存储空间

使用 Redisson中的布隆过滤器

使用 Redisson 创建布隆过滤器，插入元素，并检查某个元素是否存在。

在 pom.xml 文件中添加 Redisson 依赖：

1
2
3
4
5
6
7

<dependencies>
    <dependency>
        <groupId>org.redisson</groupId>
        <artifactId>redisson</artifactId>
        <version>3.16.1</version> <!-- 使用最新版本 -->
    </dependency>
</dependencies>

编写代码来创建布隆过滤器，插入元素，并检查元素：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilterExample {

    public static void main(String[] args) {
        // 配置 Redisson 客户端
        Config config = new Config();
        config.useSingleServer()
              .setAddress("redis://127.0.0.1:6379");

        // 创建 Redisson 客户端实例
        RedissonClient redisson = Redisson.create(config);

        // 创建布隆过滤器
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myBloomFilter");

        // 初始化布隆过滤器，设置预期插入的元素数量和误报率
        bloomFilter.tryInit(10000L, 0.03);

        // 插入元素
        bloomFilter.add("key1");
        bloomFilter.add("key2");

        // 查找元素
        boolean mightContainYi = bloomFilter.contains("key1");
        System.out.println("布隆过滤器中可能包含'key1'：" + mightContainYi);

        // 关闭 Redisson 客户端
        redisson.shutdown();
    }
}

布隆过滤器的Python实现示例

参考Bloom Filter !

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import mmh3  # MurmurHash 3，常用于布隆过滤器
import math

class BloomFilter:
    def __init__(self, m, k):
        self.m = m  # 布隆过滤器的大小（位数组的长度）
        self.k = k  # 哈希函数的数量
        self.n = 0  # 插入的元素数量
        self.bloomFilter = [0] * self.m  # 初始化位数组为0
        
    def getBitArrayIndices(self, item):
        """
        计算 item 的哈希值并返回需要设置的位数组索引列表
        """
        indexList = []
        for i in range(1, self.k + 1):
            indexList.append((hash(item) + i * mmh3.hash(item)) % self.m)
        return indexList
        
    def add(self, item):
        """
        插入一个元素到布隆过滤器
        """
        for i in self.getBitArrayIndices(item):
            self.bloomFilter[i] = 1
        self.n += 1
    
    def contains(self, key):
        """
        检查元素是否在布隆过滤器中
        """
        for i in self.getBitArrayIndices(key):
            if self.bloomFilter[i] != 1:
                return False
        return True
        
    def generateStats(self):
        """
        计算布隆过滤器的统计信息，比如错误率
        """
        n = float(self.n)
        m = float(self.m)
        k = float(self.k)
        probability_fp = math.pow((1.0 - math.exp(-(k*n)/m)), k)

        print("元素数量: ", n)
        print("布隆过滤器大小: ", m)
        print("哈希函数数量: ", k)
        print("假阳性概率: ", probability_fp)
        print("假阳性率: ", probability_fp * 100.0, "%")

参考