Bloom Filter 布隆过滤器

ゝ一世哀愁。 2022-09-05 11:22 27阅读 0赞

### 目录 ###

*   *   *  Bloom Filter简介
         *  布隆过滤器的原理
         *  布隆过滤器的实现
         *   *  使用guava实现
             *  使用redis实现

### Bloom Filter简介 ###

Bloom Filter 布隆过滤器，由一个叫布隆的小伙子提出，故而用他的名字来命名，可以判断元素是否在指定集合中。

常见的应用场景

*  避免缓存击穿
 *  爬虫：过滤新抓取到的url，已抓取存储的就不再处理
 *  黑白名单：过滤垃圾邮件（检测发件邮箱是否在垃圾邮箱集合中），拦截骚扰电话（检测手机号是否在指定号码库中）等等
 *  过滤用户：已签到、未签到，是否为新用户、是否活跃。

优点

*  使用二进制向量（数组），内存占用极少，空间效率高，存储集合占用的空间比哈希表小得多
 *  存储、查询元素效率高，查询花费的时间比一般算法少得多

缺点

*  有一定的误判率。可以判断某个数据一定不在集合中或者可能在集合中（也可能不在集合中），可能在集合中（也可能不在）这是必然事件，肯定是正确判断；而一定在集合中则可能存在误判，布隆过滤器判定该数据一定不在集合中，但实际可能在集合中。
 *  删除困难，加载集合后难以删除集合中的元素

bloom filter能做到时间、空间上的高效，是以牺牲判断的准确率、删除的便利性为代价的。

### 布隆过滤器的原理 ###

布隆过滤器由一串很长的二进制向量和一系列随机映射函数组成，二进制向量可以将看做一个二进制数组，存放的元素是0、1，初始值默认为0。

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，如果这些点有任何一个0，则被检元素一定不在集合中；如果都是1，则被检元素可能在集合中。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个数据跟k个bit对应。从而降低了冲突的概率。

使用bloom filter时，需要预估集合数据量n、确定期望的误判率fpp。误判指的是布隆过滤器判断为一定不在集合中，而实际可能在集合中。

### 布隆过滤器的实现 ###

布隆过滤器只是一个理论，有多种实现方式，常见的方式有2种

*  使用google开源的guava实现
 *  使用redis实现

guava使用本地内存存储数据，如果集合元素数量级较大，会占用很大一部分堆内存，此时可以考虑使用专业的内存型服务器redis，但与redis交互有网络通信的时间开销，初始化布隆过滤器时添加集合元素极慢，数据判断也比guava慢一些。

#### 使用guava实现 ####

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

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    /** * 使用Guava实现的BloomFilter */
    public class GuavaBloomFilter { 
    
        /** * 预计插入次数（集合中元素的预估数量），此处为 1百万 */
        private static final int expectedInsertions = 1000000;
    
        /** * 期待的误判率，只能为 (0,1) 上的小数，缺省时默认为 0.03 即 3% 判断100个数据大概有3个会误判 * 数值越大，对判断结果的准确性要求越低，判断速度越快，误判发生的可能性越大、发生的误判数量越多 */
        private static final double fpp = 0.001;
    
        /** * 布隆过滤器，泛型指定集合元素的类型 */
        // private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions);
        private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
    
        public static void main(String[] args) { 
            //加载集合元素
            for (int i = 0; i < expectedInsertions; i++) { 
                bf.put(i);
            }
            System.out.println("集合元素加载完毕");
    
            //判断检测
            int errCount = 0;
            for (int i = 0; i < expectedInsertions + 1000; i++) { 
                //mightContain()判断元素是否可能在集合中，false——一定不在集合中（可能为误判），true——可能在集合中也可能不在
                if (!bf.mightContain(i)) { 
                    System.out.printf("%d可能为误判\n", i);
                    errCount++;
                }
            }
            System.out.printf("判断检测完毕，可能的误判次数为%d", errCount);
        }
    
    }

#### 使用redis实现 ####

redis可通过Bitmap实现布隆过滤器，Bitmap是在字符串类型（Simple Dynamic String，SDS）之上定义的与比特相关的一系列操作，SDS作为bit数组，redis提供了setbit、getbit、bitcount等指令来操作二进制位。

jedis、spring data redis属于操作redis的基础类库，引入基础类库自己实现布隆过滤器很麻烦，可以使用现成的轮子Redisson。Redisson是java中操作redis的一个类库，提供了更上层的封装，功能强大。

<dependency>
        <groupId>org.redisson</groupId>
        <artifactId>redisson-spring-boot-starter</artifactId>
        <version>3.16.1</version>
    </dependency>

import org.redisson.Redisson;
    import org.redisson.api.RBloomFilter;
    import org.redisson.api.RedissonClient;
    import org.redisson.config.Config;
    
    /** * 基于redis实现的布隆过滤器 */
    public class RedissonBloomFilter { 
    
        /** * 预计插入次数（集合中元素的预估数量），此处为 1万 */
        private static final long expectedInsertions = 10000L;
    
        /** * 期待的误判率，(0,1)上的小数 * 数值越大，对判断结果的准确性要求越低，判断速度越快，误判发生的可能性越大、发生的误判数量越多 */
        private static final double falseProbability = 0.001;
    
        /** * 获取RedissonClient */
        public static RedissonClient getRedissonClient() { 
            Config config = new Config();
            config.useSingleServer().setAddress("redis://127.0.0.1:6379");
            return Redisson.create(config);
        }
    
        public static void main(String[] args) { 
            RedissonClient redissonClient = getRedissonClient();
            //会把布隆过滤器存储为一个键值对，所有的元素作为一个string进行储存，参数指定key的名称，泛型指定集合元素的类型
            RBloomFilter<Integer> bf = redissonClient.getBloomFilter("xxx");
            //初始化布隆过滤器，指定预计插入次数、误判率
            bf.tryInit(expectedInsertions, falseProbability);
    
            //加载集合元素
            for (int i = 0; i < expectedInsertions; i++) { 
                bf.add(i);
            }
            System.out.println("集合元素加载完毕");
    
            //判断检测
            int errCount = 0;
            for (int i = 0; i < expectedInsertions + 1000; i++) { 
                //contains判断元素是否可能在集合中，false——一定不在集合中（可能为误判），true——可能在集合中也可能不在
                if (!bf.contains(i)) { 
                    System.out.printf("%d可能为误判\n", i);
                    errCount++;
                }
            }
            System.out.printf("判断检测完毕，可能的误判次数为%d", errCount);
        }
    
    }

以上获取的RedissonClient是单机版redis的，如果是redis集群，可以参考[https://blog.csdn.net/chy\_18883701161/article/details/106380296][https_blog.csdn.net_chy_18883701161_article_details_106380296]

[https_blog.csdn.net_chy_18883701161_article_details_106380296]: https://blog.csdn.net/chy_18883701161/article/details/106380296