布隆过滤器 (BloomFilter) 是一种大家在学校没怎么学过，但在计算机很多畛域十分罕用的数据结构，它能够用来高效判断某个 key 是否属于一个汇合，有极高的插入和查问效率(O(1))，也十分省存储空间。当然它也不是白璧无瑕，它也有本人的毛病，接下来追随我一起具体理解下 BloomFilter 的实现原理，以及它优缺点、利用场景，最初再看下 Google guava 包中 BloomFilter 的实现，并比照下它和 HashSet 在不同数据量下内存空间的应用状况。
学过数据结构的人都晓得，在计算机领域咱们常常通过就义空间换工夫，或者就义工夫换空间，BloomFilter 给了咱们一种新的思路——就义准确率换空间。是的，BloomFilter 不是 100% 精确的，它是有可能有误判，但相对不会有漏判断，说艰深点就是，BloomFilter 有可能错杀坏蛋，但不会放过任何一个好人。BloomFilter 最大的长处就是省空间，毛病就是不是 100% 精确，这点当然和它的实现原理无关。
BloomFilter 的原理
在解说 BloomFilter 的实现前，咱们先来理解下什么叫 Bitmap(位图)，先给你一道《编程珠玑》上的题目。
给你一个有 100w 个数的汇合 S，每个数的数据大小都是 0 -100w，有些数据反复呈现，这就意味着有些数据可能都没呈现过，让你以 O(n)的工夫复杂度找出 0 -100w 之间没有呈现在 S 中的数，尽可能减少内存的应用。
既然工夫复杂度都限度是 O(N)了，意味着咱们不能应用排序了，咱们能够开一个长为 100w 的 int 数组来标记下哪些数字呈现过，在就标 1，不在标 0。但对于每个数来说咱们只须要晓得它在不在，只是 0 和 1 的区别，用 int(32 位)有点太节约空间了，咱们能够按二进制位来用每个 int，这样一个 int 就能够标记 32 个数，空间占用率一下子缩小到原来的 1 /32，于是咱们就有了位图，Bitmap 就是用 n 个二进制位来记录 0 - m 之间的某个数有没有呈现过。
Bitmap 的局限在于它的存储数据类型无限，只能存 0 - m 之间的数，其余的数据就存不了了。如果咱们想存字符串或者其余数据怎么办？其实也简略，只须要实现一个 hash 函数，将你要存的数据映射到 0 - m 之间就行了。这里假如你的 hash 函数产生的映射值是平均的，咱们来计算下一个 m 位的 Bitmap 到底能存多少数据?
当你在 Bitmap 中插入了一个数后，通过 hash 函数计算它在 Bitmap 中的地位并将其置为 1，这时任意一个地位没有被标为 1 的概率是：
$$
1 – \frac{1}{m}
$$
当插入 n 个数后，这个概率会变成：
$$
(1 – \frac{1}{m})^n
$$
所以任意一个地位被标记成 1 的概率就是：
$$
P_1 = 1 – (1 – \frac{1}{m})^n
$$
这时候你判断某个 key 是否在这个汇合 S 中时，只须要看下这个 key 在 hash 在 Bitmap 上对应的地位是否为 1 就行了，因为两个 key 对应的 hash 值可能是一样的，所以有可能会误判，你之前插入了 a，然而 hash(b)==hash(a)，这时候你判断 b 是否在汇合 S 中时，看到的是 a 的后果，实际上 b 没有插入过。
从下面公式中能够看出有 $P_1$ 的概率可能会误判，尤其当 n 比拟大时这个误判概率还是挺大的。如何缩小这个误判率？咱们最开始是只取了一个 hash 函数，如果说取 k 个不同的 hash 函数呢！咱们每插入一个数据，计算 k 个 hash 值，并对 k 地位为 1。在查找时，也是求 k 个 hash 值，而后看其是否都为 1，如果都为 1 必定就能够认为这个数是在汇合 S 中的。
问题来了，用 k 个 hash 函数，每次插入都可能会写 k 位，更耗空间，那在同样的 m 下，误判率是否会更高呢？咱们来推导下。
在 k 个 hash 函数的状况下，插入一个数后任意一个地位仍旧是 0 的概率是：
$$
(1 – \frac{1}{m})^k
$$
插入 n 个数后任意一个地位仍旧是 0 的概率是：
$$
(1 – \frac{1}{m})^{kn}
$$
所以可知，插入 n 个数后任意一个地位是 1 的概率是
$$
1 –
(1 – \frac{1}{m})^{kn}
$$
因为咱们用是用 k 个 hash 独特来判断是否是在汇合中的，可知当用 k 个 hash 函数时其误判率如下。它肯定是比下面 1 个 hash 函数时误判率要小（尽管我不会证实）
$$
\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} < (1 – \left[1 – \frac{1}{m}\right]^n)
$$
维基百科也给出了这个误判率的近似公式（尽管我不晓得是怎么来的，所以这里就间接援用了）
$$
\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} \approx\left(1-e^{-k n / m}\right)^{k}
$$
到这里，咱们从新创造了 Bloomfilter，就是这么简略，说白了 Bloomfilter 就是在 Bitmap 之上的扩大而已。对于一个 key，用 k 个 hash 函数映射到 Bitmap 上，查找时只须要对要查找的内容同样做 k 次 hash 映射，通过查看 Bitmap 上这 k 个地位是否都被标记了来判断是否之前被插入过，如下图。
通过公式推导和理解原理后，咱们曾经晓得 Bloomfilter 有个很大的毛病就是不是 100% 精确，有误判的可能性。然而通过选取适合的 bitmap 大小和 hash 函数个数后，咱们能够把误判率降到很低，在大数据流行的时代，适当就义准确率来缩小存储耗费还是很值得的。
除了误判之外，BloomFilter 还有另外一个很大的毛病 __只反对插入，无奈做删除__。如果你想在 Bloomfilter 中删除某个 key，你不能间接将其对应的 k 个位全副置为 0，因为这些地位有可能是被其余 key 共享的。基于这个毛病也有一些反对删除的 BloomFilter 的变种，适当就义了空间效率，感兴趣能够自行搜寻下。
如何确定最优的 m 和 k？
晓得原理后再来理解下怎么去实现，咱们在决定应用 Bloomfilter 之前，须要晓得两个数据，一个是要存储的数量 n 和预期的误判率 p。bitmap 的大小 m 决定了存储空间的大小，hash 函数个数 k 决定了计算量的大小，咱们当然都心愿 m 和 k 都越小越好，如何计算二者的最优值，咱们大略来推导下。（备注：推导过程来自 Wikipedia）
由上文可知，误判率 p 为
$$
p \approx \left(1-e^{-k n / m}\right)^{k} \ (1)
$$
对于给定的 m 和 n 咱们想让误判率 p 最小，就得让
$$
k=\frac{m}{n} \ln2 \ (2)
$$
把 (2) 式代入 (1) 中可得
$$
p=\left(1-e^{-\left(\frac{m}{n} \ln 2\right) \frac{n}{m}}\right)^{\frac{m}{n} \ln 2} \ (3)
$$
对 (3) 两边同时取 ln 并简化后，失去
$$
\ln p=-\frac{m}{n}(\ln 2)^{2}
$$
最初能够计算出 m 的最优值为
$$
m=-\frac{n \ln p}{(\ln 2)^{2}}
$$
因为误判率 p 和要插入的数据量 n 是已知的，所以咱们能够间接依据上式计算出 m 的值，而后把 m 和 n 的值代回到 (2) 式中就能够失去 k 的值。至此咱们就晓得了实现一个 bloomfilter 所须要的所有参数了，接下来让咱们看下 Google guava 包中是如何实现 BloomFilter 的。
guava 中的 BloomFilter
BloomFilter<T> 无奈通过 new 去创立新对象，而它提供了 create 静态方法来生成对象，其外围办法如下。
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {checkNotNull(funnel);
checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
checkNotNull(strategy);
if (expectedInsertions == 0) {expectedInsertions = 1;}
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {throw new IllegalArgumentException("Could not create BloomFilter of" + numBits + "bits", e);
}
}从代码能够看出，须要 4 个参数，别离是
- funnel 用来对参数做转化, 不便生成 hash 值
- expectedInsertions 预期插入的数据量大小，也就是上文公式中的 n
- fpp 误判率，也就是上文公式中的误判率 p
- strategy 生成 hash 值的策略，guava 中也提供了默认策略，个别不须要你本人从新实现
从下面代码可知，BloomFilter 创立过程中先查看参数的合法性，之后应用 n 和 p 来计算 bitmap 的大小 m（optimalNumOfBits(expectedInsertions, fpp)），通过 n 和 m 计算 hash 函数的个数 k（optimalNumOfHashFunctions(expectedInsertions, numBits)）, 这俩办法的具体实现如下。
static int optimalNumOfHashFunctions(long n, long m) {// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
static long optimalNumOfBits(long n, double p) {if (p == 0) {p = Double.MIN_VALUE;}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}其实就是上文中列出的计算公式。
前面插入和查找的逻辑就比较简单了，这里不再赘述，有趣味能够看下源码，咱们这里通过 BloomFilter 提供的办法列表理解下它的性能就行。
从上图能够看出，BloomFilter 除了提供创立和几个外围的性能外，还反对写入 Stream 或从 Stream 中从新生成 BloomFilter，不便数据的共享和传输。
应用案例
- HBase、BigTable、Cassandra、PostgreSQ 等驰名开源我的项目都用 BloomFilter 来缩小对磁盘的拜访次数，晋升性能。
- Chrome 浏览器用 BloomFilter 来判断歹意网站。
- 爬虫用 BloomFilter 来判断某个 url 是否爬取过。
- 比特币也用到了 BloomFilter 来减速钱包信息的同步。
……
和 HashSet 比照
咱们始终在说 BloomFilter 有微小的存储劣势，做个劣势到底有多显著，咱们拿 jdk 自带的 HashSet 和 guava 中实现的 BloomFilter 做下比照，数据仅供参考。
测试环境
测试平台 Mac
guava(28.1)BloomFilter，JDK11(64 位) HashSet
应用 om.carrotsearch.java-sizeof 计算理论占用的内存空间
测试形式
BloomFilter vs HashSet
别离往 BloomFilter 和 HashSet 中插入 UUID，总计插入 100w 个 UUID，BloomFilter 误判率为默认值 0.03。每插入 5w 个统计下各自的占用空间。后果如下，横轴是数据量大小，纵轴是存储空间，单位 kb。
能够看到 BloomFilter 存储空间始终都没有变，这里和它的实现无关，事实上你在通知它总共要插入多少条数据时 BloomFilter 就计算并申请好了内存空间，所以 BloomFilter 占用内存不会随插入数据的多少而变动。相同，HashSet 在插入数据越来越多时，其占用的内存空间也会越来越多，最终在插入完 100w 条数据后，其内存占用为 BloomFilter 的 100 多倍。
在不同 fpp 下的存储体现
在不同的误判率下，插入 100w 个 UUID，计算其内存空间占用。后果如下，横轴是误判率大小，纵轴是存储空间，单位 kb。
fpp,size
0.1,585.453125
0.01,1170.4765625
1.0E-3,1755.5
1.0E-4,2340.53125
1.0E-5,2925.5546875
1.0E-6,3510.578125
1.0E-7,4095.6015625
1.0E-8,4680.6328125
1.0E-9,5265.65625
1.0E-10,5850.6796875能够看出，在等同数据量的状况下，BloomFilter 的存储空间和 ln(fpp)呈正比，所以增长速率其实不算快，即使误判率缩小 9 个量级，其存储空间也只是减少了 10 倍。
参考资料
- wikipedia bloom filter