近期学习的时候发现了一个强大的神器，布隆过滤器，发现这个算法对大数据的去重真的很有用哎！记录一下，免得自己忘了。

概念

  首先我先来介绍一下这个算法的基本思想，假设让你实现查重的话，你肯定是用Hash表存储下来，然后判断，那么怎么存储呢？给你一个字符串，你肯定是先用hash函数映射一下，如果值的访问太大的话，可能要取个模什么的，让后这个作为标识存储在Hash表中，虽然这样做的时间复杂度不高，但空间使用率太高了，而且你想一下，你根本就不用这个串，你只是要知道是否有重复，这样布隆过滤器就诞生了。
  假设我们这边有8个不同hash函数（很完美的），4字节的一个空间（32位）（可以称之为桶），每一位都设置为0，我们分别使用这8个hash函数，然后对32取余，这样就会得到8个小于32位的数字，我们把这八个数字当作序号，把32位中对应的位设置位1，表示已经存在，这样，当我们下次再有相同的字符串的时候，我们可以看看对应位置上是不是都是1，如果是就是重复啦，如果不是就说明不在里面；
  是不是很神奇，对的。那么这个算法有没有局限呢？它是绝对不会漏掉相同的串的（因为相同的串Hash肯定是一样的），有可能会误判，这就是所谓的宁可错杀也不放过，所以说合理选择Hash函数个数很重要
  那么怎么计算这个Hash函数个数呢？ 假设整个数据大小是n,容许的失误率是p
那么 hash函数的个数（我听一个大佬总结的）

m = n * ln p / (ln 2)^2

那么这个复杂度是多少呢？还是O（n）啊，判断一个串的话就是O（1），那有的人就奇怪了，判断的话不是应该是O（n）吗？不是的，一个串的唯一表示就是一个32位的空间，相当于一个int的值，就BitSet存储get的话就是O（1）

代码实现

接着来一波代码，让大家感受一下

package Filter;

import java.util.BitSet;

public class BloomFilter {
   private  static  int BIT_SIZE = 2 << 25;//可以表示的数据量 ，你可以试着调大一点
   private BitSet bitSet ;
   private int[] seeds = {3,5,7,11,13,31,37,61};
   private HashFunction[] func;
   public BloomFilter(int size) throws Exception{
       if (size <= 30 && size > 0){
           BIT_SIZE = 2 << size;
       } else {
           throw  new Exception("range illegal");
       }
       bitSet = new BitSet(BIT_SIZE);
       func = new HashFunction[seeds.length];
       for (int i = 0; i < func.length; i++){
           func[i] = new HashFunction(seeds[i],seeds.length);
       }
   }
   public void add(String val){
       if (val == null) return;
       for (HashFunction function : func){
           bitSet.set(function.hash(val),true);
       }
   }
   public boolean contain(String val){
       if (val == null) return false;
       for(HashFunction function: func){
           if(!bitSet.get(function.hash(val)))
               return false;
       }
       return true;
   }

   public static class HashFunction{
       private int seed;
       private int size;
       public HashFunction(int seed,int size){
           this.seed = seed;
           this.size = size;
       }
      //计算hash的方法，我看String源码里面写的是seed = 31,
       public int hash(String value){
           int ans = 0;
           for (char ch : value.toCharArray()){
               ans = ans * seed + ch;
           }
           return ans & (size - 1);
       }
   }
}