布隆过滤器——Bloom Filter

 

谷歌的数学之美系列曾经提到过一种数据结构叫做bloomfilter，翻译成中文就是布隆过滤，文中使用布隆过滤器来过滤黑名单。后来我在毕业设计中也用到了它来过滤重复的URL，避免网络爬虫重复抓取。再后来在单位又一次的用到了bloomfilter来过滤用户的重复访问。随着海量数据时代的到来，布隆过滤器应用的场景越来越多。

布隆过滤器（Bloom Filter）是1970年由Burton Howard Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

 

为了表达S={X1, X2,…,Xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素X，第i个哈希函数映射的位置Hi(X)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。  

 

 

在判断Y是否属于这个集合时，我们对Y应用k次哈希函数，如果所有Hi(Y)的位置都是1（1≤i≤k），那么我们就认为Y是集合中的元素，否则就认为Y不是集合中的元素。下图中Y1就不是集合中的元素。Y2或者属于这个集合，或者刚好是一个误判。

应用布隆过滤器时，只需要由用户决定要容纳的元素数n和希望的误判率p。然后通过以下公式：

计算出位数组的长度m，然后通过m，n计算出哈希函数的个数k。

 

布隆过滤器的优劣主要与哈希函数的质量相关，而且哈希函数之间的相关度越小越好，每个哈希函数本身的计算过程不要太复杂，不然会影响效率。理想情况下是取k个完全不相关的哈希函数，在不是很严格情况下，也可以通过一个哈希函数的参数变化产生k个不同的哈希函数，比如将i（1≤i≤k）作为参数参与哈希函数的计算。

不同的应用场景，哈希函数的设计方法不同，没有通用的规律可循。在网络爬虫的设计中，我才用了MD5算法最为基础来构造哈希函数：

for (int i = 0; i < funNum; i++){ //输入URL地址拼接上Hash函数的编号 String input = url+i.toString(); //散列值取MD5摘要的后64位与比特向量大小的的余数 hash =(long)Md5(input).getLast64bit() % (long)bitSetSize; }

 

在过滤用户时，由于用户ID是一个long型数据，因此用随机数函数random()效率更高。下面是long类型bloomfilter的完整实现。

 

import java.io.Serializable; import java.util.BitSet; import java.util.Random; /** * Long类型元素的布隆过滤器 */ public class BloomFilter implements Serializable { private static final long serialVersionUID = 1L; public static final int ELEM_NUM = 1000; // 欲容纳的元素个数 public static final double PERCENTAGE = 0.001; // 希望的误差率 private int hashNum; // hash函数的数量 private int size; // 位向量的長度 private BitSet bitVecter; // 位向量 public BloomFilter() { size = (int) Math.abs(ELEM_NUM * Math.log(PERCENTAGE) / (Math.log(2) * Math.log(2))) + 1; hashNum = (int) (Math.log(2) * ((double) size / ELEM_NUM)); bitVecter = new BitSet(size); } /** * 查找元素是否在集合中 */ public boolean search(Long elem) { boolean flag = true; int temp; Random random = new Random(elem); for (int i = 0; i < hashNum; i++) { temp = random.nextInt(size); if (!bitVecter.get(temp)) {// 元素不在集合中 bitVecter.set(temp); flag = false; } } return flag; } /** * 获取位向量的长度 */ public int size() { return bitVecter.size(); }

 

public int getHashNum() { return hashNum; } public void setHashNum(int hashNum) { this.hashNum = hashNum; } public int getSize() { return size; } public void setSize(int size) { this.size = size; } public BitSet getBitVecter() { return bitVecter; } public void setBitVecter(BitSet bitVecter) { this.bitVecter = bitVecter; } }