布隆过滤器布隆过滤器是由一个位数组和多个哈希函数组成的概率数据结构，返回两种结果：可能存在和一定不存在。布隆过滤器中的元素由多个状态值共同确定。位数组存储状态值，哈希函数计算状态值的位置。从其算法结构来看，它具有以下特点：用一个有限位数组来表示大于其长度的元素个数，因为一位的状态值可以同时标识多个元素。无法删除元素。因为一个位的状态值可能同时标识多个元素。添加元素永远不会失败。就像添加元素的数量增加一样，误判率也会增加。如果判断要素不存在，则一定不存在。比如下面X,Y,Z由三个状态值共同判断元素是否存在，状态值的位置分别由三个哈希函数计算得到。数学关系误判概率是关于误判的概率，由于每一位的状态值可能同时识别多个元素，所以具有一定的误判概率。如果位数组已满，则在判断元素是否存在时总是返回true，对于不存在的元素误报率为100%。那么，与误判概率、加入元素个数、Bloomfilter的长度（位数组大小）、哈希函数个数有关的因素有哪些。根据维基百科，误判概率\(P_{fp}\)有如下关系：$${P_{fp}=\left(1-\left[1-{\frac{1}{m}}\右]^{kn}\right)^{k}\approx\left(1-e^{{-\frac{kn}{m}}}\right)^{k}}$$$m$是一个位数组大小；$n$是添加元素的个数；$k$是散列函数的个数；$e$是一个数学常数，大约等于2.718281828。由此可知，当加入的元素个数为0时，虚警率为0；当所有位数组都为1时，误报率为100%。在不同数量的哈希函数下，$P_{fp}$和$n$之间的关系如下图所示：根据误判概率公式，可以做一些事情来估计最优的Bloomfilter长度。估计哈希函数的最佳数量。最佳布隆过滤器长度\(m\)等于：$${\displaystylem=-{\frac{n\lnP_{fp}}{(\ln2)^{2}}}\approx-1.44\cdotn\log_{2}P_{fp}}$$最优哈希函数个数当\(n\)和\(P_{fp}\)确定时，\(k\)等于：$${\displaystylek=-{\frac{\lnP_{fp}}{\ln2}}=-\log_{2}P_{fp}}$$当\(n\)和\(m\)确定后，\(k\)等于：$${\displaystylek={\frac{m}{n}}\ln2}$$实施布隆过滤器在使用布隆过滤器之前，我们通常评估两个因素。预计要添加的最大元素数。企业对错误的容忍度。比如允许错1000例，那么误判的概率应该在千分之一以内。很多布隆过滤工具都提供了期望添加的次数和误判概率的配置参数，它们会根据配置的参数计算哈希函数的最优长度和个数。Java中有一些不错的布隆过滤器工具包。番石榴中的布隆过滤器。redisson中的RedissonBloomFilter可以在redis中使用。看看Guava中BloomFilter的简单实现，在创建之前先计算出位数组的长度和哈希函数的个数。staticBloomFiltercreate(Funnelfunnel,longexpectedInsertions,doublefpp,Strategystrategy){/***expectedInsertions:期望加法数*fpp:误判概率*/longnumBits=optimalNumOfBits（预期插入，fpp）；intnumHashFunctions=optimalNumOfHashFunctions(expectedInsertions,numBits);尝试{returnnewBloomFilter(newBitArray(numBits),numHashFunctions,funnel,strategy);}catch(IllegalArgumentException"IllegalExceptione){thrownotcreateBloomFilterof"+numBits+"bits",e);}}根据最优布隆过滤器长度公式计算最优位数组长度。staticlongoptimalNumOfBits(longn,doublep){if(p==0){p=Double.最小值；}return(long)(-n*Math.log(p)/(Math.log(2)*Math.log(2)));}根据最佳散列函数数公式计算最佳散列函数数。staticintoptimalNumOfHashFunctions(longn,longm){returnMath.max(1,(int)Math.round((double)m/n*Math.log(2)));redisson中RedissonBloomFilter的计算方式也是一致的。privateintoptimalNumOfHashFunctions(longn,longm){returnMath.max(1,(int)Math.round((double)m/n*Math.log(2)));}privatelongoptimalNumOfBits(longn,doublep){if(p==0){p=Double.最小值；}return(long)(-n*Math.log(p)/(Math.log(2)*Math.log(2)));}内存占用想象一个手机号码去重场景。每个手机号占用22个字节。估计的逻辑内存如下。expectedHashSetfpp=0.0001fpp=0.00000011万18.28MB2.29MB4MB10万182.82MB22.85MB40MB1十亿1.78G228.53MB400MB注：实际物理内存使用量大于逻辑内存。误判概率\(p\)与添加元素\(n\)、位数组长度\(m\)、哈希函数个数\(k\)的关系如下：应用场景弱口令检测；垃圾邮件地址过滤。浏览器检测钓鱼网站；缓存穿透。弱密码检测维护弱哈希密码列表。当用户注册或更新密码时，将使用布隆过滤器检查新密码，检测到提示用户。垃圾邮件地址过滤维护一个散列垃圾邮件地址列表。当用户收到电子邮件时，会使用Bloom过滤器进行检测并将其识别为垃圾邮件。浏览器网络钓鱼检测使用Bloom过滤器来查找网站的URL是否存在于网络钓鱼数据库中。缓存穿透缓存穿透是指查询根本不存在的数据，缓存层和数据库都不会命中。当缓存未命中时，查询数据库数据库未命中，空结果不写回缓存并返回空结果。数据库命中，查询结果写回缓存并返回结果。典型的攻击模拟大量请求查询不存在的数据，所有请求都落到数据库上，导致数据库宕机。其中一种解决方案是将已有的缓存放入Bloomfilter中，在请求前进行校验过滤。总结对于千万亿级的数据，使用布隆过滤器具有一定的优势。此外，根据业务场景合理评估预期增加数量和误判概率是关键。参考https://en.wikipedia.org/wiki...https://hur.st/bloomfilter
