布隆过滤器(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,size0.1,585.4531250.01,1170.47656251.0E-3,1755.51.0E-4,2340.531251.0E-5,2925.55468751.0E-6,3510.5781251.0E-7,4095.60156251.0E-8,4680.63281251.0E-9,5265.656251.0E-10,5850.6796875能够看出，在等同数据量的状况下，BloomFilter的存储空间和ln(fpp)呈正比，所以增长速率其实不算快，即使误判率缩小9个量级，其存储空间也只是减少了10倍。
参考资料
- wikipedia bloom filter