本文将炒作一个应用广泛的算法——“Bloomfilter算法”。Bloomfilter的一些概念主要包括：算法参数优缺点介绍Bloomfilter介绍Bloomfilter是“一种空间高效的概率数据结构”（百科全书原文是一种空间高效的概率数据结构），该数据结构为BurtonHowardBloom于1970年提出，“函数是测试一个元素是否是某个集合的成员”。Bloomfilter可能会出现falsepositive（这是一个专有名词“falsepositive”，可以理解为误判情况，下面如果用到这个词，会用英文单词）。也就是说，布隆过滤器在使用的时候，有可能返回结果“可能存在于集合中”或者“一定不能存在于集合中”。BloomFilter算法描述在复杂场景的网络爬虫中，爬取的网页URL依赖关系可能形成循环。例如，URL-2显示在URL-1页面上，然后显示URL-2页面。URL-1，这时候就需要一个方案来记录和判断历史访问过的URL。这时候可能会想到以下方案：方案一：使用数据库存储访问过的URL，比如在MySQL表中根据URL建立唯一索引或者使用Redis的SET数据类型方案二：使用HashSet（其实不限于HashSet，链表、树、哈希表等数据结构都可以满足）StorevisitedURLs方案三：在方案一和方案二的基础上优化，存储URL摘要，并对URL字符串使用MD5、SHA-n算法等摘要算法摘要生成方案4：使用Hash函数对相应的URL进行处理生成哈希码，然后将哈希码映射到固定容量的某个位BitSet通过一个映射函数。对于方案1、2、3，在历史URL数据量巨大的情况下，会消耗大量的存储空间（磁盘或内存）。对于解决方案4，如果有100亿个URL，那么冲突的概率必须降低到1%，所以BitSet的容量需要设置为1万亿。因此，以上四种方案都有明显的不足，Bloomfilter算法的基本思想与方案四类似。最大的区别是方案四只提到了一个哈希函数，而装置中使用了布隆过滤器算法K(k>=1)独立的高效低冲突哈希函数。一个初始化的Bloomfilter是一个长度为m的位数组，所有位都设置为0，这就是Redis中BitArray、BitSet或BitMap的概念。那么需要引入k个不同的哈希函数。一个新元素经过这k个哈希函数处理后，映射到位数组的m位中的k位，并将这些hitmap的k位置为1，产生均匀随机分布。通常，k的一个小常数取决于所需的误报率，而Bloomfilter容量m与散列函数的数量k和要添加的元素数量正相关。将所有需要添加的元素添加到Bloomfilter后，位数组中的很多位都被设置为1。此时如果需要判断一个元素是否存在于Bloomfilter中，只需要通过k个哈希函数对位数组的k个下标进行处理，然后判断位数组下标对应的位是否为1，如果k个下标所在的位中至少有一个0，则判断该位数组下标对应的位是否为1。需要判断的一定不能在布隆过滤器代表的集合中；如果k个下标所在的位全部为1，那么这个需要判断的元素在布隆过滤器表示的集合中“可能存在”，否则恰好是FalsePositive。错误率分析见下文“Bloomfilter相关参数”一节。FalsePositive的情况如下图所示：当加入Bloomfilter的元素数量比较多，而Bloomfilter的容量设置不合理（太小）时，容易出现多个元素通过k个哈希函数，映射到相同的k位（如上图中的下标1、3、9），此时无法准确判断这k位是从具体元素映射过来的。其实你可以想得更极端一点：假设Bloomfilter容量为24，哈希函数只有一个，那么如果你加起来最多25个不同的元素，两个不同元素的映射结果一定落在同一个位.布隆过滤器的相关参数在算法描述部分已经提到。Bloomfilter主要有以下几个参数：初始化位数组容量mhash函数个数k误判率ε（数学符号Epsilon，代表FalsePositiveRate）需要加上Bloomfilter的元素个数n。考虑到篇幅，这里不做这些值的关系推导，直接整理结果和关系表达式。误报率ε的估计值为：[1-e^(-kn/m)]^k最优哈希函数数k的估计值：对于给定的m和n，当k=m/n*ln2当误判率ε最低时，计算初始比特容量m的值。当k=m/n*ln2,m>=n*log2(e)*log2(1/ε)这里参考了m/n,k和FalsePositiveRate的关系：这里可以计算空间限制表中最大的参数所需要的。假设n为10亿，m/n=32，则m为320亿，k为24，此时的误判率为2.17e-07（0.000000217），所需空间为3814.69727m。一般规律是：当k固定时，m/n越大，误判率越小。要确定准确的值，最好评估增长趋势，预先计算一个比较大的m值，以减少误判率。当然，也必须权衡m值过大带来的空间消耗过大的问题。既然参数的关系式已经有了推导结果，那么就可以根据关系式写一个参数生成器：Math.pow(1-Math.exp(Math.floorDiv(-k*n,m)),k);returnBigDecimal.valueOf(temp).setScale(10,RoundingMode.FLOOR);}publicBigDecimalkForMinFalsePositiveRate(intm,intn){BigDecimalk=BigDecimal。valueOf(Math.floorDiv(m,n)*Math.log(2));returnk.setScale(10,RoundingMode.FLOOR);}publicBigDecimalbestM(intn,doublefalsePositiveRate){doubletemp=log2(Math.exp(1)+Math.floor(1/falsePositiveRate));returnBigDecimal.valueOf(n).multiply(BigDecimal.valueOf(temp)).setScale(10,RoundingMode.FLOOR);}publicdoublelog2(doublex){returnMath.log(x)/Math.log(2);}publicstaticvoidmain(String[]args){BloomFilterParamGeneratorgenerator=newBloomFilterParamGenerator();System.out.println(generator.falsePositiveRate(2,1,2));//0.3995764008System.out.println(generator.kForMinFalsePositiveRate(32,1));//22.1807097779System.out.println(generator.bestM(1,0.3995764009));//2.2382615950}}这里的计算没有考虑严格的进位和截断，所以可能和实际结果有偏差，只提供一个参考例子Bloomfilter的优点andDisadvantagesofBloomFilters布隆过滤器的优点：相比其他数据结构，布隆过滤器在时间和空间上有巨大的优势，占用内存少，查询和插入元素的时间复杂度为O(k)，可以准确判断元素Bloomfilters不存在的场景哈希函数可以独立设计Bloomfilters本身不需要存储元素，适用于一些数据敏感，数据严格保密的场景Bloomfilters的缺点：不能准确判断元素是否必须布隆过滤器中存在的场景有误判率。当k和m固定时，加入的元素越多，误判率越高。没有存储全部元素。对于一些精准查询或者精准统计的场景不适用原生Bloomfilter不能安全删除元素这里给读者一个很简单的问题：为什么原生Bloomfilter不能安全删除元素？（可以阅读之前的FalsePositive介绍）BloomfilterAlgorithmImplementation著名的Java工具库Guava自带了一个测试版的Bloomfilter实现。这里参考上面的源码实现思路和算法描述，实现一个Bloomfilter。首先考虑设计一个散列函数。更简单的方法是参考JavaBean的hashCode()方法的设计：//下面的方法来自java.util.Arrays#hashCodepublicstaticinthashCode(Objecta[]){if(a==null)return0;intresult=1;for(Objectelement:a)result=31*result+(element==null?0:element.hashCode());returnresult;}上面方法的31可以作为输入种子，每个哈希函数设计一个独立的种子，并且选择种子值作为质数，根据字符串中的每个char进行叠加，实现计算结果相对独立：importjava.util.Objects；publicclassHashFunction{/***布隆过滤器容器容量*/privatefinalintm;/***seed*/privatefinalintseed;publicHashFunction(intm,intseed){this.m=m;this.seed=seed;}publicinthash(Stringelement){if(Objects.isNull(element)){return0;}intresult=1;intlen=element.length();for(inti=0;i
