Bloom Filter

Most machine-coding prompts ask you to model a real-world system. This one asks you to model a probabilistic guarantee: a structure that can say "definitely not in the set" with total confidence and "probably in the set" with a tunable margin of error - and never the reverse.

Requirements

Functional

• add(item) records an item in the filter.
• mightContain(item) returns false only if the item was definitely never added, and true if the item was probably added (with a bounded false-positive rate).
• The false-positive rate should be tunable by the caller when the filter is created, given an expected number of items.

Non-functional

• Both operations must run in time independent of how many items have been added so far - no scanning a growing list.
• Memory usage must stay proportional to the configured bit-array size, not to the number of items inserted (that's the entire point of using a Bloom filter over a hash set).

Design

A BloomFilter is a fixed-size bit array plus k hash functions. add sets k bits; mightContain checks the same k bits and answers false the instant any one of them is unset - one unset bit is proof the item was never added, because add always sets all k.

1. 1The caller only ever talks to the filter, never to a hash function or the bit array directly.
2. 2The filter derives k positions from the item using its small family of hash functions.
3. 3Each of the k positions gets set to 1 - overlapping with other items' bits is expected and fine.
4. 4Later, a membership check recomputes the same k positions for a possibly-different item.
5. 5One unset bit among the k is proof this exact item was never added - the filter returns false immediately.

The one thing this structure cannot do is un-know something: a bit shared by two different items can never be safely cleared for just one of them, which is why there's no remove.

Class diagram

implementsuses

BloomFilter owns one bit array and a small family of hash functions - both fixed in size regardless of how many items pass through.

Code

import java.util.BitSet;

 

interface HashFunction {

int hash(String item, int seed);

}

 

class SeededHashFunction implements HashFunction {

public int hash(String item, int seed) {

int h = seed;

for (char c : item.toCharArray()) {

h = h * 31 + c;

}

return Math.abs(h);

}

}

 

class BloomFilter {

private final BitSet bits;

private final int size;

private final int numHashes;

private final HashFunction hashFunction;

 

private BloomFilter(int size, int numHashes, HashFunction hashFunction) {

this.size = size;

this.numHashes = numHashes;

this.hashFunction = hashFunction;

this.bits = new BitSet(size);

}

 

static BloomFilter create(int expectedItems, double falsePositiveRate) {

int size = (int) Math.ceil(-expectedItems * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2)));

int numHashes = Math.max(1, (int) Math.round((size / (double) expectedItems) * Math.log(2)));

return new BloomFilter(size, numHashes, new SeededHashFunction());

}

 

void add(String item) {

for (int position : positionsFor(item)) {

bits.set(position);

}

}

 

boolean mightContain(String item) {

for (int position : positionsFor(item)) {

if (!bits.get(position)) return false;

}

return true;

}

 

private int[] positionsFor(String item) {

int h1 = hashFunction.hash(item, 17);

int h2 = hashFunction.hash(item, 31);

int[] positions = new int[numHashes];

for (int i = 0; i < numHashes; i++) {

positions[i] = Math.floorMod(h1 + i * h2, size);

}

return positions;

}

}

Design decisions

• k hash functions are simulated from two real hash functions, not k distinct hash algorithms. Implementing and tuning ten independent hash functions is both slow and unnecessary - the standard trick (h1(x) + i * h2(x) for i in 0..k) produces k well-distributed positions from two hashes, with no measurable accuracy loss for this use case (the Kirsch-Mitzenmacher technique).
• There is no remove, and that's a design decision, not a gap. Clearing a bit to "un-add" one item can flip that bit off for a completely different item that happens to share it, turning a false positive into a false negative - which breaks the one guarantee a Bloom filter is allowed to make. A system that needs deletion needs a different structure (a Counting Bloom Filter, which trades bits for small counters), not a patch on this one.
• Bit array size and k are derived from the caller's target false-positive rate and expected item count, not left for the caller to guess. A static factory method (BloomFilter.create(expectedItems, falsePositiveRate)) runs the standard formulas once at construction, so getting the tuning right doesn't depend on the caller knowing the math.
• What's missing for a real system: a filter sized for N items degrades in accuracy well past N (scalable Bloom filters chain in a fresh, larger filter instead of resizing in place), and a multi-writer environment needs the bit-set operation to be atomic - a single-threaded boolean[] isn't safe for concurrent add calls.