This question is the second iteration of Counting Bloom filter library in Java. I did nothing more but fixing the remove
method in order to fix an issue mentioned by JS1. I will present only the actual filter implementation as all other bricks required for running a demonstration are there.
BloomFilter.java:
package net.coderodde.util;
/**
* This class implements a counting Bloom filter which allows not only
* inserting, querying, but deleting an element as well.
*
* @author Rodion "rodde" Efremov
* @version 1.6
* @param <T> the filter element type.
*/
public class BloomFilter<T> {
/**
* The minimum capacity of the counter array.
*/
private static final int MINIMUM_CAPACITY = 128;
/**
* The array holding the counts of each bucket.
*/
private final int[] array;
/**
* The array of hash functions.
*/
private final AbstractHashFunction[] hashFunctions;
/**
* The array of indices returned by the hash functions. Used for handling
* the removal of elements from the filter.
*/
private final int[] indexArray;
/**
* Constructs a counting Bloom filter with array capacity {@code capacity}
* and given hash functions.
*
* @param capacity the capacity of the counter array.
* @param firstHashFunction the mandatory hash function.
* @param otherHashFunctions the array of voluntary hash functions.
*/
public BloomFilter(int capacity,
AbstractHashFunction<T> firstHashFunction,
AbstractHashFunction<T>... otherHashFunctions) {
capacity = Math.max(capacity, MINIMUM_CAPACITY);
this.array = new int[capacity];
this.hashFunctions =
new AbstractHashFunction[otherHashFunctions.length + 1];
this.hashFunctions[otherHashFunctions.length] = firstHashFunction;
System.arraycopy(otherHashFunctions,
0,
this.hashFunctions,
0,
otherHashFunctions.length);
this.indexArray = new int[hashFunctions.length];
}
/**
* Adds an element to this filter. Works by computing the hash values of the
* element and increments the counters indexed by those hash values.
*
* @param element the element to add.
*/
public void add(T element) {
for (AbstractHashFunction<T> hashFunction : hashFunctions) {
array[Math.abs(hashFunction.hash(element)) % array.length]++;
}
}
/**
* Queries whether {@code element} is possibly in the filter. This may give
* false positives, but never false negatives. A false positive is the
* situation where an element is reported to be in the filter when it was
* never added to it. A false negative is the situation where an element
* is reported not being in the filter when it was actually added to the
* filter.
*
* @param element the element to query.
* @return {@code false} if the element is definitely not in the filter, and
* {@code true} otherwise.
*/
public boolean contains(T element) {
for (AbstractHashFunction<T> hashFunction : hashFunctions) {
if (array[Math.abs(hashFunction.hash(element)) %
array.length] == 0) {
return false;
}
}
return true;
}
/**
* Removes the {@code element} from this filter. In the first pass, this
* operation makes sure that there is chance that the input element was
* added to this filter. If so, it decrements the counters indexed by the
* hash values.
*
* @param element the element to remove.
*/
public void remove(T element) {
if (contains(element)) {
int hashFunctionIndex = 0;
for (AbstractHashFunction<T> hashFunction : hashFunctions) {
indexArray[hashFunctionIndex++] =
Math.abs(hashFunction.hash(element)) % array.length;
}
for (int i = 0; i < indexArray.length; ++i) {
if (array[indexArray[i]] == 0) {
for (int j = 0; j < i; ++j) {
array[indexArray[j]]++;
}
return;
} else {
array[indexArray[i]]--;
}
}
}
}
}
Any improvements possible?