布隆过滤器介绍以及布隆过滤器的实现

2024-03-02 12:28:22

一·简介

布隆过滤器（Bloom Filter）实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

二·原理

1·刚开始是一个全部位为0的 bit 向量或者说 bit 数组

2.往过滤器增加"Bloom"

3.往过滤器增加"Filter"

4.在过滤器中查询“Hash”，5的位置是0，说明“Hash”一定不存在

5.可能存在误判情况（布隆过滤器可能会误判，如果它说不存在那肯定不存在，如果它说存在，那数据有可能实际不存在；）

Redis的bitmap 支持2^32大小，对应到内存也就是512MB，误判率万分之一，可以放下2亿左右的数据，性能高，空间占用率及小，省去了大量无效的数据库连接。

三·使用场景

防止缓存穿透
网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
Google Chrome 使用布隆过滤器识别恶意 URL；
Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

四·实战使用

1.Java Guava实现

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>19.0</version>
</dependency>

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * @author wayleung
 * @description
 * @date 2020-11-26 11:31:24
 */
public class BloomFilterTest {
    //预计要插入多少数据
    private static int size = 1000000;

    //期望的误判率
    private static double fpp = 0.001;

    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

    public static void main(String[] args) {
        //插入数据 1-1000000
        for (int i = 1; i <= 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        //判断 1000001-2000000 因为肯定是不存在的，所以如果是true的话那肯定就是误判
        for (int i = 1000001; i <= 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("一共的误判数:" + count);
    }
}

2.Redis实现

1、安装Redis官方插件 RedisBloom并在Redis配置文件中添加插件

https://github.com/RedisLabsModules/redisbloom/

[root@redis]# vim redis.conf

#####################MODULES####################

# Load modules at startup. If the server is not able to load modules
# it will abort. It is possible to use multiple loadmodule directives.
loadmodule /usr/local/redis/redisbloom-1.1.1/rebloom.so

2、使用布隆过滤

增加到布隆过滤器

bf.add myfilter 123

从布隆过滤器中查询，判断是否存在

bf.exists myfilter 123 #返回 1 ，说明可能存在值

bf.exists myfilter 321 #返回 0，说明不存在该值

3、准确率

Redis中有一个命令可以来设置布隆过滤器的准确率：

bf.reserve myfilter 0.01 100

码农公寓