两个算法经常用于大数据规模下的去重，压缩，判断是否存在（避免直接扫描磁盘），排序等情况。海量数据的查询，判断是否存在，我们没法直接使用内存存储全部的数据，毕竟内存有限。

两者算法适用于对海量数字的判断，对于非数字的数字，可以通过其他方法映射为数字类型。

既然是数字，不直接存储到内存中，我们可以借助bit位来描述，在一个包含bit位的数组中，每一个bit位都表示一个数字，即，第零位置如果是1表示1，第一位置如果是1表示1，第三位置为1表示2......，当然位置为0表示不表示任何数，或者说，那个位置对应的数字不存在。上述方式类似hash的方式，key是bit数组中的位置，位置0,1,2...，每个位置都表示一个数，下标表示数，value是位置上0或者1，1表示数字存在，反之，0表示不存在。

Bitmap

参照博客。
[bitmap]http://www.cnblogs.com/senlinyang/p/7885685.html
如上述描述那样，通过bit数字模拟hash，如果给定的数字范围能够通过内存中的bit数组表示出来，则次方法就是bitmap。

假设，有5个数字，4,7,2,5,3，可以使用8个bit为来表示，毕竟，8个bit位的最大下表是7，足够了
0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 从左到右输出，即为排序。

那么，使用多大的bit数组来表示给定的数据范围呢？先通过例子分析，假定给定数据组，最大数为N=100000000，采用int数组来表示bit位数组，1个int是32个bit，那么一共需要int数组的大小为，1 + N/32，即需要申请int a[1 + N/32]数组。这个a数组可表示的数据范围如下，
a[0]-----------------------------> 0 - 31 注意，a[0]是32bit 下标0-31，表示0到31数字，以此类推
a[1]------------------------------> 32 - 63
a[2]-------------------------------> 64 - 95
a[3]--------------------------------> 96 - 127
....................................................
给定一个下标（或者理解为给定的数字），如何计算该下标属于int数组的第一个元素，以及在该元素中的第一个位置（ 将a理解为bit的2维数组，即byte[][] a = new byte[1 + N/32][8]{} ）。

考虑图中，0,32,64,96，发现只要下标整除32得到的值x即可得到属于a[x]，
考虑图中，1,32,65,96，对应的结果为，a[0][1]，a[1][1]，a[2][1]，a[3][1]，可以推断，下标模除32得到的值y就是在第a[x]数组的第y个位置。

结论，下标n所谓位置，a[n/32][n%32]

但是a毕竟不是二维数组，那么可以通过位操作来实现。
a[n/32] 定位int数组第几号元素。a[n/32]=>a[n>>5]，
拿到第a[n>>5]后，将第n%32个位置设置为1，其余位置不变，明显是与或运算。n%32 等于 n & 0x1F（其中，0x1F是通过，2的N次方等于32，N=5，即保留后5位，第n%32个位置，需要将1向左移动n & 0x1F位置。

最终，位运算为a[n>>5] |= 1 << (n & 0x1F)，此公式是设置int数组某一位为1，表示对应的下标存在。

公式直接拿人家的吧。

public class BitMap {

    private static final int N = 10000000;

    private int[] a = new int[N/32 + 1];

    /**
     * 设置所在的bit位为1
     * @param n
     */
    public void addValue(int n){
        //row = n / 32 求十进制数在数组a中的下标
        int row = n >> 5;
        //相当于 n % 32 求十进制数在数组a[i]中的下标
        a[row] |= 1 << (n & 0x1F);
    }

    // 判断所在的bit为是否为1
    public boolean exits(int n){
        int row = n >> 5;
        return (a[row] & ( 1 << (n & 0x1F))) == 1;
    }

    public void display(int row){
        System.out.println("BitMap位图展示");
        for(int i=0;i<row;i++){
            List<Integer> list = new ArrayList<Integer>();
            int temp = a[i];
            for(int j=0;j<32;j++){
                list.add(temp & 1);
                temp >>= 1;
            }
            System.out.println("a["+i+"]" + list);
        }
    }

    public static void main(String[] args){
        int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
        BitMap map = new BitMap();
        for(int i=0;i<num.length;i++){
            map.addValue(num[i]);
        }

        int temp = 120;
        if(map.exits(temp)){
            System.out.println("temp:" + temp + "has already exists");
        }
        map.display(5);
    }
}

Bloom过滤器

Bitmap不是万能的，比如说，上述例子N很大，大到内存无法放下一个bitmap，如何？
此时，另一个解决方案，bloom过滤器诞生，当然bloom过滤不是解决bitmap压缩，排序等场景问题。bloom过滤器可以解决判断是否存在的问题，它是如何突破bitmap很大内存无法放下的限制？

如果说Bitmap对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，那布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。通俗讲，bloom过滤器就是三个hash函数，在给定的bit空间上连续判断三次是否存在，即是否对应的bit位是否为1。只是这个bit空间不同于bitmap足够，而是不使用足够的bit空间，在允许一定错误的情况下，来判断。

算法如下，
算法：

1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1

4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

   
   bloom过滤器图解

缺点：

1. 如果判定为存在，则实际情况下可能不存在，False positives。
2. 无法删除

备注：bloom过滤没有False negatives问题，即如果过滤器判定为不存在，则实际集合中就真不存在。这里需要理解下False positives和False negatives，二者都是false，都是错误的判断，False positives意思就是认为是这样的，其实不是这样的，而False negatives意思是认为不是这样的，其实是这样的。

