[Java] Java实现布隆过滤器的方法步骤

1亿在线用户的布隆过滤器

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];
 //创建一个长度为10亿的比特位
 private bitset bits = new bitset(256 << 22);
 
 public bloomfileter() {
 for (int i = 0; i < primes.length; i++) {
  //使用8个质数，创建八种算法
  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));
 }
}

维护了1亿个userid以后检索5324512515是否登录，代码执行时间很短

jvm整个的内存情况

书上的表，直接拍下来的