布隆过滤器简介

01、什么是 BloomFilter（布隆过滤器）

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，这个时候往往我们都是采用 Hashmap，Set 或者其他集合将数据保存起来，然后进行对比判断，但是如果元素很多的情况，我们如果采用这种方式就会非常浪费空间。这个时候我们就需要 BloomFilter 来帮助我们了。

1.1、BloomFilter 原理

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列（通常好几个）映射函数组成的。布隆过滤器的原理是，当一个变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1。查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了，如果这些点有任何一个 0，则被查询变量一定不在；如果都是 1，则被查询变量很可能在。注意，这里是可能存在，不一定一定存在！这就是布隆过滤器的基本思想。

如下图所示，字符串 "ziyou" 在经过四个映射函数操作后在位图上有四个点被设置成了 1。当我们需要判断 “ziyou” 字符串是否存在的时候只要在一次对字符串进行映射函数的操作，得到四个 1 就说明 “ziyou” 是可能存在的。

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的，意思也就是说会存在一个字符串可能是 “ziyou01” 经过相同的四个映射函数运算得到的四个点跟 “ziyou” 是一样的，这种情况下我们就说出现了误算。另外还有可能这四个点位上的 1 是四个不同的变量经过运算后得到的，这也不能证明字符串 “ziyou” 是一定存在的，如下图框出来的 1 也可能是字符串“张三”计算得到，同理其他几个位置的 1 也可以是其他字符串计算得到。

1.2 特性

所以通过上面的例子我们就可以明确

• 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。

• 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

02、使用场景

2.1、网页 URL 去重

我们在使用网页爬虫的时候（爬虫需谨慎），往往需要记录哪些 URL 是已经爬取过的，哪些还是没有爬取过，这个时候我们就可以采用 BloomFilter 来对已经爬取过的 URL 进行存储，这样在进行下一次爬取的时候就可以判断出这个 URL 是否爬取过。

2.2、黑白名单存储

工作中经常会有一个特性针对不同的设备或者用户有不同的处理方式，这个时候可能会有白名单或者黑名单存在，所以根据 BloomFilter 过滤器的特性，我们也可以用它来存在这些数据，虽然有一定的误算率，但是在一定程度上还是可以很好的解决这个问题的。

2.3、小结

除了上面说的两种场景，其实还有很多场景，比如热点数据访问，垃圾邮件过滤等等，其实这些场景的统一特性就是要判断某个元素是否在某个集合中，原理都是一样的。

03、代码实践

3.1、自己实现

package com.test.pkg;
import java.util.BitSet;
/** * <br> * <b>Function：</b><br> * <b>Author：</b>@author ziyou<br> * <b>Date：</b>2019-10-23 23:21<br> * <b>Desc：</b>无<br> */public class BloomFilterTest {
    /**     * 初始化布隆过滤器的 bitmap 大小     */    private static final int DEFAULT_SIZE = 2 << 24;    /**     * 为了降低错误率，这里选取一些数字作为基准数     */    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};    /**     * 设置 bitmap     */    private static BitSet bitset = new BitSet(DEFAULT_SIZE);    /**     * 设置 hash 函数数量     */    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**     * 添加数据     *     * @param value 需求加入的值     */    public static void put(String value) {        if (value != null) {            for (HashFunction f : functions) {                //计算 hash 值并修改 bitmap 中相应位置为 true                bitset.set(f.hash(value), true);            }        }    }
    /**     * 判断相应元素是否存在     *     * @param value 需要判断的元素     * @return 结果     */    public static boolean check(String value) {        if (value == null) {            return false;        }        boolean ret = true;        for (HashFunction f : functions) {            ret = bitset.get(f.hash(value));            //一个 hash 函数返回 false 则跳出循环            if (!ret) {                break;            }        }        return ret;    }
    public static void main(String[] args) {        String value = "test";        for (int i = 0; i < seeds.length; i++) {            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);        }        put(value);        System.out.println(check("value"));    }}
class HashFunction {
    private int size;    private int seed;
    public HashFunction(int size, int seed) {        this.size = size;        this.seed = seed;    }
    public int hash(String value) {        int result = 0;        int len = value.length();        for (int i = 0; i < len; i++) {            result = seed * result + value.charAt(i);        }        int r = (size - 1) & result;        return (size - 1) & result;    }
}

上面我们自己写了一个简单的 BloomFilter ，通过 put 方法录入数据，通过 check 方法判断元素是否存在，基本能实现功能，代码中注释也写的很清楚，但是自己实现必定效率不高，所以下面我们看下业内大佬帮我们已经实现好的 BloomFilter。

2.4、Guava 中的 BloomFilter

package com.test.pkg;
import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;
/** * <br> * <b>Function：</b><br> * <b>Author：</b>@author ziyou<br> * <b>Date：</b>2019-10-24 00:17<br> * <b>Desc：</b>无<br> */public class BloomFilterTest02 {
    public static void main(String[] args) {        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);        for (int i = 0; i < 100000; i++) {            bloomFilter.put(i);        }        System.out.println(bloomFilter.mightContain(1));        System.out.println(bloomFilter.mightContain(2));        System.out.println(bloomFilter.mightContain(3));        System.out.println(bloomFilter.mightContain(100001));    }}

Guava 中已经帮我们实现好了 BloomFilter 的代码，我们只需要在使用的地方调用就好。

这里我们简单解释一下构造方法中的后面两个参数，一个是预计包含的数据量，一个是允许的误差值。代码中会根据我们填入的这两个值，自动帮我们计算出数组的大小，以及需要的散列函数个数，如下图。更多详细的内容，读者可以自行去查看源码，我们这里就不介绍了。

04、总结

这篇文章给大家介绍了 BloomFilter，一个用来判断元素是否存在与某个集合的高效方法，可以在我们日常的工作中运用起来，结合日常工作的场景，可以进行选择。

其他的一些更具体的简介：

在进入正文之前，之前看到的有句话我觉得说得很好：

Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.

大意是不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。

什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实现原理

HashMap 的问题

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：

Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：

值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

支持删除么

目前我们知道布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上图中的 bit 位 4 被两个值共同覆盖的话，一旦你删除其中一个值例如 “tencent” 而将其置位 0，那么下次判断另一个值例如 “baidu” 是否存在的话，会直接返回 false，而实际上你并没有删除它。

如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。

如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：

如何推导这个公式这里只是提一句，因为对于使用来说并没有太大的意义，你让一个高中生来推会推得很快。k 次哈希函数某一 bit 位未被置为 1 的概率为：

插入n个元素后依旧为 0 的概率和为 1 的概率分别是：

标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 1，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定

最佳实践

常见的适用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

另外，既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。

大Value拆分

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

转载自：https://zhuanlan.zhihu.com/p/43263751