BloomFilter——大规模数据处理利器
Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。
# t3 B' P- a6 Q/ N
一. 实例
为了说明Bloom Filter存在的重要意义，举一个实例：
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL，怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：
1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
4. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。
, j: J ]9 L) P }/ q 以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。
方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？
方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。
方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。
实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
2 a" F4 @ p8 d' L8 H, n9 B; Y二. Bloom Filter的算法
废话说到这里，下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高，为了降低冲突的概念，Bloom Filter使用了多个哈希函数，而不是一个。
Bloom Filter算法如下：
创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h（i，str），且h（i，str）的范围是0到m-1 。
) h Y1 Q" Y* G$ N7 c3 Z(1) 加入字符串过程
下面是每个字符串处理的过程，首先是将字符串str“记录”到BitSet中的过程：
对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后将BitSet的第h（1，str）、h（2，str）…… h（k，str）位设为1。
图1.Bloom Filter加入字符串过程
很简单吧？这样就将字符串str映射到BitSet中的k个二进制位了。
1 S+ `2 v& V2 e3 W(2) 检查字符串是否存在的过程
7 L3 }& l9 V+ ?' g2 S8 ^6 j
下面是检查字符串str是否被BitSet记录过的过程：
对于字符串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存在。
; w; `6 O7 F- ^% q* T/ x7 l( ` 若一个字符串对应的Bit不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）
但是若一个字符串对应的Bit全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive 。
& ? V9 g+ L! L6 p3 t! d(3) 删除字符串过程
字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。
9 C( r2 ^0 Y) i) V Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。
9 w& M5 n6 @* x2 F" s三. Bloom Filter参数选择
{+ R9 Q! P% e4 ?
(1)哈希函数选择
哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。
(2)Bit数组大小选择
哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考
参考文献1。该文献证明了对于给定的m、n，当 k = ln(2)* m/n 时出错的概率是最小的。
同时该文献还给出特定的k，m，n的出错概率。例如：根据参考文献1，哈希函数个数k取10，位数组大小m设为字符串个数n的20倍时，false positive发生的概率是0.0000889 ，这个概率基本能满足网络爬虫的需求了。
& B) ?- |+ K. `9 L4 W四. Bloom Filter实现代码
下面给出一个简单的Bloom Filter的Java实现代码：
+ U/ ]" T2 N: z$ m; }[url=]
[/url]
8 i( \' v! W/ [) n- F( i6 Yimport java.util.BitSet;. F+ d1 s- F6 ?$ g; f
7 [& i( U9 z7 U V+ {6 M
publicclass BloomFilter / h$ B/ a# z; E) v, E/ c, Z
{
7 o% d* I9 a3 S* u6 E/* BitSet初始分配2^24个bit */ " D. _* P: v5 t" I9 {1 r3 I
privatestaticfinalint DEFAULT_SIZE =1<<25; $ ?% L5 A0 I( ^8 |2 H" a
/* 不同哈希函数的种子，一般应取质数 */! O: C7 h2 l# l% z5 @% k
privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };$ _4 F6 i' G* b9 S
private BitSet bits =new BitSet(DEFAULT_SIZE);
7 F4 W7 y. ]; M6 I/ g6 j# l/* 哈希函数对象 */
2 j! Q. l; m! i7 U9 r2 y; e5 j& Oprivate SimpleHash[] func =new SimpleHash[seeds.length];
. N. q, L8 z1 I7 v# T- N6 A3 H3 ?7 X9 `
! x1 I/ Y9 O; C" k4 a" Ypublic BloomFilter()
; _* k" m- R" b. t{
$ X" Q# W" I" @& i7 V& `for (int i =0; i < seeds.length; i++)& [/ C9 ^& t) F3 ], p L2 t) P! u0 a
{
" q! N$ o# K& M8 \1 a' N0 i; |func =new SimpleHash(DEFAULT_SIZE, seeds);) o- T1 Q4 y, p: K
}/ ?1 [1 \5 g& r. ~
}& g q3 A* z% t( s
- [% y/ W7 D8 U
// 将字符串标记到bits中
% G* G) q2 c U: D$ Zpublicvoid add(String value)
+ e. C2 R, a( E2 W{5 I" a* B" ]3 c2 Z; K
for (SimpleHash f : func) / T4 T: h/ J$ p g* p1 k2 Z
{
/ T o% e: x% V6 fbits.set(f.hash(value), true);
3 m: X( m, H9 @9 |; S) h# q}$ D, ?& {1 H+ ?. |8 s
}3 {7 z) C5 c0 x
! w* A$ v. r; q5 P# t) A9 Q//判断字符串是否已经被bits标记
, m5 e8 l/ |( w) tpublicboolean contains(String value)
' }7 v/ ?; n* F0 H{- M& Z8 Y* t' s8 r0 B
if (value ==null) 4 S2 O1 P+ K/ Q% z
{- r% H0 v( s( \: V; G
returnfalse;
9 s' N ^8 M* r2 @, p}/ b- ?7 R1 F; D& H! f) \
boolean ret =true;! z7 O$ V8 h1 b3 {
for (SimpleHash f : func)
- V( p7 a9 {) k. X' P- P{' U4 B: I! f$ p8 Y# H4 d' m
ret = ret && bits.get(f.hash(value));
K7 M" d; E S* Y7 p3 `: V3 w1 s2 {}
: V* J5 n- _; S0 t; m9 A, Breturn ret;( V) w& K) Q/ M
}6 h! k1 E0 R; n) p/ y
" F n' b/ d) r7 w
/* 哈希函数类 */
* t8 j4 M9 Q ?publicstaticclass SimpleHash / Y& r7 j1 {% j" v# ~! q
{
3 [% }+ m1 m# h4 o4 a, u! bprivateint cap;
: e: B$ r+ Z% F% w; xprivateint seed;: W5 [+ P! p2 [ ^* a: S9 `' m; [
Z4 Y: e: B8 W3 r2 Q4 d$ v. ~public SimpleHash(int cap, int seed)
: G% h1 y6 f' C# B) ?) R! n" {! U3 d4 m{/ w9 m& D! [6 @0 z
this.cap = cap;
# B3 a6 G: p& [ U( j- Zthis.seed = seed;
1 ]$ K1 s: q1 y: H; }}
& ~7 r$ w+ H7 t& P$ ? t6 _7 G7 k. P+ Z- y) h, f6 D: c! ~
//hash函数，采用简单的加权和hash
" q% q. S n9 ~8 k/ M3 g H# a% Spublicint hash(String value) 9 c. F- G: Y+ r2 y3 d' A/ t
{
, N* g# X$ a; cint result =0;6 F$ b9 \$ C. }9 k5 D) C/ `+ M
int len = value.length();7 b; O% w2 L* A# P
for (int i =0; i < len; i++)
+ n2 ]- H! l2 {( Z! [* }/ G! U{1 l/ n* n# @( k0 r7 t. U1 h) Q
result = seed * result + value.charAt(i);/ a. Z& y0 X9 F7 j
}) _! |& N! ]) k3 P3 Z/ O
return (cap -1) & result;
2 W: l, u% t2 t9 u; j7 h}
3 e- _9 H r8 j" _9 e}
. z6 f1 S" G3 c4 Y+ p2 K5 {}) M/ I8 L! S9 @+ a9 ^; J% P
/ O* I# p" f& {
[url=][/url]
! L( k: V4 _: ]. V4 r V) [8 V- C' k4 }& T' ^
$ X5 P) S& V! f, L5 \+ R
+ ]- |7 Z$ M8 L
! g5 T2 Q) q1 n/ R) r; c$ e% q4 z
参考文献：
) B8 q0 h9 y. F2 H
[1]Pei Cao. Bloom Filters - the math.
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
[2]Wikipedia. Bloom filter.
9 E8 B$ |( W ~$ t& s
