手写一个简易的布隆过滤器

1.什么是布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
人话理解就是，布隆过滤器是一个容器，我们可以往这个容器里添加元素，并且可以查询某个元素是否在容器中存在，欸有人就经验的可以知道，这个工作Set也可以做，为什么要用布隆过滤器呢，

布隆过滤器的优点：
时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
保密性强，布隆过滤器不存储元素本身
占用空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）
布隆过滤器的缺点：
有点一定的误判率，但是可以通过调整参数来降低
无法获取元素本身
很难删除元素（可以试试自己实现一个可以删除元素的某隆过滤器）

2. 布隆过滤器的使用使用场景

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在（误判，后续会讲），**利用这个判断是否存在的特点可以做很多有趣的事情。

解决Redis缓存穿透问题（面试重点）
邮件过滤，使用布隆过滤器来做邮件黑名单过滤
对爬虫网址进行过滤，爬过的不再爬
解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
HBase\RocksDB\LevelDB等数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求

实现原理

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
我下面的实现是采用了二维数组的方式来实现的，一个hash函数对应每一个数组，这样的误判率会非常小，当然每个人都有自己的实现方式，学习思想即可

代码实现

1.定义接口

public interface AccessInterface<T extends Object> {void add(T t);boolean query(T t);boolean set(T t);
}

2.hash值方法实现

public class HashCode<T extends Object> {/*** @param index* @param length* @param t* @return* 注：适用于hashpool较小的时候，，太大了不行。计算hash值的时候会溢出，当然这个问题换个对象来计算就行了，这里图省事就简单点， Java有内置的大数据对象。*/public int GetHashCode(int index,int length,T t){int hashcode=t.hashCode();Long hashcode1=Math.round(Math.floor((hashcode+index+index*index)%length));return hashcode1.intValue();}}

过滤器实现

/*** 过滤器实现*/
public class BlloomEnity<T extends Object> implements AccessInterface<T> {private boolean[][] blloompool;private int length;HashCode<T> Code;public BlloomEnity() {this.length=100;this.blloompool=new boolean[100][100];this.Code=new HashCode<T>();}public BlloomEnity( int length) {this.blloompool = new boolean[length][length];this.length = length;this.Code=new HashCode<T>();}@Overridepublic void add(T o) {for(int i=0;i<this.length;i++){int k=Code.GetHashCode(i+1,this.length,o);this.blloompool[i][k]=true;}}@Overridepublic boolean query(T o) {for(int i=0;i<this.length;i++){int k=Code.GetHashCode(i+1,this.length,o);if(!this.blloompool[i][k]){return false;}}return true;}@Overridepublic boolean set(T o) {if(query(o)){return false;}else{add(o);}return true;}
}