JAVA：利用布隆过滤器(BloomFilter)实现高效的去重和判重

蔚落 2024-04-20 12:14 22阅读 0赞

#### 1、简述 ####

布隆过滤器 (Bloom Filter)是一种空间效率高、时间效率低的数据结构，用于判断一个元素是否存在于一个集合中。它基于一个位数组和多个哈希函数实现，当一个元素被添加到集合中时，会将其哈希到位数组中的多个位置，并将对应的位设置为1；当判断一个元素是否在集合中时，只需检查位数组中的对应位置是否为1即可。

哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的 1/8 或 1/4 的空间复杂度就能完成同样的问题。

布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，误报率越大，但是 漏报是不可能的。

#### 2、原理 ####

BloomFilter 的算法是，首先分配一块内存空间做 bit 数组，数组的 bit 位初始值全部设为 0。

加入元素时，采用 k 个相互独立的 Hash 函数计算，然后将元素 Hash 映射的 K 个位置全部设置为 1。

检测 key 是否存在，仍然用这 k 个 Hash 函数计算出 k 个位置，如果位置全部为 1，则表明 key 存在，否则不存在。  
![在这里插入图片描述][3ea4cf45920a420887a08dc075dae000.png]

#### 3、代码实现 ####

##### 3.1 Jedis #####

Java中可以通过Redis的位图数据结构来实现Bloom Filter。Redis提供了Jedis等客户端库，可以方便地与Redis进行交互。

首先，确保在Maven中引入Jedis的依赖：

<dependency>
        <groupId>redis.clients</groupId>
        <artifactId>jedis</artifactId>
        <version>3.6.3</version>
    </dependency>

下面是一个简单的Java示例，演示了如何利用Redis实现Bloom Filter：

package com.xhl.lk.auth2.modules.admin.demo;
    
    import redis.clients.jedis.Jedis;
    
    public class BloomFilterExample {
    
        private Jedis jedis;
    
        public BloomFilterExample() {
            jedis = new Jedis("192.168.245.181",6379);
            jedis.auth("123456");
        }
    
        public void add(String key, String value) {
            jedis.setbit(key, Long.parseLong(value), true);
        }
    
        public boolean contains(String key, String value) {
            return jedis.getbit(key, Long.parseLong(value));
        }
    
        public static void main(String[] args) {
            BloomFilterExample example = new BloomFilterExample();
            example.add("bloom-filter", "1");
            example.add("bloom-filter", "2");
    
            System.out.println(example.contains("bloom-filter", "1")); // true
            System.out.println(example.contains("bloom-filter", "2")); // true
            System.out.println(example.contains("bloom-filter", "3")); // false
        }
    }

在这个示例中，我们创建了一个名为bloom-filter的位图，然后添加了两个元素1和2。最后，我们分别判断了元素1、2和3是否在集合中，结果分别为true、true和false。

##### 3.2 Guava #####

Guava是Google开发的Java库，其中包含了许多实用的工具类和数据结构。其中也包含了Bloom Filter的实现。下面是一个示例代码，演示了如何使用Guava实现Bloom Filter：

首先，确保在Maven中引入Guava的依赖：

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>31.0.1-jre</version>
    </dependency>

然后，可以使用以下代码来创建和使用Guava的Bloom Filter：

package com.xhl.lk.auth2.modules.admin.demo;
    
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    import static com.google.common.base.Charsets.UTF_8;
    
    public class GuavaBloomFilterExample {
    
        public static void main(String[] args) {
            // 创建Bloom Filter，预计容量为10000，误判率为0.01
            BloomFilter<String> bloomFilter = BloomFilter.create(
                    Funnels.stringFunnel(UTF_8),
                    10000,
                    0.01);
    
            // 添加元素到Bloom Filter
            bloomFilter.put("element1");
            bloomFilter.put("element2");
    
            // 检查元素是否存在于Bloom Filter
            System.out.println(bloomFilter.mightContain("element1")); // true
            System.out.println(bloomFilter.mightContain("element3")); // false
        }
    }

在这个示例中，我们使用了Guava提供的BloomFilter类来创建Bloom Filter。我们初始化了Bloom Filter，设置了预计容量为10000和误判率为0.01。然后，我们向Bloom Filter中添加了两个元素，并检查了一个已存在的元素和一个不存在的元素是否在Bloom Filter中。

##### 3.3 Redisson #####

