public class MyBloomFilter {
 
    /**
     * 一個長度為10 億的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;
 
    /**
     * 為了降低錯誤率，使用加法hash算法，所以定義一個8個元素的質(zhì)數(shù)數(shù)組
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
 
    /**
     * 相當于構(gòu)建 8 個不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];
 
    /**
     * 初始化布隆過濾器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);
 
    /**
     * 添加數(shù)據(jù)
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //計算 hash 值并修改 bitmap 中相應(yīng)位置為 true
                bitset.set(f.hash(value), true);
            }
        }
    }
 
    /**
     * 判斷相應(yīng)元素是否存在
     * @param value 需要判斷的元素
     * @return 結(jié)果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一個 hash 函數(shù)返回 false 則跳出循環(huán)
            if (!ret) {
                break;
            }
        }
        return ret;
    }
 
    /**
     * 測試。。。
     */
    public static void main(String[] args) {
 
        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }
 
        // 添加1億數(shù)據(jù)
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);
 
        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}
 
class HashFunction {
 
    private int size;
    private int seed;
 
    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }
 
    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}