布隆过滤器

布隆过滤器主要是用于检查在于不在的一个东西。布隆过滤器判断在，可能不在。判断不在，一定不在。所以也有一定的风险。而且不能删去元素，除非重新做一遍。

为解决单个布隆过滤器过大、查询压力集中，以及扩容不方便的问题，可以将数据分片，分别存入多个布隆过滤器。只要各分片的位数与元素数量之比保持不变，理论误判率就基本不变。

布隆过滤器的理论误判率近似为：

p \approx \left(1-e^{-kn/m}\right)^k

其中， $m$ 是位数组的总位数， $n$ 是插入的元素数量， $k$ 是哈希函数数量。最优哈希函数数量约为：

k_{\mathrm{opt}}=\frac{m}{n}\ln 2

假设原过滤器使用 1000 万位，存储 100 万个元素，则每个元素对应的位数为：

\frac{m}{n}=\frac{10^7}{10^6}=10

将其均匀拆成两个分片后，每个分片使用 500 万位，存储约 50 万个元素：

\frac{m_i}{n_i} =\frac{5\times10^6}{5\times10^5} =10

拆分前后的 $m/n$ 相同，因此最优哈希函数数量不变；在哈希均匀、各分片使用相同 $k$ 的条件下，理论误判率也基本不变。

这种拆分本质上是数据分片（Sharding）。通过 Hash(Key) % N 路由，每个 Key 只写入和查询一个过滤器。将分片分布到不同节点，可以分散内存占用和查询压力。

实际分片未必严格均匀，需要监控各分片的元素数量。如果某个分片存入过多元素，使其 $m_i/n_i$ 降低，该分片的误判率就会上升。

以下是 redisson 实现代码：

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

@Service
public class BloomFilterService {

    @Autowired
    private RedissonClient redissonClient;

    public void createAndUseBloomFilter() {
        // 创建布隆过滤器
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("myBloomFilter");

        // 初始化布隆过滤器，容量为 1000000，误差率为 0.03（3%）
        bloomFilter.tryInit(1000000, 0.03);

        // 添加元素到布隆过滤器
        bloomFilter.add("apple");
        bloomFilter.add("banana");

        // 检查元素是否存在
        boolean containsApple = bloomFilter.contains("apple"); // 返回 true
        boolean containsOrange = bloomFilter.contains("orange"); // 返回 false (有一定的误报概率)

        System.out.println("Contains apple: " + containsApple);
        System.out.println("Contains orange: " + containsOrange);
    }
}

tryInit(capacity, errorRate)：
capacity：布隆过滤器的容量，表示预期插入的元素数量。
errorRate：误差率，即假阳性概率。误差率越小，布隆过滤器的准确性越高，但需要更多的内存。
add(element)：将一个元素添加到布隆过滤器中。
contains(element)：检查元素是否可能存在于布隆过滤器中。由于布隆过滤器的特性，存在一定的误报概率。

如何删掉布隆过滤器：

bloomFilter.delete();

Redisson 提供的 RBloomFilter 是一个简单而强大的布隆过滤器实现，适用于许多场景。例如，常用于：

缓存穿透：在数据库查询之前，使用布隆过滤器先过滤掉不存在的数据，减少对数据库的压力。
去重：在处理大数据时，用布隆过滤器来去除重复元素，节省内存。