1
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.