五分钟搞懂布隆过滤器，亿级数据过滤算法值得拥有本文转载请联系知点码的公众号大叔。在正式讲解布隆过滤器之前，我们先来看一下这个业务场景：Redis是软件架构中常用的组件。最常见的用法是将热点数据缓存在Redis中，以减轻数据库的压力；常见的用法是：查询Redis，如果能查询到则直接返回，如果Redis中不存在则继续查询数据库。这种方式可以减少访问数据库的次数，但是“没有缓存的时候，查询数据库”，在高并发环境下还是有风险的。例如，90%的请求数据不在缓存中，那么这些请求将被丢弃。对于数据库来说，这就是缓存穿透。那么有没有办法解决这个问题呢？这个可以用【布隆过滤器】，可以判断“某条数据一定不存在”。01.Bloomfilter的概念Bloomfilter是由一个叫“Bloom”的人提出的，它本身就是一个很长的二值向量（想象成一个数组）和一系列随机映射函数（想象成多个Hash函数），其binaryvector要么存0，要么存1（在学习布隆过滤器之前，可以先了解一下BitMap算法，方便理解）。比如根据客户的手机号查询客户信息，通常会在缓存中设置手机号为Key。让我们设置一个长度为16的布隆过滤器。布隆过滤器初始化全为0；分别对13800000000进行hash1()、hash2()、hash3()运算，得到三个结果5、9、12，将对应位置置1；分别对18900000000进行hash1()、hash2()、hash3()操作，得到三个结果2、8、12，将对应位置置为1，现在2、5、8、9、12都为1，其余个元素为0；如果我们要验证某个电话号码是否存在，需要做什么呢？分别对13700000000进行hash1()、hash2()、hash3()运算，得到三个结果1、9、13，然后判断1、9、13位上的值是0还是1，如果是不全为1，说明13700000000不在布隆过滤器上；这就决定了“某数据一定不能存在”。当然，我们也可以看出布隆过滤器存在一个问题，就是不能保证数据一定存在。比如我们对18000000000进行hash1()、hash2()、hash3()运算，得到的结果分别是5、8、9，正好这三个位都是1，但实际上这个数据并不存在，所以布隆过滤器有一定的误判率；又因为运算后可能会有多个数据映射到同一个位置（138和189的运算结果都是12），所以很难删除布隆过滤器，除非为每一位加一个计数器，需要计数器删除时减1，直到counter为0才对应Bloomfilter，把位置改成0。02.特性总结可以判断一个元素不存在，但是不能判断一个元素存在;二值向量越长，映射函数越多，误报率越低；如果可以预先确定误报率，那么布隆过滤器的长度也是可以反转的；可以添加元素，但不能删除元素（除非增加计数器）；插入查询在存储空间和时间复杂度上有巨大的优势。回到本文开头的业务场景，为了防止缓存穿透，可以使用Bloomfilter过滤掉肯定不存在的数据。虽然误判的请求还是会放到数据库中，但是渗透率已经大大降低了。数量。03.手写一个BloomfilterCode不是目的，Coding的过程是为了加深理解。首先，我们需要定义一个位图。在JDK中，已经有对应的数据结构类java.util.BitSet：//设置布隆过滤器privateintDEFAULT_SIZE=1<<30;privateBitSetbitset;我们还需要一组映射函数，这里可以使用加法哈希函数设置6个素数，对应6个不同的哈希函数：//定义一个长度为6的素数数组，可以生成6个哈希函数用于随机映射privateint[]seeds={3,7,13,31,37,61};privateHashFunction[]functions=newHashFunction[seeds.length];在构造函数中初始化，设置BitSet的长度，生成映射函数:/***初始化*/publicBloomFilter(){bitset=newBitSet(DEFAULT_SIZE);for(inti=0;i
