图解布隆过滤器，十分钟带你理解什么是布隆过滤器

谁践踏了优雅 2024-03-25 22:35 73阅读 0赞

## 一、什么是布隆过滤器？ ##

布隆过滤器（Bloom Filter）是非常经典的以空间换时间的算法。布隆过滤器由布隆在 1970 年提出。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

其实说白了，布隆过滤器就是一种节省空间的概率数据结构，通过使用很数组和一些列随机映射函数。用于判断一个元素是否在一个集合中，0代表不存在某个数据，1代表存在某个数据。

![f78015dea09cd8afef6ef76747b5b28f.png][]

## 二、布隆过滤器的优缺点 ##

## 2.1优点 ##

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。

布隆过滤器存储空间和插入/查询时间都是常数（即hash函数的个数）；

Hash 函数相互之间没有关系，方便由硬件并行实现；

布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势；

布隆过滤器可以表示全集，其它任何数据结构都不能；

## 2.2缺点 ##

布隆过滤器的缺点和优点一样明显：

误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加（误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息）。但是如果元素数量太少，则使用散列表足矣。

一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

## 三、布隆过滤器的使用场景 ##

利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，就可以直接结束查询，比如以下场景：

大数据去重，比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5 亿以上！）；

网页爬虫对 URL 的去重，避免爬取相同的 URL 地址；

反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；

缓存击穿，将已存在的缓存放到布隆过滤器中，当黑客频繁访问不存在的缓存时迅速返回避免缓存及数据库挂掉；

![2b842594c3a7b3a74c93d595059ad136.png][]

## 四、布隆过滤器实现原理 ##

## 4.1数据结构 ##

布隆过滤器是一个基于数组和哈希函数散列元素的结构，很像HashMap的哈希桶。它可以用于检测一个元素是否在集合中。它的优点是空间效率和查询时间比一般算法要好很多，缺点是有一定概率的误判性，如HashMap出现哈希碰撞。

![bfda4c4953cfc72d1e6581c1a4060cd5.png][]

## 4.2实现原理 ##

**（1）存入过程**

布隆过滤器的核心就是一个二进制数据的集合和hash计算函数。当一个元素加入布隆过滤器中的时会进行如下操作：

1.使用布隆过滤器中的哈希函数对元素值进行计算，返回对应的哈希值（一般有几个哈希函数得到几个哈希值）；

2.根据返回的hash值映射到对应的二进制集合的下标；

3.将下标对应的二进制数据改成1；

![643b997620ed31a5b3d05ff6c3f738e6.png][]

如上图所示，三个Hash函数计算key值“test”的hash值分别为2、5、9；那么就会把集合中2、5、9下标对应的数据改成1。

**（2）判断是否存在**

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

1.对给定元素再次进行相同的哈希计算；

2.根据返回的hash值判断位数组中对应的元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，则说明该元素不在布隆过滤器中。

![cff9852ff54091acf84600428e8cc7dd.png][]

从上图可以看到，元素“test”通过哈希函数计算，得到下标为 2、5、9 这 3个数据。虽然前两个点都为 1，但是很明显第 3 个点得到的数据为0，说明元素不在集合中。

## 五、布隆过滤器实现 ##

目前市面上有很多实现布隆过滤器的方式，比如Google的GUAVA实现，还有Redis的插件RedisBloom等。

接下来，我们简单实现一个布隆过滤器算法。需要注意的是，我这里的示例是为了演示布隆过滤器的实现原理的简单实现，实际上完善的布隆过滤器的算法还是比较复杂的，包括误判率，哈希计算方式等。

**1. 构建集合**

根据之前介绍的布隆过滤器的实现原理，布隆过滤器的实现主要包括可以存放二进制元素的 BitSet 以及多样性的哈希计算函数。下面通过示例演示布隆过滤器的实现。

public class MyBloomFilter {
    /**
    * 位数组的大小
    */
    private static final int DEFAULT_SIZE = 2 << 24;
    
