Bloom Filter算法

Hash（函数/表）

Hash （中译为哈希，或者散列）函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面（这些小的数据集叫做哈希值，或者散列值）。Hash table（散列表，也叫哈希表），是根据哈希值(Key value)而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。下面是一个典型的hash函数/表示意图：

哈希函数有以下两个特点：

• 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。但也可能不同，这种情况称为“散列碰撞”（或者“散列冲突”）。上图中，John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类，比如上图，Hash值为0的表示可能在A集合中，Hash值为2的表示B集合中，依次类推，值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题，对于一个未知的新值，其可能不属于上面任何一个集合，但由于冲突，其Hash值和上面的某一个相同，导致误报（因为事先我们不可能做一个含有无限多项输入的完整的Hash表，也就是原来的Hash函数不可能是完美的）。并且，hash冲突也会导致查找效率低下。


Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，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或者属于这个集合，或者刚好是一个false positive。

最优的哈希函数个数

既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。

 

位数组的大小

下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为，下面我们来求位数组的位数m。

Bloom-Filter的应用。
        Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个 URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。 
      比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。  

     布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

     假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制位全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制位全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）   现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。 
      布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。 
      布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。


java实现这个算法 如下：
1、对每一个网址，用8个哈希函数生成8个keycode,然后把每个keycode代表的整数作为index，并将BitSet[index]的值置为1

->准确率和哈希函数的数量、使用内存的多少有关。单用一个哈希函数准确率太低了 ……

->例如：使用 11 个哈希函数时， 对 1 万个词的数据量，只需要 20k 的内存作 filter 就能达到错误率 0.1% 以下。 哈希函数用 CRC32 就行，选一个随机数 s，分别以 s, s+1, s+2, s+3, ... ,s+k-1 作为种子，那就得到 k 个哈希函数了。

package itcast.bloofilter;

import java.util.BitSet;

public class BloomFilter
{
         private static int defaultSize = 5000 << 10000;
        private int basic = defaultSize -1;
        private String key = null;
        private static BitSet bits = new BitSet(defaultSize);

        public BloomFilter(String key){
            this.key = key;
        }
        //将信息指纹置为1，bitset充当了再用一个随机数产生器 G
        private int changeInteger(int h) {
            return basic & h;
        }

        //八个不同的随机数产生器，用Q控制不同产生八个信息指纹
        private int hashCode(String key,int Q){
            int h = 0;
            int off = 0;
            char val[] = key.toCharArray();
            int len = key.length();
            for (int i = 0; i < len; i++) {
                h = (30 + Q) * h + val[off++];
            }
            return changeInteger(h);
        }

        private int[] lrandom(){
            int[] randomsum = new int[8];
            int random1 = hashCode(key,1);
            int random2 = hashCode(key,2);
            int random3 = hashCode(key,3);
            int random4 = hashCode(key,4);
            int random5 = hashCode(key,5);
            int random6 = hashCode(key,6);
            int random7 = hashCode(key,7);
            int random8 = hashCode(key,8);
            randomsum[0] = random1;
            randomsum[1] = random2;
            randomsum[2] = random3;
            randomsum[3] = random4;
            randomsum[4] = random5;
            randomsum[5] = random6;
            randomsum[6] = random7;
            randomsum[7] = random8;
            return randomsum;
        }
        private int[] sameLrandom(){
            int[] randomsum = new int[8];
            int random1 = hashCode(key,1);
            int random2 = hashCode(key,1);
            int random3 = hashCode(key,1);
            int random4 = hashCode(key,1);
            int random5 = hashCode(key,1);
            int random6 = hashCode(key,1);
            int random7 = hashCode(key,1);
            int random8 = hashCode(key,1);
            randomsum[0] = random1;
            randomsum[1] = random2;
            randomsum[2] = random3;
            randomsum[3] = random4;
            randomsum[4] = random5;
            randomsum[5] = random6;
            randomsum[6] = random7;
            randomsum[7] = random8;
            return randomsum;
        }
        private boolean exist(){
            int keyCode[] = lrandom();
            if(bits.get(keyCode[0])&&
                    bits.get(keyCode[1])
                    &&bits.get(keyCode[2])
                    &&bits.get(keyCode[3])
                    &&bits.get(keyCode[4])
                    &&bits.get(keyCode[5])
                    &&bits.get(keyCode[6])
                    &&bits.get(keyCode[7])){
                return true;
            }
            return false;
        }

        private void add(){
            if(exist()){
                System.out.println("已经包含("+key+")");
                return;
            }
            int keyCode[] = lrandom();
            bits.set(keyCode[0]);
            bits.set(keyCode[1]);
            bits.set(keyCode[2]);
            bits.set(keyCode[3]);
            bits.set(keyCode[4]);
            bits.set(keyCode[5]);
            bits.set(keyCode[6]);
            bits.set(keyCode[7]);
        }
        private boolean set0(){
            if(exist()){
                int keyCode[] = lrandom();
                bits.clear(keyCode[0]);
                bits.clear(keyCode[1]);
                bits.clear(keyCode[2]);
                bits.clear(keyCode[3]);
                bits.clear(keyCode[4]);
                bits.clear(keyCode[5]);
                bits.clear(keyCode[6]);
                bits.clear(keyCode[7]);
                return true;
            }
            return false;
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            BloomFilter f = new BloomFilter("");
            System.out.println(f.defaultSize);
            f.add();
           // f.set0();
            System.out.println(f.exist());
            BloomFilter f2 = new BloomFilter("");
            System.out.println(f2.defaultSize);
            f2.add();
            System.out.println(f2.exist());
            //f.set0();

        }


}

 输出：

327680000
true
327680000
已经包含(http://)
true

【适用范围】可以用来实现数据字典，进行数据的判重，或者集合求交集 【基本原理及要点】

　　对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。 

　　还有一个比较重要的问题，如 何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。 

　　举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。 

　　注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。现在，用位数代表了个数（每一个数可能是字符串，或者其他类型）所以使用bloom filter内存上通常都是节省的。