详解布隆过滤器原理,及分布式运用方法_布隆过滤器最小误差

<!--guava:布隆过滤器-->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>19.0</version>
</dependency>

public class BloomFilterObj {
    //预计要插入元素个数
    private static int size = 1000000;
    //期望的误判率
    private static double fpp = 0.01;
    //布隆过滤器
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

    public static void main(String[] args) {
        HashMap 
        //插入数据
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 1000000; i < 3000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("总共的误判数:" + count);
    }
}

//最后几行输出
2999753误判了
2999838误判了
2999923误判了
2999928误判了
总共的误判数:20339

/**
* @author: feiwang_6
* @create: 2020/6/4 22:14
* @description: Redis实现布隆过滤器
*/
public class RedisBloomFilter {
//预计插入的元素个数
static final int expectedInsertions = 1000;
//期望的误判率
static final double fpp = 0.01;
//bit数组长度
private static long bitSize;
//hash函数数量
private static int numHashFunctions;
static {
bitSize = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public static void main(String[] args) {
//初始化Redis布隆过滤器
Jedis jedis = new Jedis("localhost", 6379);
for (int i = 0; i < 1000; i++) {
long[] indexArray = getIndexArray(String.valueOf(i));
for (long index : indexArray) {
jedis.setbit("bloom_key_name", index, true);
}
}
//测试布隆过滤器的误报率
int num = 0;
for (int i = 1000; i <= 2000; i++) {
long[] indexArray = getIndexArray(String.valueOf(i));
for (long index : indexArray) {
if (!jedis.getbit("bloom_key_name", index)) {
System.out.println(i + " 一定不存在");
num++;
break;
}
}
}
System.out.println("一定不存在的有 " + num + " 个");
}
/**
* 根据key获取布隆过滤器bitmap下标
* (guava的布隆过滤器实现源码)
*/
private static long[] getIndexArray(String key) {
//低32位
long hash1 = (int)hash(key);
//高32位
long hash2 = (int)(hash1 >>> 32);
long[] result = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
long combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % bitSize;
}
return result;
}
/**
* hash计算
* @param key
* @return
*/
private static long hash(String key) {
return Hashing.murmur3_128().hashBytes(key.getBytes()).asLong();
}
/**
* 计算hash函数个数
* 根据上面公式hash函数个数k = (m / n) * log(2)，需要考虑到避免因除法而截断小数部分
*  (guava的布隆过滤器实现源码)
* @param n
* @param m
* @return
*/
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
/**
* 根据上面公式计算布隆过滤器bit数组长度m 
*     (guava的布隆过滤器实现源码)
* @param n
* @param p
* @return
*/
private static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
}

//最后几行运行结果：
1997 一定不存在
1998 一定不存在
1999 一定不存在
2000 一定不存在
一定不存在的有988个