package test;
import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;
/**
* @author gjp
* @className Filter class
* @date 2021/12/31
* @description: 布隆数
*/
public class Filter {
//后面hash函数会用到,用来生成不同的hash值,可以随便给,但别给奇数
private final int[] ints = {6, 8, 16, 38, 58, 68};
private AtomicInteger currentBeanCount = new AtomicInteger(0);
//布隆过滤器容量
private int DEFAULT_SIZE = Integer.MAX_VALUE;
//bit数组,用来存放结果
private final BitSet bitSet = new BitSet(DEFAULT_SIZE);
public BitSet getBitSet() {
return bitSet;
}
public Filter() {
}
public Filter(int size) {
if (size > Integer.MAX_VALUE) {
throw new RuntimeException("size is too large");
}
if (size <= (2 << 8)) {
throw new RuntimeException("size is too small");
}
DEFAULT_SIZE = size;
}
//获取当前过滤器的对象数量
public Integer getCurrentBeanCount() {
return currentBeanCount.get();
}
//计算出key的hash值,并将对应下标置为true
public void push(Object key) {
Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
currentBeanCount.getAndIncrement();
}
//计算出key的hash值,并将对应下标置为false
public void del(Object key) {
Arrays.stream(ints).forEach(i -> bitSet.clear(hash(key, i)));
currentBeanCount.getAndDecrement();
}
//判断key是否存在,true不一定说明key存在,但是false一定说明不存在
public boolean contain(Object key) {
boolean result = true;
for (int i : ints) {
result = result && bitSet.get(hash(key, i));
}
return result;
}
//hash算法
private int hash(Object key, int i) {
int h;
int index = key == null ? 0 : (DEFAULT_SIZE - 1 - i) & ((h = key.hashCode()) ^ (h >>> 16));
return index > 0 ? index : -index;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
Filter myFilter = new Filter();
myFilter.push("孙悟空");
myFilter.push("孙悟空");
myFilter.push("孙悟空");
myFilter.push("二师兄");
myFilter.push("沙师弟");
myFilter.push(666);
String pre = "唐僧1200";
for (int i = 0; i <2 ; i++) {
myFilter.push(pre+i);
}
System.out.println(";size="+myFilter.getCurrentBeanCount());
System.out.println(myFilter.contain("孙悟空"));//true
//删除
myFilter.del("孙悟空");
System.out.println("删除后:size="+myFilter.getCurrentBeanCount());
System.out.println(myFilter.contain("孙悟空"));//false
System.out.println(myFilter.contain("孙悟空"));//false
System.out.println(myFilter.contain("二师兄"));//true
System.out.println(myFilter.contain("二师兄1"));//false
System.out.println(myFilter.contain(666));//true
System.out.println(myFilter.contain("沙师弟"));//false
System.out.println(myFilter.contain("唐僧200"));
System.out.println(myFilter.contain("唐僧2000"));
for (int i = 0; i <2 ; i++) {
System.out.println(myFilter.contain(pre+i));
}
System.out.println((System.currentTimeMillis()-start) +"毫秒");
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)