有过搜索经验的同学们都知道，当进行网页抓取的时候都会遇到url排重的问题，当然这也是面试经常遇到的问题，同学们可能会想到很多的方法去解决这个问题，比如用数据库，kv系统，bitmap等等，但是都由于种种问题不能完全的解决掉排重的问题，数据库在大数据量和高访问量的时候往往会不尽人意，kv库会很耗内存，bitmap会出现很高的冲突率，这时候bloomfilter就成为了很好的选择，一方面是基于内存的具有很高的性能，而且耗费内存不高，另一方面它的错误率（假阳概率：判断存在，但实际上不存在）比较低，这样就可以满足我们的需求了，可以采用bloomfilter加kv数据库的形式实现100%的准确，但有时非必要。
Bloom Filter的算法
Bloom filter是一个时间效率很高的随机访问结构，它包含一个m位的bit数组，使用k个独立的hash函数，它们分别将集合N中的每个元素映射到{1...m}的范围内，在判断一个元素是否属于集合N时，使用这k个hash函数进行验证，当所有hash函数映射的bit全部是1时，认为该元素属于集合N，否则认为元素不属于集合N，当然这存在假阳的现象，也就是说元素实际上不属于集合N，但是被判断属于集合N，这是由于存在某个bit有可能被其他的元素置1。
对于元素i，分别计算h1（i），h2（i）…… hk（i）。然后将BitSet的第h1（i）、h2（i）…… hk（i）位设为1。
图1.Bloom Filter加入字符串过程
错误率估计：
M位的bitset中，某一位被置1的概率为1/m，那么没被置1的概率为（1-1/m），k个hash函数映射n个元素总计需要对k*n个位置1，那么k个hash函数映射n个元素后，m位的bitset中，某位仍然为0的概率为（1-1/m）^kn约等于e^(-kn/m)，则错误的概率为（1-e^(-kn/m))^k
最优hash函数个数：
当e^(-kn/m) = 1/2时，出错概率为最低，即当k=ln(2) *(m/n)时出错率最低，这时错误率为（1/2）^k = 0.6189 ^(m/n)
位数组大小的选择：
给定错误率E，可以推算出当m>n * log2(1/E)时，错误概率f不会超过E,上面我们已经推算出k=ln(2) *(m/n)时出错率最低，为了让错误率在hash函数的最优解时错误率不会超过E，m>= log2(e) * (n*log2(1/E))，这个值是正常情况下m最小值的1.44倍。
Hash函数的选择
Hash函数k = ln(2)* m/n时，错误率最低0.6185^m/n，例如哈希函数个数k取10，位数组大小m设为字符串个数n的20倍时，false positive发生的概率是0.0000889，hash函数的选择应该使得同一个元素的hash值分布的尽量的分散，减少这K个hash函数的冲突率，最简单的方式是使用同一个hash函数，但这个hash函数使用不用的k个参数。
从以上对基本原理和数学基础的分析，我们可以得到Bloom filter的如下基本特征，用于指导实际应用。
(1)存在一定错误率，发生在正向判断上（存在性），反向判断不会发生错误（不存在性）；
(2)错误率是可控制的，通过改变位数组大小、hash函数个数或更低碰撞率的hash函数来调节；
(3)保持较低的错误率，位数组空位至少保持在一半以上;
(4)给定m和n，可以确定最优hash个数，即k = ln2 * (m/n)，此时错误率最小；
(5)给定允许的错误率E，可以确定合适的位数组大小，即m >= log2(e) * (n * log2(1/E))，继而确定hash函数个数k；
(6)正向错误率无法完全消除，即使不对位数组大小和hash函数个数进行限制，即无法实现零错误率；
(7)空间效率高，仅保存“存在状态”，但无法存储完整信息，需要其他数据结构辅助存储；
(8)不支持元素删除操作，因为不能保证删除的安全性。
如何确定一个bloom filter
1、选择bit数组的大小m
2、根据m和n计算最优解k（ (m/n)ln(2)）
3、计算错误率，看错误率是否满足要求，如果不满足，返回1重新计算
Reference：
http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html