考虑False positives误算率，如果这个能够容忍，那么bloom过滤器就可以实施。
假定，k是hash函数的个数，m个bit数组的大小，n表示元素个数。

从False positives出发，某个位置应该为0，但是被设置为了1.

n个数据只要有任何一个设置为1，则结果就是1，计算概率，反向算比较容易，即考虑设置为0的概念。bit数组的某一位设置为0的概率如下（1/m表示某位设置为1的概率），

k次hash函数之后，该位仍然是0的概率，

插入n个数后，仍然是0的概率，

所以，该位为1的概率是，

检验某个元素是否在集合中，k个位置上都是为1的概率是，

根据中心极限定理，


最后，得到，

上述结果是在假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立为前提计算出来的，不难看出，随着 m （位数组大小）的增加，假正例（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升。

求ε的最优解，当且仅当，

此时False Positives的概率为，

而对于给定的False Positives概率 p，如何选择最优的位数组大小 m为，

上式表明，给定位ε的时候，数组的大小最好与插入元素的个数成线性关系。

综上所示，m，n，k，p的关系一目了然。

bloom过滤器例子

假定，一个数据类型是64bit构成，可以看到，如果使用bitmap存储的话，需要多大内存？计算过程，64bit，最大数据为 ，

根据bitmap公式，可以得到需要内存数为（假定使用bit作为存储单元），

等于，

显然，以目前的内存无法胜任。bloom过滤器不考虑数据的最大值，因为它不同于bitmap那样需要存储每一个值，相反的，bloom过滤器考虑通过概率方式，将一个数值经过多次散列后，定位bit数组位置进行标记，通过这个多次标记的结果来判定是否存在这个数据，它考虑的是数据的元素个数n，只要保证这n个数据，能够在m个bit位上经过k次散列标记后，得到最小的误差即可！，就想下图描述这样，将w数据经过三次散列标记，
bloom过滤器图解
回到我们的问题中（对硬盘上的5TB数据），有趣的是由于硬盘空间是限制死的，集合元素个数n的大小反而与单个数据的比特数成反比，数据长度为64bit时，

m和n是线性关系，假定m=16n，当然，m越大越好，Bitmap集合的大小为，

得到是误差的上限，即如果m增大，误差更小。布隆过滤器通过引入一定错误率，使得海量数据判重在可以接受的内存代价中得以实现。从上面的公式可以看出，随着集合中的元素不断输入过滤器中(n增大)，误差将越来越大。但是，当Bitmap的大小m（指bit数）足够大时，比如，比所有可能出现的不重复元素个数还要大10倍以上时，错误概率是可以接受的。

Bloom过滤器的应用

参照[博客] https://blog.csdn.net/jdsjlzx/article/details/43916241
用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是1.

虽然有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

代码如下，

public   class  SimpleBloomFilter {
     private   static   final   int    DEFAULT_SIZE  =   2   <<   24 ;
     private   static   final   int [] seeds         =   new int[]{ 3, 5, 7, 9, 11, 13, 17, 19}; //使用质数，减少碰撞
     private  BitSet             bits          =   new  BitSet(DEFAULT_SIZE);
     private  SimpleHash[]       func          =   new  SimpleHash[seeds.length];
 
     public   static   void  main(String[] args) {
        String value  =   " stone2083@yahoo.cn " ;
        SimpleBloomFilter filter  =   new  SimpleBloomFilter();
        System.out.println(filter.contains(value));
        filter.add(value);
        System.out.println(filter.contains(value));
    }
 
     public  SimpleBloomFilter() {
         for  ( int  i  =   0 ; i  <  seeds.length; i ++ ) {
            func[i]  =   new  SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }
 
     public   void  add(String value) {
         for  (SimpleHash f : func) {
            bits.set(f.hash(value),  true );
        }
    }
 
     public   boolean  contains(String value) {
         if  (value  ==   null ) {
             return   false ;
        }
         boolean  ret  =   true ;
         for  (SimpleHash f : func) {
            ret  =  ret  &&  bits.get(f.hash(value));
        }
         return  ret;
    }
 
     public   static   class  SimpleHash {
         private   int  cap;
         private   int  seed;
         public  SimpleHash( int  cap,  int  seed) {
             this .cap  =  cap;
             this .seed  =  seed;
        }
 
         public   int  hash(String value) {
             int  result  =   0 ;
             int  len  =  value.length();
             for  ( int  i  =   0 ; i  <  len; i ++ ) {
                result  =  seed  *  result  +  value.charAt(i);
            }
             return  (cap  -   1 )  &  result;
        }
 
    }
 
}

Google，开源的bloom过滤器实现源码如下，com.google.common.hash.BloomFilter。

  //构造工厂，对外使用，构造函数private，工厂需要提供，期望插入的数据元素个数n，以及期望的错误率。
  public static <T> BloomFilter<T> create(
      Funnel<T> funnel, int expectedInsertions /* n */, double fpp) {
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
   //根据元素个数和期望错误率计算bit的位数
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
  //根据元素个数和bit位数，计算合适的hash个数，k。
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel,
          BloomFilterStrategies.MURMUR128_MITZ_32);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

 static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
      p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
  }

static int optimalNumOfHashFunctions(long n, long m) {
    return Math.max(1, (int) Math.round(m / n * Math.log(2)));
  }

可以对照公式，发现optimalNumOfBits和optimalNumOfHashFunctions果然是按照公式走的，注意换底公式的使用。

因此，借鉴google bloom过滤器的原理，现实中，我们给定期望的误差率和待插入的元素个数，让程序自动计算所需要的bit位数和hash函数个数，更合适一些。