布隆过滤器的原理与实现前言
最近，在朋友的面试中，经常有人问我如何解决redis缓存直通，什么是redis缓存直通。 客户端通过访问不存在缓存或数据库的类似key的查询直接访问数据库。 解决办法有很多。
1接口参数检查、
2将缓存设置为空值，然后单击、
3布隆过滤器。
本章来看看布隆过滤器是如何解决的
什么是布隆过滤器
布隆过滤器从大量数据中快速验证是否存在一个数据。
内部结构由一组多个散列函数和位数组成
各位的位置默认为0
以下请参阅图
实现过程
1、将所有数据的位置信息添加到位数组中
每个数据都由散列函数运算，如果有几个函数，则计算几次。
每次计算时计算出对应的位置信息，将该位置从0置于1，
2、检查个别数据是否在布隆过滤器中
与附加位置信息同样地经由多个函数计算对应值信息
如果各位置信息为1，则布隆过滤器判断为存在该数据
在都为0的情况下，或者一个位置信息为0的情况下，判断为数据不存在
优势：
1、只保存保存数据的位置信息，空间利用率极高
2、信息安全性高，无法根据位置信息反算数据
3、查询效率高，时间复杂度为0(n )缺点：
存在一定的错误判断：不存在的数据经过混列运算计算出的位置信息都为1时，此时发生混列冲突，布隆过滤器进行错误判断。 因为散列冲突是不可避免的，所以错误判定是不可避免的。 hash函数越多，错误判定率越低。 该错误判定率可以手动配置，但请记住，错误判定率最低的bit数组越大，与散列函数的多少相对应的性能越低
数据难以删除：在尝试删除某个数据时，不能只将他的对应位置设置为0。 因为那个位置可能还是另一个数据的位置信息。 所以不能物理删除。
看这里，布隆过滤器无法避免误判率，你可能会问为什么要使用它，或者什么时候使用。它只会误判不存在的数据，不会误判存在的数据
让我们回到前面提到的redis缓存直通问题。 当有人恶意攻击你的服务器缓存，并以每秒上万个不存在的k访问我们的缓存时，我们会在缓存前加一个光晕过滤器，这样只要有真实的数据就一定不会误判。 通过布隆过滤器后，可能很少有非法数据访问我们的服务器。 服务器也能承受。
经典应用场景
1、文字处理软件需要检查一个英语单词是否正确
2、网站非法网址过滤
3、订单物流号码查询
4、联邦调查局，调查嫌疑人是否存在于嫌疑人名单上
最后，让我们来看看演示
所需的依赖
ependencygroupidcom.Google.guava/groupidartifactidguava/artifactidversion 21.0/version/dependency代码的实现
package com.teamer.service TM.controller； import com.Google.com mon.base.charsets； import com.Google.com mon.hash.bloom filter； import com.Google.com mon.hash.funnels； import java.util.ArrayList； import java.util.List； import java.util.UUID； publicclassbloomfiltertest { privatestaticfinalintnum=1000000； 创建用于存储publicstaticvoidmain (字符串[ ] args (/* *字符串)的光晕过滤器。 初始化大小为num，默认错误判定率为0.03。 如果可以这样写误判率，就可以写bloomfilterstringbloomfilter=(*/bloomfilterstringbloomfilter=bloom filter.create (funne 创建//过滤器和两个列表容器以验证他的错误率liststringlist=new ArrayList (num )； liststringlist1=新阵列列表(num )； for(intI=0； inum； I ) { String uuid=UUID.randomUUID ().toString )； bloomfilter.put(uuid； list.add(uuid； list1.add(uuid； (} int nums=0； int trueNum=0； //正确个数int wrongNum=0； //错误的个数for(intI=0； i10000； I({stringstr=I0==0？ list.get(I ) :UUID.randomUUID ).toString )； //布隆过滤器判断true时证明布隆过滤器承认存在if (bloom filter.might contain (str ) ) { nums； //而且，如果在list1中判断为list1也存在，则证明模糊滤波器的判断正确，相反判断错误if(list1.contains(str ) ) { trueNum； }else{ wrongNum； } } } System.out.println ('光晕滤波器检查的数量为' nums )； System.out.println ('正确个数为' trueNum ' )； System.out.println ('错误判定的数量为' wrongNum )； }这里介绍的是一个大致的原理性过程，但要实现它，必须在多个线程上初始化数据。 线程池化技术、锁定(布隆过滤器要求线程不安全)、线程协作等。 感兴趣的人可以了解Fork/Join。