Redisson是一个基于Redis的分布式Java对象存储库，它提供了一系列的分布式Java对象和服务。它也提供了Bloom Filter的实现，使得在Java中使用Bloom Filter变得非常方便。下面是一个示例代码，演示了如何使用Redisson实现Bloom Filter：

首先，确保在Maven中引入Redisson的依赖：

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

然后，可以使用以下代码来创建和使用Redisson的Bloom Filter：

package com.xhl.lk.auth2.modules.admin.demo;
    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://192.168.245.181:6379");
            config.useSingleServer().setPassword("123456");
            RedissonClient redisson = Redisson.create(config);
    
            // 创建Bloom Filter
            RBloomFilter<String> bloomFilter = redisson.getBloomFilter("bloomFilter");
            // 初始化Bloom Filter，预计容量为10000，误判率为0.01
            bloomFilter.tryInit(10000L, 0.01);
    
            // 添加元素到Bloom Filter
            bloomFilter.add("element1");
            bloomFilter.add("element2");
    
            // 检查元素是否存在于Bloom Filter
            System.out.println(bloomFilter.contains("element1")); // true
            System.out.println(bloomFilter.contains("element3")); // false
    
            // 关闭Redisson客户端
            redisson.shutdown();
        }
    }

在这个示例中，我们首先创建了一个Redisson的客户端，然后使用该客户端创建了一个Bloom Filter。我们初始化了Bloom Filter，设置了预计容量为10000和误判率为0.01。然后，我们向Bloom Filter中添加了两个元素，并检查了一个已存在的元素和一个不存在的元素是否在Bloom Filter中。

#### 4、使用场景 ####

*  缓存穿透问题：  
    在缓存中存储了一些数据的 key，而请求中传递的 key 不在缓存中，为了防止对底层数据源造成压力，可以使用 Bloom Filter 来快速判断请求的 key 是否可能存在于缓存中，如果不存在直接拒绝，避免了无效查询。
 *  爬虫 URL 去重：  
    爬虫系统需要处理海量的 URL，为了避免重复爬取相同的 URL，可以使用 Bloom Filter 存储已经爬取的 URL，通过判断新爬取的 URL 是否可能已经存在于 Bloom Filter 中来进行快速去重。
 *  分布式系统中的数据一致性检查：  
    在分布式系统中，为了确保各个节点存储的数据一致，可以使用 Bloom Filter 存储已经接收的数据的唯一标识，通过检查新接收的数据是否可能已经存在于 Bloom Filter 中来进行快速判断，避免了重复操作。
 *  防止邮件或者消息的重复发送：  
    在邮件系统或者消息系统中，为了避免重复发送相同的消息，可以使用 Bloom Filter 存储已经发送的消息的唯一标识，通过判断新发送的消息是否可能已经存在于 Bloom Filter 中来进行快速去重。

#### 5、优势 ####

##### 5.1 优点 #####

*  空间效率高：  
    Bloom Filter 只需要存储位图，而不需要存储具体的元素，因此在存储大量数据时，相比较其他数据结构，Bloom Filter 的空间占用更小。
 *  查询速度快：  
    Bloom Filter 的查询时间复杂度为 O(k)，其中 k 为哈希函数的个数，通常情况下 k 很小且固定，因此查询速度非常快。
 *  去重效果好：  
    Bloom Filter 能够有效地去重，可以快速判断一个元素是否存在于一个集合中。

##### 5.2 缺点 #####

*  存在误判  
    由于 Bloom Filter 是一种概率型数据结构，它可能会存在一定的误判率，即判断一个元素不存在于集合中时，有一定的概率会错误地判断为存在。这是由于多个元素映射到同一个位上造成的。
 *  无法删除元素  
    Bloom Filter 不支持删除元素的操作，一旦添加了一个元素，就无法删除。因为删除一个元素可能会影响其他元素的判断结果。
 *  不支持动态扩容  
    Bloom Filter 的大小是固定的，一旦创建后就无法动态扩容。如果需要存储的元素数量超过了预设的大小，就会导致误判率上升。

#### 6、结论 ####

尽管 Bloom Filter 存在一定的局限性，但在很多实际场景中，它仍然是一个非常有用的数据结构，能够提高系统的性能和效率。在使用 Bloom Filter 时，需要根据具体的场景和需求来选择合适的参数，并且需要注意其存在的误判率和不支持删除元素的特性

[3ea4cf45920a420887a08dc075dae000.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/341a3d56202d4c9eba17280901f0cee4.png