Bloom Filter

What’s Bloom Filter

A Bloom filter is a data structure that’s used to test whether an element is a member of a set.
The primary advantage of a Bloom filter over other data structures is that it’s incredibly space-efficient
when dealing with large data sets.

However, this comes with a trade-off: while Bloom filters can definitively state if an element is not in the set,
it can only probabilistically determine if an element is in the set.
This means it has a certain rate of false positives.

In a Bloom filter, data is passed through several hash functions, with each function mapping the input to a
position within a bit array.

When an element is added to the Bloom filter, bits at the hashed positions are set to 1.
When testing for the presence of an element, the filter checks whether the bits at the hashed positions are set.
If they are, the filter returns “possibly in set”. If not, it returns “definitely not in set”.

Simple Java Implementation

import java.util.BitSet;

public class BloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24;
    private final BitSet bitSet = new BitSet(DEFAULT_SIZE);
    private static final int[] seeds = new int[]{7, 11, 13, 31, 37, 61};
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    public void add(String value) {
        for (SimpleHash f : func) {
            bitSet.set(f.hash(value), true);
        }
    }

    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bitSet.get(f.hash(value));
        }
        return ret;
    }

    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
}

Unit tests

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class BloomFilterTest {
    private BloomFilter bloomFilter;

    @Before
    public void setup() {
        bloomFilter = new BloomFilter();
    }

    @Test
    public void testAddAndContains() {
        String testValue = "test";
        bloomFilter.add(testValue);

        Assert.assertTrue(bloomFilter.contains(testValue));
    }

    @Test
    public void testDoesntContain() {
        String testValue = "test";
        String otherValue = "other";

        bloomFilter.add(testValue);

        Assert.assertFalse(bloomFilter.contains(otherValue));
    }

    @Test
    public void testEmpty() {
        String testValue = "test";

        Assert.assertFalse(bloomFilter.contains(testValue));
    }
}