Description
中文English
Implement a counting bloom filter. Support the following method:
add(string). Add a string into bloom filter.contains(string). Check a string whether exists in bloom filter.remove(string). Remove a string from 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,true]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 = (int)(((long)hashCode * base + Integer.valueOf(str.charAt(i))) % size);
}
return hashCode;
}
}
public class CountingBloomFilter {
private List<HashFunction> hashFunctions;
private int[] bloomFilter;
/*
* @param k: An integer
**/
public CountingBloomFilter(int k) {
// do intialization if necessary
hashFunctions = new ArrayList<>();
for (int i = 0; i < k; i++) {
HashFunction func = new HashFunction(100000, 2 * i + 3);
hashFunctions.add(func);
bloomFilter = new int[100000];
}
}
/*
* @param word: A string
* @return: nothing
*/
public void add(String word) {
// write your code here
for (HashFunction hashFunc : hashFunctions) {
int hashCode = hashFunc.hash(word);
bloomFilter[hashCode] += 1;
}
}
/*
* @param word: A string
* @return: nothing
*/
public void remove(String word) {
// write your code here
for (HashFunction hashFunc : hashFunctions) {
int hashCode = hashFunc.hash(word);
bloomFilter[hashCode] -= 1;
}
}
/*
* @param word: A string
* @return: True if contains word
*/
public boolean contains(String word) {
// write your code here
for (HashFunction hashFunc : hashFunctions) {
int hashCode = hashFunc.hash(word);
if (bloomFilter[hashCode] <= 0) {
return false;
}
}
return true;
}
}
