常德交通网站,西南交通建设集团股份有限公司网站,o2o网站开发公司,房产官网查询系统1.什么是布隆过滤器
布隆过滤器#xff08;Bloom Filter#xff09;是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多#xff0c;…1.什么是布隆过滤器
布隆过滤器Bloom Filter是1970年由布隆(人名)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多缺点是有一定的误识别率和删除困难。 人话理解就是布隆过滤器是一个容器我们可以往这个容器里添加元素并且可以查询某个元素是否在容器中存在欸有人就经验的可以知道这个工作Set也可以做为什么要用布隆过滤器呢
布隆过滤器的优点 时间复杂度低增加和查询元素的时间复杂为O(N)N为哈希函数的个数通常情况比较小 保密性强布隆过滤器不存储元素本身 占用空间小如果允许存在一定的误判布隆过滤器是非常节省空间的相比其他数据结构如Set集合布隆过滤器的缺点 有点一定的误判率但是可以通过调整参数来降低 无法获取元素本身 很难删除元素可以试试自己实现一个可以删除元素的某隆过滤器
2. 布隆过滤器的使用使用场景
布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”也就是说布隆过滤器说这个数不存在则一定不存布隆过滤器说这个数存在可能不存在误判后续会讲**利用这个判断是否存在的特点可以做很多有趣的事情。
解决Redis缓存穿透问题面试重点邮件过滤使用布隆过滤器来做邮件黑名单过滤对爬虫网址进行过滤爬过的不再爬解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)HBase\RocksDB\LevelDB等数据库内置布隆过滤器用于判断数据是否存在可以减少数据库的IO请求
实现原理
布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例Redis中的布隆过滤器底层是一个大型位数组二进制数组多个无偏hash函数。 我下面的实现是采用了二维数组的方式来实现的一个hash函数对应每一个数组这样的误判率会非常小当然每个人都有自己的实现方式学习思想即可
代码实现
1.定义接口
public interface AccessInterfaceT extends Object {void add(T t);boolean query(T t);boolean set(T t);
}2.hash值方法实现
public class HashCodeT extends Object {/*** param index* param length* param t* return* 注适用于hashpool较小的时候太大了不行。计算hash值的时候会溢出当然这个问题换个对象来计算就行了这里图省事就简单点 Java有内置的大数据对象。*/public int GetHashCode(int index,int length,T t){int hashcodet.hashCode();Long hashcode1Math.round(Math.floor((hashcodeindexindex*index)%length));return hashcode1.intValue();}}过滤器实现
/*** 过滤器实现*/
public class BlloomEnityT extends Object implements AccessInterfaceT {private boolean[][] blloompool;private int length;HashCodeT Code;public BlloomEnity() {this.length100;this.blloompoolnew boolean[100][100];this.Codenew HashCodeT();}public BlloomEnity( int length) {this.blloompool new boolean[length][length];this.length length;this.Codenew HashCodeT();}Overridepublic void add(T o) {for(int i0;ithis.length;i){int kCode.GetHashCode(i1,this.length,o);this.blloompool[i][k]true;}}Overridepublic boolean query(T o) {for(int i0;ithis.length;i){int kCode.GetHashCode(i1,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;}
}测试 完事儿一切对象都可存
