共计 5279 个字符，预计需要花费 14 分钟才能阅读完成。
在程序的世界中，布隆过滤器是程序员的一把利器，利用它能够疾速地解决我的项目中一些比拟辣手的问题。如网页 URL 去重、垃圾邮件辨认、大汇合中反复元素的判断和缓存穿透等问题。
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都比个别的算法要好的多，毛病是有肯定的误识别率和删除艰难。
浏览更多对于 Angular、TypeScript、Node.js/Java、Spring 等技术文章，欢送拜访我的集体博客 ——全栈修仙之路
一、布隆过滤器简介
当你往简略数组或列表中插入新数据时，将不会依据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有间接关系。这样的话，当你须要在数组或列表中搜寻相应值的时候，你必须遍历已有的汇合。若汇合中存在大量的数据，就会影响数据查找的效率。
针对这个问题，你能够思考应用哈希表。利用哈希表你能够通过对“值”进行哈希解决来取得该值对应的键或索引值，而后把该值寄存到列表中对应的索引地位。这意味着索引值是由插入项的值所确定的，当你须要判断列表中是否存在该值时，只须要对值进行哈希解决并在相应的索引地位进行搜寻即可，这时的搜寻速度是十分快的。
bf-array-vs-hashtable.jpg
依据定义，布隆过滤器能够查看值是“可能在汇合中”还是“相对不在汇合中”。“可能”示意有肯定的概率，也就是说可能存在肯定为误判率。那为什么会存在误判呢？上面咱们来剖析一下具体的起因。
布隆过滤器（Bloom Filter）实质上是由长度为 m 的位向量或位列表（仅蕴含 0 或 1 位值的列表）组成，最后所有的值均设置为 0，如下图所示。
bf-bit-vector.jpg
为了将数据项增加到布隆过滤器中，咱们会提供 K 个不同的哈希函数，并将后果地位上对应位的值置为“1”。在后面所提到的哈希表中，咱们应用的是单个哈希函数，因而只能输入单个索引值。而对于布隆过滤器来说，咱们将应用多个哈希函数，这将会产生多个索引值。
bf-input-hash.jpg
如上图所示，当输出“semlinker”时，预设的 3 个哈希函数将输入 2、4、6，咱们把相应地位 1。假如另一个输出”kakuqo“，哈希函数输入 3、4 和 7。你可能曾经留神到，索引位 4 曾经被先前的“semlinker”标记了。此时，咱们曾经应用“semlinker”和”kakuqo“两个输出值，填充了位向量。以后位向量的标记状态为：
bf-input-hash-1.jpg
当对值进行搜寻时，与哈希表相似，咱们将应用 3 个哈希函数对”搜寻的值“进行哈希运算，并查看其生成的索引值。假如，当咱们搜寻”fullstack“时，3 个哈希函数输入的 3 个索引值别离是 2、3 和 7：
bf-input-hash-2.jpg
从上图能够看出，相应的索引位都被置为 1，这意味着咱们能够说”fullstack“可能曾经插入到汇合中。事实上这是误报的情景，产生的起因是因为哈希碰撞导致的偶合而将不同的元素存储在雷同的比特位上。侥幸的是，布隆过滤器有一个可预测的误判率（FPP）：
bf-fpp.jpg
n 是曾经增加元素的数量；
k 哈希的次数；
m 布隆过滤器的长度（如比特数组的大小）。
极其状况下，当布隆过滤器没有闲暇空间时（满），每一次查问都会返回 true。这也就意味着 m 的抉择取决于冀望预计增加元素的数量 n，并且 m 须要远远大于 n。
理论状况中，布隆过滤器的长度 m 能够依据给定的误判率（FFP）的和冀望增加的元素个数 n 的通过如下公式计算：
bf-bit-vector-length.jpg
对于 m/n 比率示意每一个元素须要调配的比特位的数量，也就是哈希函数 k 的数量能够调整误判率。通过如下公式来抉择最佳的 k 能够缩小误判率（FPP）：
bf-hash-fn-count.jpg
理解完上述的内容之后，咱们能够得出一个论断，当咱们搜寻一个值的时候，若该值通过 K 个哈希函数运算后的任何一个索引位为”0“，那么该值必定不在汇合中。但如果所有哈希索引值均为”1“，则只能说该搜寻的值可能存在汇合中。
二、布隆过滤器利用
在理论工作中，布隆过滤器常见的利用场景如下：
网页爬虫对 URL 去重，防止爬取雷同的 URL 地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
Google Chrome 应用布隆过滤器辨认歹意 URL；
Medium 应用布隆过滤器防止举荐给用户曾经读过的文章；
Google BigTable，Apache HBbase 和 Apache Cassandra 应用布隆过滤器缩小对不存在的行和列的查找。
除了上述的利用场景之外，布隆过滤器还有一个利用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查问不在缓存中的数据，这样每次服务调用都会到数据库中进行查问，如果这类申请比拟多的话，就会导致数据库压力增大，这样缓存就失去了意义。
利用布隆过滤器咱们能够事后把数据查问的主键，比方用户 ID 或文章 ID 缓存到过滤器中。当依据 ID 进行数据查问的时候，咱们先判断该 ID 是否存在，若存在的话，则进行下一步解决。若不存在的话，间接返回，这样就不会触发后续的数据库查问。须要留神的是缓存穿透不能齐全解决，咱们只能将其管制在一个能够容忍的范畴内。
三、布隆过滤器实战
布隆过滤器有很多实现和优化，由 Google 开发驰名的 Guava 库就提供了布隆过滤器（Bloom Filter）的实现。在基于 Maven 的 Java 我的项目中要应用 Guava 提供的布隆过滤器，只须要引入以下坐标：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
在导入 Guava 库后，咱们新建一个 BloomFilterDemo 类，在 main 办法中咱们通过 BloomFilter.create 办法来创立一个布隆过滤器，接着咱们初始化 1 百万条数据到过滤器中，而后在原有的根底上减少 10000 条数据并判断这些数据是否存在布隆过滤器中：
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);
}}
当以上代码运行后，控制台会输入以下后果：
已匹配数量 1000309
很显著以上的输入后果曾经呈现了误报，因为相比预期的后果多了 309 个元素，误判率为：
309/(1000000 + 10000) * 100 ≈ 0.030594059405940593
如果要进步匹配精度的话，咱们能够在创立布隆过滤器的时候设置误判率 fpp：
BloomFilter<CharSequence> bf = BloomFilter.create(
Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);
在 BloomFilter 外部，误判率 fpp 的默认值是 0.03：
// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03D);
}
在从新设置误判率为 0.0002 之后，咱们从新运行程序，这时控制台会输入以下后果：
已匹配数量 1000003
通过观察以上的后果，可知误判率 fpp 的值越小，匹配的精度越高。当缩小误判率 fpp 的值，须要的存储空间也越大，所以在理论应用过程中须要在误判率和存储空间之间做个衡量。
四、简易版布隆过滤器
为了便于大家了解布隆过滤器，咱们来看一下上面简易版布隆过滤器。
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;
}
}}
在 SimpleBloomFilter 类的实现中，咱们应用到了 Java util 包中的 BitSet，BitSet 是位操作的对象，值只有 0 或 1，外部保护了一个 long 数组，初始只有一个 long，所以 BitSet 最小的容量是 64 位。当随着存储的元素越来越多，BitSet 外部会动静扩容，最终外部是由 N 个 long 值来存储。默认状况下，BitSet 的所有位都是 0。
五、总结
本文次要介绍的布隆过滤器的概念和常见的利用场合，在实战局部咱们演示了 Google 驰名的 Guava 库所提供布隆过滤器（Bloom Filter）的根本应用，同时咱们也介绍了布隆过滤器呈现误报的起因及如何进步判断准确性。最初为了便于大家了解布隆过滤器，咱们介绍了一个简易版的布隆过滤器 SimpleBloomFilter。
六、参考资源
了解布隆过滤器
布隆过滤器 (Bloom Filter) 的原理和实现
probabilistic-data-structures-bloom-filter