    /**
    * 位数组。数组中的元素只能是 0 或者 1
    */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    
    /**
    * 通过这个数组可以创建 3 个不同的哈希函数
    */
    private static final int[] SEEDS = new int[]{3, 13, 46};
    
    /**
    * 存放包含 hash 函数的类的数组
    */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];
    /**
    * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
    */
    public MyBloomFilter() {
    // 初始化多个不同的 Hash 函数
    for (int i = 0; i < SEEDS.length; i++) {
    func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
    }
    }
    }

所有的元素存放都经过多样的哈希计算存放到 BitSet 中，这样可以尽可能的分散元素，减少误判性。

**2. 哈希函数**

这里只是提供了一种哈希计算的方式，实际可以实现多种不同的hash计算方式，每一个哈希计算都是一次扰动处理。一个元素的存放可以经过多次哈希，尽量让元素值做到散列，从而避免hash碰撞。

/**
    * 静态内部类。用于 hash 操作！
    */
    public static class SimpleHash {
    private int cap;
    private int seed;
    public SimpleHash(int cap, int seed) {
    this.cap = cap;
    this.seed = seed;
    }
    /**
    * 计算 hash 值
    */
    public int hash(Object value) {
    int h;
    return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
    }
    }

**3. 添加元素**

添加元素就是当某个元素不在集合中时，我们使用布隆过滤器中的哈希函数对元素值进行计算得到哈希值，然后根据返回的哈希值，将集合数组中把对应下标的值置为 1。具体代码如下：

/**
    * 添加元素到位数组
    */
    public void add(Object value) {
    for (SimpleHash f : func) {
    bits.set(f.hash(value), true);
    }
    }

**4. 比对元素**

比对元素就是判断某个元素是否存在。我们对该元素进行哈希计算，然后通过哈希值获取集合中的数据，最后把这些哈希值 进行&& 计算，从而确定该元素是否存在。具体代码如下：

/**
    * 判断指定元素是否存在于位数组
    */
    public boolean contains(Object value) {
    boolean ret = true;
    for (SimpleHash f : func) {
    ret = ret && bits.get(f.hash(value));
    }
    return ret;
    }

这里使用多个集合中的bit位置记录同一个元素的状态，确保结果更加准确，避免hash碰撞。

**5. 验证测试**

接下来我们创建一个测试类，验证布隆过滤器是否生效。示例代码如下：

public class MyBloomFilterTest {
    public static void main(String[] args) {
    String value1 = "com:weiz:user:logininfo";
    String value2 = "https://www.cnblogs.com/zhangweizhong";
    String value3 = "200110221";
    MyBloomFilter filter = new MyBloomFilter();
    filter.add(value1);
    filter.add(value2);
    System.out.println("key:" + value1 +"是否存在:"+ filter.contains(value1));
    System.out.println("key:" + value2 +"是否存在:"+ filter.contains(value2));
    System.out.println("key:" + value3 +"是否存在:"+ filter.contains(value3));
    }
    }

运行上面的测试代码，验证布隆过滤器算法是否正常，具体结果如下图所示：

![67ef35a0b4d60323ce32510d75c5c47e.png][]

通过上面的输出结果可以看到，value1和value2已经添加到布隆过滤器，返回结果为true，而value3未加入到布隆过滤器，所以返回false。说明布隆过滤器起到了数据过滤的作用。

[f78015dea09cd8afef6ef76747b5b28f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/89afa0b3a912441a9953a871f0be8958.png
[2b842594c3a7b3a74c93d595059ad136.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0bbb2571f54a45129c9ec47efa0b13b2.png
[bfda4c4953cfc72d1e6581c1a4060cd5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/260484a9b5f1404fb134e3d935d9e031.png
[643b997620ed31a5b3d05ff6c3f738e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c842553add6c4351b319c634b1c4fadf.png
[cff9852ff54091acf84600428e8cc7dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/89797ddf74d74346a231fc29ea2dcf73.png
[67ef35a0b4d60323ce32510d75c5c47e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ebbcd4daaa36443a87f8bc21cb52d24b.png