java 实现布隆过滤器（BloomFilter）

HashGenerator.java

package BloomFilter;
 
public class HashGenerator {
 
    private int size;
 
    private int seed;
 
    private HashGroup group;
 
    enum HashGroup {
        G1, G2, G3, G4
    }
 
    public HashGenerator(int size, int seed, HashGroup group) {
        this.size = size;
        this.seed = seed;
        this.group = group;
    }
 
    public int doHash(String value) {
        switch (group) {
            case G1 -> {return hashG1(value);}
            case G2 -> {return hashG2(value);}
            case G3 -> {return hashG3(value);}
            case G4 -> {return hashG4(value);}
            default -> throw new RuntimeException("Err HashGroup is NULL!");
        }
    }
 
    private int hashG1(String value) {
        var hash = 0;
        for (var idx = 0; idx < value.length(); idx++) {
            var c = value.charAt(idx);
            hash = (hash << 5) + hash + c;
            hash &= hash;
            hash = Math.abs(hash);
        }
        return hash % (seed + size - 1);
    }
 
    private int hashG2(String value) {
        var hash = 7397;
        for (var idx = 0; idx < value.length(); idx++) {
            var c = value.charAt(idx);
            hash = (hash << 5) + hash + c;
        }
        return Math.abs(hash % seed * (size - 1));
    }
 
    private int hashG3(String value) {
        var hash = 0;
        for (var idx = 0; idx < value.length(); idx++) {
            var c = value.charAt(idx);
            hash = (hash << 5) + hash + c;
            hash += c;
            hash &= hash;
        }
        return Math.abs(hash % (seed * size - 1));
    }
 
    private int hashG4(String value) {
        int h;
        return (value == null) ? 0 : Math.abs(seed * (size - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
    }
 
}

BloomFilter.java

package BloomFilter;
 
import java.util.BitSet;
 
public class BloomFilter {
 
    private static final HashGenerator.HashGroup[] GROUPS = new HashGenerator.HashGroup[]{HashGenerator.HashGroup.G1, HashGenerator.HashGroup.G2, HashGenerator.HashGroup.G3, HashGenerator.HashGroup.G4};
 
    private final BitSet bits;
 
    private HashGenerator[] generators;
 
    public BloomFilter(int size, int[] seeds) {
        bits = new BitSet(size);
        generators = new HashGenerator[seeds.length];
        for (var i = 0; i < seeds.length; i++) {
            generators[i] = new HashGenerator(size, seeds[i], GROUPS[i % GROUPS.length]);
        }
    }
 
    public void add(String value) {
        for (var generator : generators) {
            var hash = generator.doHash(value);
            bits.set(hash, true);
        }
    }
 
    public boolean contains(String value) {
        var ret = true;
        for (var generator : generators) {
            ret = ret && bits.get(generator.doHash(value));
        }
        return ret;
    }
}

测试代码

    public static void main(String[] args) {
        String val00 = "小傅哥";
        String val01 = "https://bugstack.cn";
        String val02 = "https://github.com/fuzhengwei/CodeGuide";
        String val03 = "https://github.com/fuzhengwei";
 
        BloomFilter filter = new BloomFilter(Integer.MAX_VALUE, new int[]{7, 19, 43, 77});
        filter.add(val00);
        filter.add(val01);
        filter.add(val02);
 
        System.out.println("测试结果 val00：" + val00 + " 布隆过滤器：" + filter.contains(val00));
        System.out.println("测试结果 val01：" + val01 + " 布隆过滤器：" + filter.contains(val01));
        System.out.println("测试结果 val02：" + val02 + " 布隆过滤器：" + filter.contains(val02));
        System.out.println("测试结果 val02：" + val03 + " 布隆过滤器：" + filter.contains(val03));
    }