class BloomFilter {
    private int bitSize;
    private BitSet bits;
    private int[] seeds;
    private int hashIterations;
    /**
     * @param size          預(yù)計(jì)元素?cái)?shù)量
     * @param falsePositive 期望誤判率
     */
    public BloomFilter(int size, double falsePositive) {
        this.bitSize = (int) Math.ceil((size * Math.log(falsePositive)) / Math.log(1.0 / (Math.pow(2.0, Math.log(2.0)))));
        this.bits = new BitSet(bitSize);
        this.hashIterations = (int) Math.round(Math.log(2.0) * bitSize / size);
        this.seeds = new int[hashIterations];
        for (int i = 0; i < hashIterations; i++) {
            seeds[i] = i + 1;
        }
    }
    /**
     * 添加一個(gè)元素
     *
     * @param element 元素
     */
    public void add(String element) {
        for (int seed : seeds) {
            int hash = MurmurHash.hash(element.getBytes(), seed);
            bits.set(Math.abs(hash % bitSize), true);
        }
    }
    /**
     * 判斷一個(gè)元素是否存在
     *
     * @param element 元素
     * @return 是否存在
     */
    public boolean contains(String element) {
        for (int seed : seeds) {
            int hash = MurmurHash.hash(element.getBytes(), seed);
            if (!bits.get(Math.abs(hash % bitSize))) {
                return false;
            }
        }
        return true;
    }
    /**
     * MurmurHash算法
     */
    static class MurmurHash {
        public static int hash(byte[] data, int seed) {
            int m = 0x5bd1e995;
            int r = 24;
            int h = seed ^ data.length;
            int len = data.length;
            int pos = 0;
            while (len >= 4) {
                int k = data[pos] & 0xff;
                k |= (data[pos + 1] & 0xff) << 8;
                k |= (data[pos + 2] & 0xff) << 16;
                k |= (data[pos + 3] & 0xff) << 24;
                k *= m;
                k ^= k >>> r;
                k *= m;
                h *= m;
                h ^= k;
                pos += 4;
                len -= 4;
            }
            switch (len) {
                case 3:
                    h ^= (data[pos + 2] & 0xff) << 16;
                case 2:
                    h ^= (data[pos + 1] & 0xff) << 8;
                case 1:
                    h ^= data[pos] & 0xff;
                    h *= m;
            }
            h ^= h >>> 13;
            h *= m;
            h ^= h >>> 15;
            return h;
        }
    }
}

public class test {
    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1000,0.01);
        bloomFilter.add("xyz");
        boolean xyz = bloomFilter.contains("xyz");
        System.out.println("xyz查詢結(jié)果："+xyz);
        boolean xyzk = bloomFilter.contains("xyzk");
        System.out.println("xyz查詢結(jié)果："+xyzk);
    }
}