布隆过滤器是什么？一起来瞅瞅！

<p style="text-indent:33px;"> 布隆过滤器，看名字就知道，不就是一个过滤器么！首先，过滤器大家都知道，像筛子啊，纱网啊等用来过滤大颗粒的工具。使用过滤器可以过滤一些不需要的东东，最终获取我们想要的。还记得某个矿泉水的广告么，全部工序经过20道以上的过滤流程！牛皮爆了！可能过滤沙子什么的也都算一层过滤吧！【微微一笑：呵呵】</p>
<p style="text-indent:33px;">前几天，看Redis方面的东西的时候，看到了一个结构，叫做BitMap，等看完之后，我打呼：好家伙，这不就是布隆过滤器的根子么！于是，我默默在心里打个箭头，指向了布隆过滤器。</p>
<p style="text-indent:33px;">来来来，先加个百度词条，秀点字数：</p>
<blockquote>
<p style="text-indent:33px;">布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的<a href="https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6/361457">二进制</a>向量和一系列随机映射<a href="https://baike.baidu.com/item/%E5%87%BD%E6%95%B0/301912">函数</a>。布隆过滤器可以用于<a href="https://baike.baidu.com/item/%E6%A3%80%E7%B4%A2/11003896">检索</a>一个元素是否在一个<a href="https://baike.baidu.com/item/%E9%9B%86%E5%90%88/2908117">集合</a>中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。</p>
</blockquote>
<p style="text-indent:33px;">这种词条解释，有些哥们可能不是很明白，咱们还是用通俗的话来说下。</p>
<p style="text-indent:33px;">布隆过滤器，简单来说就是过滤用的，怎么过滤呢？首先，我准备一段很大的数字段，比如从0到1亿，然后每个数字上都有一个对应的true和false值，默认的是false。然后我这边接收到一个请求，请求中有一个参数，比如Id。我要怎么过滤呢？首先，我先把数据库中所有的Id，多次求hash（先来3次吧），那么就会有3个hash值，接着，我就把这3个数字对应数字段上的值改成true，如果数据库有30万数据，我就求了90万次hash，然后把这些hash对应数字段上的值都改成了true，当然可能有重复的。（这个都是提前做好的，起码请求到来之前已经搞完了，嘿嘿。）</p>
<p style="text-indent:33px;">请求到来之后，我对请求的参数进行求hash，嗯，也是3次，然后从这个数字段上查看对应的值，如果是true，就让你过，如果有一个是false，那么对不起，你这个id明显不在数据库啊，爱哪哪去，爷不伺候了！</p>
<p style="text-indent:33px;">当然，求hash在某一数据段内也会有重复，也有可能来了一个数据，它特别幸运，虽然数据库中没有它，但是3次求hash上面的值都是true，它也从过滤器中溜了过去！</p>
<p style="text-indent:33px;">所以，布隆过滤器就有这么一个特性，存在的一定能通过，不存在的可能会通过。</p>
<p style="text-indent:33px;">大家这个时候不要抬杠哈，过滤器主要是针对负载、攻击进行一层拦截的，哪怕有一些漏网之鱼，最终经过代码的处理，对服务器或者DB的伤害几乎微不可查了，这种少量的数据处理，是可以接受的。</p>
<p style="text-indent:33px;">我们来看个简单的示意图：</p>
<p style="text-align:center;"><img alt="布隆过滤器示意图" height="300" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-bad1a4411c07b65626d4501a2dedc365.png" width="500"></p>
<p style="text-indent:33px;">如图，下面那个数据段就是我们提前准备好的，而且数据提前求hash，修改数据段中的true和false。当请求来的时候，根据求hash来判断是否对数据进行过滤。</p>
<p style="text-indent:33px;">好了，模型图已经出来了，我们要怎么实现呢？</p>
<p style="text-indent:33px;">难道创建一个数组？唉! 刚好哎，这个数据段不就是一个数组么？然后在数据里面写上true和false，这样功能不就实现了？</p>
<p style="text-indent:33px;">不错，功能是实现了，看示意图也能明白，这个数据段必须十分大，否则随随便便就填充满了，都是true，那么，还有啥过滤的必要？咱们不说多，就千万级吧！你确定要创建一个千万级别的数组或者说是list？先不说这个能不能很好的过滤攻击，就这个千万级别的数组，都够服务器受的！来来来，给你小算一下，Java中创建一个对象，咱们按照最小的算吧，也要16Byte，乘以千万，也就是1.6亶