package edu.se;

import java.util.BitSet;

/**
 * @author ZhaoWeinan
 * @date 2018/10/28
 * @description
 */
public class BloomFileter {

 //使用加法hash算法，所以定義了一個8個元素的質數數組
 private static final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
 //用八個不同的質數，相當于構建8個不同算法
 private Hash[] hashList = new Hash[primes.length];
 //創(chuàng)建一個長度為10億的比特位
 private BitSet bits = new BitSet(256 << 22);

 public BloomFileter() {
 for (int i = 0; i < primes.length; i++) {
  //使用8個質數，創(chuàng)建八種算法
  hashList[i] = new Hash(primes[i]);
 }
 }

 //添加元素
 public void add(String value) {
 for (Hash f : hashList) {
  //算出8個信息指紋，對應到2的32次方個比特位上
  bits.set(f.hash(value), true);
 }
 }

 //判斷是否在布隆過濾器中
 public boolean contains(String value) {
 if (value == null) {
  return false;
 }
 boolean ret = true;
 for (Hash f : hashList) {
  //查看8個比特位上的值
  ret = ret && bits.get(f.hash(value));
 }
 return ret;
 }

 //加法hash算法
 public static class Hash {

 private int prime;

 public Hash(int prime) {
  this.prime = prime;
 }

 public int hash(String key) {
  int hash, i;
  for (hash = key.length(), i = 0; i < key.length(); i++) {
  hash += key.charAt(i);
  }
  return (hash % prime);
 }
 }

 public static void main(String[] args) {

 BloomFileter bloomFileter = new BloomFileter();
 System.out.println(bloomFileter.contains("5324512515"));
 bloomFileter.add("5324512515");

 //維護1億個在線用戶
 for (int i = 1 ; i < 100000000 ; i ++){
  bloomFileter.add(String.valueOf(i));
 }

 long begin = System.currentTimeMillis();
 System.out.println(begin);
 System.out.println(bloomFileter.contains("5324512515"));
 long end = System.currentTimeMillis();
 System.out.println(end);
 System.out.println("判斷5324512515是否在線使用了:" + (begin - end));
 }
}