布隆过滤器

public class BloomFilter {
    private int[] filter;
    private int size;
    private int hashFunctions;
    private int numElements;

    public BloomFilter(int size, int hashFunctions) {
        this.size = size;
        this.hashFunctions = hashFunctions;
        filter = new int[size];
        numElements = 0;
    }

    public void add(String value) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hash(value, i);
            filter[hash] = 1;
        }
        numElements++;
        checkSize();
    }       

    public boolean contains(String value) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hash(value, i);
            if (filter[hash] != 1) {
                return false;
            }
        }
        return true;
    }

    private int hash(String value, int i) {
        int hash = 0;
        for (int j = 0; j < value.length(); j++) {
            hash = hash * 31 + value.charAt(j);
        }
        return Math.abs(hash + i) % size;
    }

    private void checkSize() {
        if (numElements > size * 0.75) {
            resize();
        }
    }

    private void resize() {
        size *= 2;
        hashFunctions = (int) Math.round(Math.log(2) * size / numElements);
        int[] newFilter = new int[size];
        for (int i = 0; i < filter.length; i++) {
            newFilter[i] = filter[i];
        }
        filter = newFilter;
    }
}

Q.E.D.