Java实现布隆过滤器的几种方式

布隆过滤器应用场景：

为预防大量黑客故意发起非法的时间查询请求，造成缓存击穿，建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数（哈希函数）来记录与识别某个数据是否在一个集合中。如果数据不在集合中，能被识别出来，不需要到数据库中进行查询，所以能将数据库查询返回值为空的查询过滤掉。

缓存穿透： 缓存穿透是查询一个根本不存在的数据，由于缓存是不命中时需要从数据库查询，这将导致这个不存在的数据每次请求都要到数据库去查询，进而给数据库带来压力。

1 介绍

概念：布隆过滤器（Bloom Filter）： 1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列的随机映射函数（哈希函数）两部分组成的数据结构。

用途： 用于检索一个元素是否在一个集合中。

优点：

时间复杂度低，增加及查询元素的时间复杂度都是O(k)，k为Hash函数的个数；
占用存储空间小，布隆过滤器相对于其他数据结构（如Set、Map）非常节省空间。
缺点：

存在误判，只能证明一个元素一定不存在或者可能存在，返回结果是概率性的，但是可以通过调整参数来降低误判比例；
删除困难，一个元素映射到bit数组上的k个位置为1，删除的时候不能简单的直接置为0，可能会影响到其他元素的判断。

2.布隆过滤器的原理

当一个元素加入布隆过滤器中的时候，会进行如下操作ÿ