Return to Revisions

##Typo##

This probably happened when you cut and pasted your code, but your contains function had a few lines switched in their ordering.

##Operations taking O(size) time, could be faster##

Your add, remove, and contains operations all do approximately the same thing. They create a hash where the hash contains up to bpe bits set in an array of size bits. Then they iterate over the size bits.

The important thing here is that bpe is much smaller than size. For any size larger than 64, bpe will be sqrt(size). Since only bpe bits are set, you only need to take O(bpe) time instead of O(size) time.

##Operations using 32x the required space##

Also, when you create your array of bits, you use one int per bit even though you only ever set the int to 1 or 0. If size is very large, such as 100 million, you could be using 400 MB when you only need to be using 12.5 MB.

##Putting it all together##

I rewrote your functions, and also combined all of their functionality into the hashing function since all 3 functions were so similar. In the new code, the loops only run through bpe iterations instead of size iterations. I also packed the bits to minimize the space used.

/**
 * Performs one of three operations: add, remove, or contains.
 *
 * @param        v                The element to add/remove/test.
 * @param        operation        1 = add, -1 = remove, 0 = contains
 * @return                        If operation is "contains", returns true
 *                                if v is contained in the bloom filter, and
 *                                false if it is not.  If operation is
 *                                anything else, returns true.
 */
private boolean hashOperation(V v, int operation)
{
    Random r         = new Random(v.hashCode());
    int[]  bitsFound = new int[(size+31)/32];

    for(int i=0;i<bpe;i++){
        int bitNum   = r.nextInt(size);
        int bitIndex = bitNum >> 5;
        int bit      = (1 << (bitNum & 31));
        if ((bitsFound[bitIndex] & bit) == 0) {
            // New bit.  Perform operation.
            bitsFound[bitIndex] |= bit;
            if (operation == 0) {
                if(data[bitNum] == 0)
                    return false;
            } else {
                data[bitNum] += operation;
            }
        }
    }
    return true;
}

public boolean remove(V v)
{
    if (contains(v)) {
        hashOperation(v, -1);
        count--;
        return true;
    }
    return false;
}

public void insert(V v)
{
    hashOperation(v, 1);
    count++;
}

public boolean contains(V v)
{
    return hashOperation(v, 0);
}