Lintcode 556. Standard Bloom Filter

Description

中文English

Implement a standard bloom filter. Support the following method:

1. StandardBloomFilter(k),The constructor and you need to create k hash functions.
2. add(string). add a string into bloom filter.
3. contains(string). Check a string whether exists in bloom filter.

Have you met this question in a real interview?  

Example

Example1

Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]

Example2

Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,false]

Code (Java):

class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = ((hashCode * base) + Character.getNumericValue(str.charAt(i))) % size;
        }

        return hashCode;
    }
}

public class StandardBloomFilter {
    private BitSet bitSet;
    private int k;
    private List<HashFunction> hashFunctions;
    /*
    * @param k: An integer
    */public StandardBloomFilter(int k) {
        // do intialization if necessary
        this.k = k;
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 1);
            hashFunctions.add(func);
        }

        bitSet = new BitSet(100000);
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (int i = 0; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            bitSet.set(hashCode);
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (int i = 0 ; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            if (!bitSet.get(hashCode)) {
                return false;
            }
        }

        return true;
    }
}