(转载)BloomFilter——大规模数据处理利器

  • 时间:
  • 浏览:0

boolean ret =true;

}

for (int i =0; i < seeds.length; i++)

{

(1)加入字符串过程

若另另二个 字符串对应的Bit不全为1,则还需要肯定该字符串一定能也能了被Bloom Filter记录过。(这是显然的,肯能字符串被记录过,其对应的二进制位肯定全部被设为1了)

3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

(3)删除字符串过程

{

{

{

}

publicstaticclass SimpleHash

{

}

{

Bloom Filter算法如下:

下面是检查字符串str不是被BitSet记录过的过程:

{

创建另另二个 m位BitSet,先将所有位初始化为0,有后后 选用k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i,str),且h(i,str)的范围是0到m-1 。

privateint seed;

(2)检查字符串不是居于的过程

下面给出另另二个 简单的Bloom Filter的Java实现代码:

为了说明Bloom Filter居于的重要意义,举另另二个 实例:

.实例

}

. Bloom Filter实现代码

Bloom Filter跟单哈希函数Bit-Map不同之居于于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概率。

1. 将访问过的URL保存到数据库。

int result =0;

/* 哈希函数对象 */

int len = value.length();

}

this.seed = seed;

}

{

func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);

private BitSet bits =new BitSet(DEFAULT_SIZE);

result = seed * result + value.charAt(i);

publicint hash(String value)

{

. Bloom Filter参数选用

bits.set(f.hash(value), true);

if (value ==null)

privateint cap;

public SimpleHash(int cap, int seed)

{

假设要你写另另二个 网络蜘蛛(web crawler)。肯能网络间的链接错综冗杂,蜘蛛在网络间爬行很肯能会形成“环”。为了解决形成“环”,就需要知道蜘蛛肯能访问过有有哪些URL。给另另二个 URL,怎样知道蜘蛛不是肯能访问过呢?稍微想想,就会有如下几种方案:

{

最好的土办法2的缺点:太消耗内存。随着URL的增多,占用的内存会越多。就算能也能了1亿个URL,每个URL只算30个字符,就需要5GB内存。

对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。有后后 检查BitSet的第h(1,str)、h(2,str)…… h(k,str)位不是为1,若其中任何一位不为1则还需要判定str一定能也能了被记录过。若全部位全部都是1,则“认为”字符串str居于。

对于字符串str,分别计算h(1,str),h(2,str)…… h(k,str)。有后后 将BitSet的第h(1,str)、h(2,str)…… h(k,str)位设为1。

下面是每个字符串解决的过程,首先是将字符串str“记录”到BitSet中的过程:

延伸阅读:https://my.oschina.net/kiwivip/blog/133498

一齐该文献还给出特定的k,m,n的出错概率。例如于:根据参考文献1,哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive居于的概率是0.0000889 ,你这俩概率基本能满足网络爬虫的需求了。

/* BitSet初始分配2^2另另二个 bit */

return (cap -1) & result;

实质上底下的算法都忽略了另另二个 重要的隐含条件:允许小概率的出错,不一定要30%准确!也可是说极少量url实际能也能也能了没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几块网页呗。

}

原文链接:http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html

ret = ret && bits.get(f.hash(value));

哈希函数个数k、位数组大小m、加入的字符串数量n的关系还需要参考参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。

有后后 若另另二个 字符串对应的Bit全为1,实际上是能也能了30%的肯定该字符串被Bloom Filter记录过的。(肯能有肯能该字符串的所有位都刚好是被你这俩字符串所对应)你这俩将该字符串划分错的情形,称为false positive 。

最好的土办法3:肯能字符串经过MD5解决后的信息摘要长度能也能了128Bit,SHA-1解决后也能也能了130Bit,有后后 最好的土办法3比最好的土办法2节省了好几倍的内存。

public BloomFilter()

很简单吧?另另另二个 就将字符串str映射到BitSet中的k个二进制位了。

for (SimpleHash f : func)

private static final int[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };

Bloom Filter是由Bloom在1970年提出的你这俩多哈希函数映射的快速查找算法。通常应用在你这俩需要快速判断某个元素不是属于集合,有后后 越多严格要求30%正确的场合。

最好的土办法1~3全部都是将访问过的URL全部保存,最好的土办法4则只标记URL的另另二个 映射位。

. Bloom Filter的算法

}

return ret;

publicvoid add(String value)

}

废话说到这里,下面引入本篇的主角——Bloom Filter。随便说说底下最好的土办法4的思想肯能很接近Bloom Filter了。最好的土办法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而全部都是另另二个 。

for (SimpleHash f : func)

/* 哈希函数类 */

import java.util.BitSet;

(1)哈希函数选用

publicboolean contains(String value)

//hash函数,采用简单的加权和hash

// 将字符串标记到bits中

this.cap = cap;

最好的土办法4消耗内存是相对较少的,但缺点是单一哈希函数居于冲突的概率太高。还记得数据社会形态课上学过的Hash表冲突的各种解决最好的土办法么?若要降低冲突居于的概率到1%,就要将BitSet的长度设置为URL个数的30倍。

(2)Bit数组大小选用

for (int i =0; i < len; i++)

}

private SimpleHash[] func =new SimpleHash[seeds.length];

returnfalse;

/* 不同哈希函数的种子,一般应取质数 */

}

{

4. Bit-Map最好的土办法。建立另另二个 BitSet,将每个URL经过另另二个 哈希函数映射到某一位。

}

2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就还需要查到另另二个 URL不是被访问过了。

字符串加入了就被能也能了删除了,肯能删除会影响到你这俩字符串。随便说说需要删除字符串的还需要使用Counting bloomfilter(CBF),这是你这俩基本Bloom Filter的变体,CBF将基本Bloom Filter每另另二个 Bit改为另另二个 计数器,另另另二个 就还需要实现删除字符串的功能了。

最好的土办法1的缺点:数据量变得非常庞大后关系型数据库查询的数率会变得很低。有后后 每来另另二个 URL就启动一次数据库查询是全部都是太小题大做了?

privatestaticfinalint DEFAULT_SIZE =1<<25;

以上最好的土办法在数据量较小的情形下都能完美解决大大问题,有后后 当数据量变得非常庞大时大大问题就来了。

//判断字符串不是肯能被bits标记

publicclass BloomFilter

哈希函数的选用对性能的影响应该是很大的,另另二个 好的哈希函数也能近似等概率的将字符串映射到各个Bit。选用k个不同的哈希函数比较麻烦,你这俩简单的最好的土办法是选用另另二个 哈希函数,有后后 送入k个不同的参数。

图1.Bloom Filter加入字符串过程