布隆过滤器

Updated on in 程序人生 with 0 views and 0 comments

一、定义

布隆过滤器（Bloom Filter）是一种概率型数据结构，用于判断一个元素是否在一个集合中。它由 Burton Howard Bloom 在 1970 年提出。布隆过滤器的特点是空间效率高和查询速度快，但是有一定的误判率，并且一旦添加元素后无法删除。

二、布隆过滤器的工作原理

2.1 初始化

创建一个位数组（bit array），长度为 m，所有位都初始化为 0

image.png

2.2 插入元素

对于每一个要加入集合的元素，使用 k 个不同的哈希函数对该元素进行哈希，得到 k 个不同的索引位置。将这些位置上的位设置为 1

image.png

2.3 查询元素

当查询一个元素是否存在于集合中时，同样用上述 k 个哈希函数对元素进行哈希，检查所得的 k 个位置上的值是否全都是 1。如果全是 1，则认为该元素可能存在于集合中；如果有一个位置是 0，则可以确定该元素不存在于集合中

三、特点

  • 优点 ：
    • 空间效率高：相比于其它数据结构如哈希表或二叉树，布隆过滤器占用的空间更小。
    • 查询速度快：由于只需要计算几个哈希函数，所以查询速度非常快。
    • 可以节省大量的存储资源，尤其是在处理大数据量的情况下。
  • 缺点 ：
    • 存在误报（False Positive）的可能性：即有可能将不在集合中的元素错误地判断为在集合中。
    • 无法支持从集合中删除元素：一旦某个元素被加入到布隆过滤器中，就不能被删除，因为这可能会影响到其它元素的判断。

2.4 位数组大小与哈希函数量

image.png

四、误报

如图所示，id为3的数据不存在但是计算过后在数组下标中结果都为1

image.png

五、代码实例

参考redisson实现的布隆过滤器

        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson</artifactId>
            <version>3.16.2</version>
        </dependency>

public void testRedis(){
        // 创建 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("phoneNumber");

        // 初始化布隆过滤器，设置期望的元素数量和期望的误报率
        // 这里假设我们期望存储大约 10 万个元素，且希望误报率为 1%
        // 向布隆过滤器中添加元素
        long phoneNum = 100000L;
        double falseProbability = 0.01;
        bloomFilter.tryInit(phoneNum, falseProbability);
        for(int i=0;i<phoneNum;i++){
            bloomFilter.add(String.valueOf(i));
        }

        // 查询10万以后的数字是否存在
        long totalNum = phoneNum+10000;
        long existPhoneNum = 0;
        for(long i=phoneNum;i<totalNum;i++){
            boolean mightContain = bloomFilter.contains(String.valueOf(i));
            if(mightContain){existPhoneNum++;}
        }

        // 检查元素是否可能存在于布隆过滤器中

        System.out.println(existPhoneNum+"个号码重复，重复率为"+ BigDecimal.valueOf(existPhoneNum).divide(BigDecimal.valueOf(phoneNum)).doubleValue());

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

参考

https://www.bilibili.com/video/BV1yT411H7YK?p=7

标题：布隆过滤器
作者：wenyl
地址：http://www.wenyoulong.com/articles/2024/09/25/1727245477321.html

↑ ↓