布隆过滤器（BloomFilter）是年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
简单来说就是：当我们通过布隆过滤器判断一个元素在不在集合中时；如果布隆过滤器返回的是在集合中，那么集合中可能没有这个元素；如果布隆过滤器返回的不存在于集合中，那么集合中是一定不存在这个元素的。
TRAVEL布隆过滤器算法分析
下面通过一个简要例子和图例来对布隆过滤器进行简要的说明。
假如现在有10亿个数组成的集合M（数的范围在1~10亿之间），现在新来一个数x，那么该如何快速的判断这个数在不在集合中？同时又需要尽量的节约内存呢？
如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢，同时这些数据实际我们几乎就不会用，仅仅是想知道一个元素在不在一个集合中。由此诞生了散列表（又叫哈希表，Hashtable）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bitarray）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
TRAVEL消耗空间分析
传统方案：将集合M的数用散列表保存，然后对数x判断是否在散列表中即可；内存计算：假设使用int类型来保存，那么10亿个数消耗的内存=4byte(int)*10亿≈M。
位图方案：由于我们只关心数x是否存在于集合中，因此我们通标记0和1来标记，通下标来表示数；即开辟空间使用byte数组来保存，那么10亿个数消耗的内存=1byte*10亿≈95M。
上面看去视乎消耗不大，那么我们现在将数据量扩大10倍，即有亿个数，此时传统方案大约需要3.7G；使用位图的方案大约需要0.9G。
想想我们服务器的内存才多少个G，而这个还仅仅只是这个Java程序中的一个Java对象，同时其他外在因素都未考虑进去，而我们这仅仅是系统中一个小小的判断是否存在的功能；无论是使用位图方案还是传统方案都不是太符合要求。
PS.不要觉得10亿数据很多；假如公司的一个业务有万用户，平均每个用户一天产生10条数据，一个月(30天)就是1.5亿条数据，那么一年就是18亿条数据；而这只是一个业务功能中的一个表，如果有多个的话…
TRAVEL布隆过滤器的设计方案
通过上面的内存消耗分析，我们知道需要对方案进行优化；而布隆过滤器正是在位图方案的基础上进行优化设计。它的设计方案如下：
对于亿个数的要求，我们开辟一个10亿的空间大小；当放入一个数x(判断的时候也类似)，通过几种不同的hash算法计算这个数x的hash值，然后将这几个hash值对应的小标置为1。就像下面这样：
当多个值进入的时候：
从上面的图中可以发现传统的散列表设计使用一个hash的话，会出现hash冲突；因此在布隆过滤器中选择使用多种不同的hash算法得到多个hash值，有多个hash值来定位一个数的位置，这样就可以有效的减小hash冲突的概率了。
但是由于其散列表的基础特性依旧没有突破，因此会依然会存在误判的可能（从图中可以很容易的发现），这也就就是布隆过滤器的特性总结一句话就是：
告诉你没有那是真的没有；告诉你有可能是有，也可能是没有。你细品…像不像你问你女票的时候的情况，区别就布隆过滤器说没有那是真的没有
因此布隆过滤器适合的场景是对误判有一定容忍度的场景，比如说：垃圾邮箱、钓鱼网址、URL地址判重（比如爬虫）、海量图库判重、推荐算法（比如新闻资讯这些推荐给用户，但是需要将用户看过的去掉，如果通过数据库里面的历史记录来去重，时间久了数据量会很大…）
引入布隆过滤器后，也会带来新的问题，导致将系统业务复杂化。正所谓‘鱼与熊掌不可兼得’；因此需要仔细思量。
TRAVEL说了那么开始showcode，下面通过一个基于redis来实现布隆过滤器，对无效的参数请求过滤，缓存穿透的解决方案。
publicclassRedisBloomFilterT{privatefinalRedisTemplateString,TredisTemplate;privatefinalStringkey;privatefinalintcapacity;privatefinalintnumHashFunctions=2;publicRedisBloomFilter(Stringkey,RedisTemplateString,TredisTemplate,intn,doublep){this.redisTemplate=redisTemplate;this.key=key;this.capacity=calculateCapacity(n,p);}publicvoidput(Tvalue){int[]hash=index(value);for(inti=1;i=numHashFunctions;++i){int