赞
踩
https://www.jianshu.com/p/88c6ac4b38c8
布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组
和几个哈希函数
。假设位数组的长度为m,哈希函数的个数为k
以上图为例,具体的操作流程:假设集合里面有3个元素{x, y, z},哈希函数的个数为3。
首先将位数组进行初始化,将里面每个位都设置位0。
对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。
查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。
注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因。
如何选择哈希函数个数和布隆过滤器长度
过小的布隆过滤器
很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的
了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长
其误报率越小
。
另外,哈希函数的个数也需要权衡,个数越多
则布隆过滤器bit 位置位 1 的速度越快
,且布隆过滤器的效率越低
;但是如果太少的话
,那我们的误报率会变高
。
添加元素
查询元素
优点
1、存储空间和插入/查询时间都是常数
,远远超过一般的算法
2、Hash函数相互之间没有关系
,方便由硬件并行实现
3、不需要存储元素本身,在某些对保密要求非常严格
的场合有优势
缺点
1、有一定的误识别率
2、删除困难
应用
1、搜索引擎中的海量网页去重
2、leveldb等数据库中快速判断元素是否存在
,可以显著减少磁盘访问
。利用布隆过滤器减少磁盘 IO
或者网络请求
,因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。
import java.util.BitSet; /** * Created by haicheng.lhc on 18/05/2017. * * @author haicheng.lhc * @date 2017/05/18 */ public class SimpleBloomFilter { private static final int DEFAULT_SIZE = 2 << 24; private static final int[] seeds = new int[] {7, 11, 13, 31, 37, 61,}; private BitSet bits = new BitSet(DEFAULT_SIZE); private SimpleHash[] func = new SimpleHash[seeds.length]; public static void main(String[] args) { String value = " stone2083@yahoo.cn "; SimpleBloomFilter filter = new SimpleBloomFilter(); System.out.println(filter.contains(value)); filter.add(value); System.out.println(filter.contains(value)); } public SimpleBloomFilter() { for (int i = 0; i < seeds.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); } } public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } } public boolean contains(String value) { if (value == null) { return false; } boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; } public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } public int hash(String value) { int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。