冷饭新炒：理解布隆过滤器算法的实现原理

import java.math.BigDecimal;
import java.math.RoundingMode;
public class BloomFilterParamGenerator {
    public BigDecimal falsePositiveRate(int m, int n, int k) {
        double temp = Math.pow(1 - Math.exp(Math.floorDiv(-k * n, m)), k);
        return BigDecimal.valueOf(temp).setScale(10, RoundingMode.FLOOR);
    }
    public BigDecimal kForMinFalsePositiveRate(int m, int n) {
        BigDecimal k = BigDecimal.valueOf(Math.floorDiv(m, n) * Math.log(2));
        return k.setScale(10, RoundingMode.FLOOR);
    }
    public BigDecimal bestM(int n, double falsePositiveRate) {
        double temp = log2(Math.exp(1) + Math.floor(1 / falsePositiveRate));
        return BigDecimal.valueOf(n).multiply(BigDecimal.valueOf(temp)).setScale(10, RoundingMode.FLOOR);
    }
    public double log2(double x) {
        return Math.log(x) / Math.log(2);
    }
    public static void main(String[] args) {
        BloomFilterParamGenerator generator = new BloomFilterParamGenerator();
        System.out.println(generator.falsePositiveRate(2, 1, 2));  // 0.3995764008
        System.out.println(generator.kForMinFalsePositiveRate(32, 1)); // 22.1807097779
        System.out.println(generator.bestM(1, 0.3995764009)); // 2.2382615950
    }
}
复制代码

// 下面的方法来源于java.util.Arrays#hashCode
public static int hashCode(Object a[]) {
    if (a == null)
        return 0;
    int result = 1;
    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());
    return result;
}
复制代码

import java.util.Objects;
public class HashFunction {
    /**
     * 布隆过滤器容量
     */
    private final int m;
    /**
     * 种子
     */
    private final int seed;
    public HashFunction(int m, int seed) {
        this.m = m;
        this.seed = seed;
    }
    public int hash(String element) {
        if (Objects.isNull(element)) {
            return 0;
        }
        int result = 1;
        int len = element.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + element.charAt(i);
        }
        // 这里确保计算出来的结果不会超过m
        return (m - 1) & result;
    }
}
复制代码

public class BloomFilter {
    private static final int[] K_SEED_ARRAY = {5, 7, 11, 13, 31, 37, 61, 67};
    private static final int MAX_K = K_SEED_ARRAY.length;
    private final int m;
    private final int k;
    private final BitSet bitSet;
    private final HashFunction[] hashFunctions;
    public BloomFilter(int m, int k) {
        this.k = k;
        if (k <= 0 && k > MAX_K) {
            throw new IllegalArgumentException("k = " + k);
        }
        this.m = m;
        this.bitSet = new BitSet(m);
        hashFunctions = new HashFunction[k];
        for (int i = 0; i < k; i++) {
            hashFunctions[i] = new HashFunction(m, K_SEED_ARRAY[i]);
        }
    }
    public void addElement(String element) {
        for (HashFunction hashFunction : hashFunctions) {
            bitSet.set(hashFunction.hash(element), true);
        }
    }
    public boolean contains(String element) {
        if (Objects.isNull(element)) {
            return false;
        }
        boolean result = true;
        for (HashFunction hashFunction : hashFunctions) {
            result = result && bitSet.get(hashFunction.hash(element));
        }
        return result;
    }
    public int m() {
        return m;
    }
    public int k() {
        return k;
    }
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(24, 3);
        bf.addElement("throwable");
        bf.addElement("throwx");
        System.out.println(bf.contains("throwable"));  // true
    }
}
复制代码

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1-jre</version>
</dependency>
复制代码

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;
public class GuavaBloomFilter {
    @SuppressWarnings("UnstableApiUsage")
    public static void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.US_ASCII), 10000, 0.0444D);
        bloomFilter.put("throwable");
        bloomFilter.put("throwx");
        System.out.println(bloomFilter.mightContain("throwable"));
        System.out.println(bloomFilter.mightContain("throwx"));
    }
}
复制代码

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.15.1</version>
</dependency>
复制代码

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
public class RedissonBloomFilter {
    public static void main(String[] args) {
        Config config = new Config();
        config.useSingleServer()
                .setAddress("redis://127.0.0.1:6379");
        RedissonClient redissonClient = Redisson.create(config);
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("ipBlockList");
        // 第一个参数expectedInsertions代表期望插入的元素个数，第二个参数falseProbability代表期望的误判率，小数表示
        bloomFilter.tryInit(100000L, 0.03D);
        bloomFilter.add("127.0.0.1");
        bloomFilter.add("192.168.1.1");
        System.out.println(bloomFilter.contains("192.168.1.1")); // true
        System.out.println(bloomFilter.contains("192.168.1.2")); // false
    }
}
复制代码