查看“什么是布隆过滤器（BloomFilter）？”的源代码

[[category:Redis]][[category:数据结构]]

== 关于 ==
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的'''二进制向量'''和一系列'''随机映射函数'''。


布隆过滤器可以用于'''检索一个元素是否可能在一个集合中'''。
* 优点：空间效率和查询时间都比一般的算法要好的多，
* 缺点：有一定的误识别率，'''不能删除'''。
** 其变种“Counting Bloom filter”可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。

=== 通常判断某个元素是否存在用的是什么？ ===
HashMap！
: 将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。
: [[File:HashMap实现集合中元素判断.jpg|600px]]

但是 HashMap 的实现也有缺点，例如存储容量占比高：
: 考虑到负载因子的存在，通常空间是不能被用满的，而数据量大的时候，HashMap 占据的内存大小就变得很可观了。


由此就需要一种查询效率近似 HashMap，但空间占用更少的结构来进行大数据量的判断。

== 原理 ==
布隆过滤器是一个 bit 向量或者说 bit 数组（仅包含 0 或 1 值）：
: [[File:布隆过滤器结构.jpg|400px]]


要映射一个值到布隆过滤器中，我们需要使用'''多个不同的哈希函数'''生成'''多个哈希值'''，并将每个哈希值所指向的 bit 位置为 1：
: 如下，添加元素“semlinker”：
: [[File:布隆过滤器：添加元素1.jpg|400px]]
: 如下，添加元素“kakuqo”：
: [[File:布隆过滤器：添加元素2.jpg|400px]]
在进行元素判定时，同样通过多个哈希函数生成多个哈希值，并查找哈希值所指向的 bit 位：
: 如下，查找元素“semlinker”：
: [[File:布隆过滤器：添加元素1.jpg|400px]]
: 如下，查找元素“fullstack”：
: [[File:布隆过滤器：判断元素1.jpg|400px]]
: 查找元素“bullshit”：
: [[File:布隆过滤器：判断元素2.jpg|400px]]
可以看出，判定结果为：元素“semlinker”、“fullstack”都在集合中，“bullshit”不在集合中。

但是其实“fullstack”并不在其中，是误报。
* 产生误报的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。


如上，可以看出 Bloom Filter 的判定结果：
# 哈希值比特位都为 1，元素'''可能'''在集合中；
# 哈希值比特位有 0，元素'''一定不在'''集合中。
即，布隆过滤器用于'''检索一个元素是否可能在一个集合中'''。

== “布隆过滤器长度”（m）和“哈希函数个数”（k） ==
“布隆过滤器长度”与“哈希函数个数”直接影响 Bloom Filter 的效率：
* 布隆过滤器的长度会直接影响误报率：布隆过滤器越长其误报率越小。
*: 布隆过滤器长度过小，则很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了；
* 哈希函数的个数则需要在效率与误报率间平衡：
*: 个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。


以：'''k''' 为哈希函数个数，'''m''' 为布隆过滤器长度，'''n''' 为插入的元素个数，'''p''' 为误报率，其关系如下：
:[[File:布隆过滤器：k、m、n、p之间的关系.jpg|600px]]
极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 '''m 需要远远大于 n''' 。


实际情况中，以如下公式确定 k、m：
:[[File:布隆过滤器：适合的“布隆过滤器长度”（m）和“哈希函数个数”（k）.jpg|200px]]

而误报率也可由公式得到：
:[[File:布隆过滤器：误判率（FFP）.jpg|200px]]

== 应用 ==
在实际工作中，布隆过滤器常见的应用场景如下：
* '''网页爬虫'''对 URL 去重，避免爬取相同的 URL 地址；
* '''反垃圾邮件'''，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；【邮箱配置中常见】
* Google Chrome 使用布隆过滤器识别'''恶意 URL'''；
* Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
* Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。


除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决'''缓存穿透'''的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
* 需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。


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

=== Redis 使用布隆过滤器 ===
Redis 因其支持 '''setbit''' 和 '''getbit''' 操作（string类型操作），且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。


但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议'''对布隆过滤器进行拆分'''。

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

== 布隆过滤器实战 ==
布隆过滤器有很多实现和优化，由 Google 开发著名的 '''Guava''' 库就提供了布隆过滤器（Bloom Filter）的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器，只需要引入以下坐标：
<syntaxhighlight lang="xml" highlight="">
<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>
</syntaxhighlight>

复制代码在导入 Guava 库后，我们新建一个 BloomFilterDemo 类，在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器，接着我们初始化 1 百万条数据到过滤器中，然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中：
<syntaxhighlight lang="java" highlight="">
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 总数量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }
}
</syntaxhighlight>
复制代码当以上代码运行后，控制台会输出以下结果：
<syntaxhighlight lang="java" highlight="">
已匹配数量 1000309
</syntaxhighlight>
复制代码很明显以上的输出结果已经出现了误报，因为相比预期的结果多了 309 个元素，误判率为：
<syntaxhighlight lang="java" highlight="">
309/(1000000 + 10000) * 100 ≈ 0.030594059405940593
</syntaxhighlight>


复制代码如果要提高匹配精度的话，我们可以在创建布隆过滤器的时候设置误判率 fpp：
<syntaxhighlight lang="java" highlight="">
BloomFilter<CharSequence> bf = BloomFilter.create(
  Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);
</syntaxhighlight>
复制代码在 BloomFilter 内部，误判率 fpp 的默认值是 0.03：
<syntaxhighlight lang="java" highlight="">
// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
  return create(funnel, expectedInsertions, 0.03D);
}
</syntaxhighlight>
复制代码在重新设置误判率为 0.0002 之后，我们重新运行程序，这时控制台会输出以下结果：
<syntaxhighlight lang="java" highlight="">
已匹配数量 1000003
</syntaxhighlight>
复制代码通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

== 简易版布隆过滤器 ==
为了便于理解，以下实现了一个简易版布隆过滤器：
<syntaxhighlight lang="java" highlight="">
package com.semlinker.bloomfilter;

import java.util.BitSet;

public class SimpleBloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61};

    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public SimpleBloomFilter() {
        // 创建多个哈希函数
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加元素到布隆过滤器中
     *
     * @param value
     */
    public void put(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断布隆过滤器中是否包含指定元素
     *
     * @param value
     * @return
     */
    public boolean mightContain(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    public static void main(String[] args) {
        SimpleBloomFilter bf = new SimpleBloomFilter();
        for (int i = 0; i < 1000000; i++) {
            bf.put("" + i);
        }
        // 判断值是否存在过滤器中
        int count = 0;
        for (int i = 0; i < 1000000 + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配数量 " + count);
    }

    /**
     * 简单哈希类
     */
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            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);
            }
            return (cap - 1) & result;
        }
    }
}
</syntaxhighlight>
在 SimpleBloomFilter 类的实现中，我们使用到了 Java util 包中的 BitSet，BitSet 是位操作的对象，值只有 0 或 1 ，内部维护了一个 long 数组，初始只有一个 long，所以 BitSet 最小的容量是 64 位。当随着存储的元素越来越多，BitSet 内部会动态扩容，最终内部是由 N 个 long 值来存储。默认情况下，BitSet 的所有位都是 0。

== 参考 ==
# [https://segmentfault.com/a/1190000021136424 布隆过滤器你值得拥有的开发利器]
# [https://juejin.cn/post/6844904007790673933 5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！]
# [https://zhuanlan.zhihu.com/p/43263751 详解布隆过滤器的原理，使用场景和注意事项]