布隆过滤器原理及应用

    可以采用如下几种方案：

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

    每次需要过滤网页就需要启用一个数据库select查询，且当数据量变得非常庞大后，关系型数据库查询的效率会变得很低。

    2、用HashSet将访问过的URL保存起来

    那只需接近O(1)的代价就可以查到一个URL是否被访问过了。但是内存消耗太大。

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

    字符串经过MD5散列处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。

    4、BitMap方法

    建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。

    布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。

    哈希表与布隆过滤器：

    哈希表也能用于判断元素是否在集合中，但是Bloom Filter只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。Bloom Filter可以插入元素，但是不可以删除已有元素。集合中的元素越多，误报率越大，但是不会漏报。

    可以利用Bitmap：只要检查对应点是不是1就可以知道集合中有没有这个数。Bloom filter可以看做是对bitmap的扩展。只是使用多个hash映射函数，从而减低hash发生冲突的概率。

    算法如下:

    1、创建m（m=28）位的bitset，初始化为0，选中k（k=3）个不同的哈希函数；

    2、第 i 个hash函数对字符串str哈希的结果记为 h(i,str)，范围是（0,m-1）；

    3、将字符串记录到bitset的过程（即插入）：对于一个字符串str，分别记录h(1,str)，h(2,str)…，h(k,str)，然后将bitset的h(1,str)，h(2,str)…，h(k,str)位置1，也就是将一个a映射到bitset的k个二进制位；

    4、检查字符串是否存在（即查找）：对于字符串astr，分别计算h(1,str)、h(2,str)，…，h(k,str)，然后检查bitset的第h(1,str)，h(2,str)，…，h(k,str) 位是否为1：

    若其中任何一位不为1则可以判定str一定没有被记录过；

    若全部位都是1，则“认为”字符串str存在；

    但是若一个字符串对应的Bit全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive ；

    5、删除字符串（删除）：字符串加入了就被不能删除了，因为删除会影响到其他字符串。

    Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。