今天一个不小心看了一下bloom filter,做了一下总结。
原理
其实很简答,但是很聪明。
维基里面有个下例子的图,对这个问题讲的很清楚
对于一个元素,判断它是否存在于集合内,我们用不同的hash算法去算他,比如有3个,假设每一个算出来都是一个数吧,以这个数为下标,我们就把位数组里面相应的数设置为1,因为位数组只能设置为0或者1。3个hash函数算完后,我们得到三个下标,看着三个下标里面的元素是否是1,是1就在里面,如果有一个为0就不在里面。插入的方式也就是将相应的下标设置为1。
总的来说,bloom filter以低概率的错误(将“不在”集合内的元素判定为“在”)换取时间和空间。
优点
详见他人博客,我总结的有两点:
- 具有很好的空间和时间效率(只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题)
- 不存在false negative (漏报),就是说如果元素存在的话,必能得到正确的结果
缺点
参考了一篇博客,我总结有两点:
- 不能删除已储存的元素
- 元素越多,false positive rate(误报率)越大,也就说将不存在的元素判定为存在。(常见的补救方法:增加一个白名单,存储可能被误判的元素)
应用
参考了一篇博客,比如:
- 垃圾邮件过滤中的黑白名单
- 爬虫(Crawler)的网址判重模块
下面详细的阐述一个例子,先是插入:
- 为了存储一亿个电子邮件地址
- 建立一个含有十六亿二进制比特,也就是两亿字节
- 将十六亿的比特全部设置为0
- 我们用八个不同的哈希函数,以电子邮件地址为键,算出值,有8个(也许不是数字)
- 我们再一个哈希函数,分别以这8个值为键,会得到8个数值(范围为1到十六亿的某个数字)
- 以上一步算出的8个数值为下标,将这8个位置的二进制都设置为1(存储了一个地址)
查询时只需要用类似的方法得到相应电子邮件的8个数值,以其为下标看二进制是否都设置为了1,如果设置为了1,那么这个电子邮件就存在在这个表中。
实现代码
java代码,参考了一篇博客(http://www.cnblogs.com/hitwtx/archive/2011/08/24/2152180.html)
我做了一些较大的修改和添加了全部注释,有两个类:bloomFilter和element
import java.util.BitSet; /** * 就是这个过滤器,有插入、查询等功能,可以设置位集的大小。虽然有删除功能,但是最好不要用 * @author chouyou * */ public class bloomFilter { private int defaultSize = 5000 << 10000;// <<是移位运算 /** * 从basic的使用来看,hashCode最后的结果会产生一个int类型的数,而这个int类型的数的范围就是0到baisc * 所以basic的的值为defaultsize减一 */ private int basic = defaultSize -1; private BitSet bits = new BitSet(defaultSize);//初始化一个一定大小的位集 public bloomFilter(){ } /** * 针对一个key,用8个不同的hash函数,产生8个不同的数,数的范围0到defaultSize-1 * 以这个8个数为下标,将位集中的相应位置设置成1 * @return */ private int[] indexInSet(element ele){ int[] indexes = new int[8]; for (int i = 0;i<8;i++){ indexes[i] = hashCode(ele.getKey(),i); } return indexes; } /** * 添加一个元素到位集内 */ private void add(element ele){ if(exist(ele)){ System.out.println("已经包含("+ele.getKey()+")"); return; } int keyCode[] = indexInSet(ele); for (int i = 0;i<8;i++){ bits.set(keyCode[i]); } } /** * 判断是否存在 * @return */ private boolean exist(element ele){ int keyCode[] = indexInSet(ele); if(bits.get(keyCode[0]) &&bits.get(keyCode[1]) &&bits.get(keyCode[2]) &&bits.get(keyCode[3]) &&bits.get(keyCode[4]) &&bits.get(keyCode[5]) &&bits.get(keyCode[6]) &&bits.get(keyCode[7])){ return true; } return false; } /** * 要进行集合删除某个元素 * 那么在位集中将相应的下标设置为0即可 * 但是这样岂不是有可能会让影响到别的元素,因为多个元素公用一个下标呀 * 那样岂不是让别的元素也不存在了么 * 经查证,这就是bloom Filter的缺点,不能删除元素。 * @return */ private boolean deleteElement(element ele){ if(exist(ele)){ int keyCode[] = indexInSet(ele); for (int i = 0;i<8;i++){ bits.clear(keyCode[i]); } return true; } return false; } /** * Q传入不同的Q就可以得到简单的不同的hash函数 */ private int hashCode(String key,int Q){ int h = 0; int off = 0; char val[] = key.toCharArray(); int len = key.length(); for (int i = 0; i < len; i++) { h = (30 + Q) * h + val[off++]; } return changeInteger(h); } private int changeInteger(int h) { return basic & h;//&是位与运算符 } public static void main(String[] args) { // TODO Auto-generated method stub bloomFilter f=new bloomFilter(); element ele = new element("blog.csdn.net/zy825316"); System.out.println("位集大小:"+f.defaultSize); f.add(ele); System.out.println(f.exist(ele)); f.deleteElement(ele); System.out.println(f.exist(ele)); } }
/** * 位集里面的每一个元素 * @author chouyou * */ public class element { private String key = null; public element(String key){ this.setKey(key); } public String getKey() { return key; } public void setKey(String key) { this.key = key; } }
代码结果:
位集大小:327680000
true
false
工程已经打包上传至网盘:
- BloomFilterDemo.rar