目录
实现思路
首先最重要的自定义hash()
然后就是将key放入bitSet
然后就是判断布隆过滤器bitSet数组中是否含有对应的key
代码
实现思路
(39条消息) Redis布隆过滤器_Fairy要carry的博客-CSDN博客
1.首先判断key是否为null，否则返回0——>2.然后数组长度-1-i（目的使散列均匀，因为我们定义一个数组，全是辅助多次hash，所以需要-i保留特点），然后就是（size-1-i）&（(h=key.hashcode())^h>>>16）——>3.非常关键在这里，计算key的hash值后，然后^key的hash>>>16,目的是保留key的特点，保证散列均匀，因为size-1-i（像hashMap默认size为16，那么15对应的二进制为1111，那么就只能与hash的低位四个进行运算，那么保留特点就很少），所以>>>16保留了key hash低位16的特点，然后再^key.hashCode()->保证了高位16的特点（这样就保证了key的特点）
private int hash(Object key, int i) {
int h;
//BloomFilter_Size-i归根结底是为了保证散列均匀，保证每一次hash后key的特点——>之前push也是对key进行多次hash
int index = key == null ? 0 : (BloomFilter_Size - 1 - i) & ((h = key.hashCode()) ^ (h >>> 16));
return index > 0 ? index : -index;
}思路：1.计算key的hash（利用辅助hash数组对key进行多次hash），得到位置index后放入数组
/**
* 2.存放key
* 思路：1.遍历布隆过滤器的hash数组，对key进行多次hash并且保存在BitSet数组中
*
* @param key
*/
public void push(Object key) {
Arrays.stream(HelperBloom).forEach(i -> bitSet.set(hash(key, i)));
currentBaseBean++;
}思路：1.一样的，这里巧妙的是利用了&&，因为我们对key进行了多次hash，所以我们遍历辅助hash数组进行多次hash，根据对应index位置从bitSet取出看是否能取出，若为false，那么后面全为false——>2.直接利用&&，result默认为true，&&有一个为false那么结果就是false
/**
* 3.计算key的hash值并且去bitSet寻找看是否有位置，如果有返回true
* 思路：利用&&，从bitSet取出对应key的hash的index，如果没有返回false，因为&&所以结果false
*
* @param key
* @return
*/
public boolean isContain(Object key) {
boolean result=true;
for (int i : HelperBloom) {
result = result && bitSet.get(hash(key, i));
}
return result;
}代码
import java.util.Arrays;
import java.util.BitSet;
/**
* @author diao 2022/9/7
*/
public class BloomFilter {
//后面hash函数会用到，用来生成不同的hash值，可以随便给，但别给奇数
private final int[] ints = {6, 8, 16, 38, 58, 68};
private Integer currentBeanCount = 0;
//你的布隆过滤器容量
private int DEFAULT_SIZE = Integer.MAX_VALUE;
//bit数组，用来存放结果
private final BitSet bitSet = new BitSet(DEFAULT_SIZE);
public BloomFilter() {
}
public BloomFilter(int size) {
if (size <= (2 << 8)) {
throw new RuntimeException("size is too small");
}
DEFAULT_SIZE = size;
}
//获取当前过滤器的对象数量
public Integer getCurrentBeanCount() {
return currentBeanCount;
}
//计算出key的hash值，并将对应下标置为true
public void push(Object key) {
for (int i : ints) {
bitSet.set(hash(key, i));
}
currentBeanCount++;
}
//判断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算法，借鉴了hashmap的算法
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) {
BloomFilter bf = new BloomFilter ();
bf.push("张学友");
bf.push("郭德纲");
bf.push("特雷杨");
bf.push(666);
System.out.println(bf.contain("张学友"));//true
System.out.println(bf.contain("张学友 "));//false
System.out.println(bf.contain("张学友1"));//false
System.out.println(bf.contain("郭德纲"));//true
System.out.println(bf.contain("老鹰特雷杨8"));//false
System.out.println(bf.contain(666));//true
System.out.println(bf.contain(888));//false
}
}
