2
\$\begingroup\$

I have tried to implement a Bloom Filter in Java here.

https://github.com/srirammanoj/skynet/tree/master/bloomfilter

I just wanted to know if my implementation can be called 'thread-safe' , and if there is an improvement to be made on the locking I have used here. I opted for locks instead of 'sychronized', as I wanted multiple simultaneous reads. I tried to minimize the section of the code inside the lock.

The optimistic read lock of Stamped Lock seems fragile and will give me erroneous reads and I would rather block a read than fail it and retry.

I wanted to know if there is an obvious improvement to be made here.

The actual methods in the code containing the lock. ----

private void addElement(byte[] element) {
    if (null == element) {
        throw new NullPointerException();
    }

    long hash1 = Integer.toUnsignedLong(Murmur3Hash.murmurhash3_x86_32(element, 0, element.length, filterParams.seed1));
    long hash2 = Integer.toUnsignedLong(Murmur3Hash.murmurhash3_x86_32(element, 0, element.length, filterParams.seed2));

    writeLock.lock();
    try {
        for (int i = 1; i <= filterParams.k; i++) {
            long hash = hash1 + i * hash2;

            int mod = ( int ) ( hash % filterParams.bucketLength );

            int offset = (i - 1) * filterParams.bucketLength;

            int index = offset + mod;
            bitSet.set(index);
        }

        elementsAdded++;
    } finally {
        writeLock.unlock();
    }

}

public boolean containsElement(byte[] element) {
    if (null == element) {
        throw new NullPointerException();
    }

    long hash1 = Integer.toUnsignedLong(Murmur3Hash.murmurhash3_x86_32(element, 0, element.length, filterParams.seed1));
    long hash2 = Integer.toUnsignedLong(Murmur3Hash.murmurhash3_x86_32(element, 0, element.length, filterParams.seed2));

    readLock.lock();
    try {
        for (int i = 1; i <= filterParams.k; i++) {
            long hash = hash1 + i * hash2;

            int mod = ( int ) ( hash % filterParams.bucketLength );
            int offset = (i - 1) * filterParams.bucketLength;
            int index = offset + mod;
            if (index < 0)
                index = -index;

            if (!bitSet.get(index)) {
                return false;
            }
        }
    } finally {
        readLock.unlock();
    }

    return true;
}

Thanks.

\$\endgroup\$
1
\$\begingroup\$

The locking looks fine, but there are a couple of things which look fishy in the code.

Firstly,

            if (index < 0)
                index = -index;

This should surely be present in both methods or in neither? But it's only in the second one.

Secondly,

            int offset = (i - 1) * filterParams.bucketLength;

It seems that each derived hash is stored in a non-overlapping bucket. By my understanding of Bloom filters, what you have here isn't a Bloom filter.

Finally, I suggest for your consideration unrolling the multiplications:

        long hash = hash1;
        for (int i = 1, offset = 0; i <= filterParams.k; i++) {
            hash += hash2;

            int mod = ( int ) ( hash % filterParams.bucketLength );
            int index = offset + mod;

            bitSet.set(index);

            offset += filterParams.bucketLength;
        }

This saves a bit of thought as to "why does it multiply by i to calculate hash but by i-1 to calculate offset?".

\$\endgroup\$
1
  • \$\begingroup\$ The first part was a mistake. The code should not be in either method. The unrolling the multiplications part makes sense. Regarding the bucketing, it is a variant of the bloom filter , to make sure that each element is described by exactly k bits . There might be cases where all or most of the 'k' hash functions map to the same index. This makes some elements more prone to false positives. The bucketing tries to alleviate the issue. Its described here in the second page of the document gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf . Thanks for your help , really appreciate it ! \$\endgroup\$ – sriram manoj May 4 '16 at 15:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.