Design a Bloom Filter

The Problem

Suppose a web application checks every incoming URL against a blocklist of 50 million known-malicious domains. The naive approach loads every domain into a HashSet<String>, consuming over 3 GB of heap. On a container with a 512 MB memory limit, the service crashes on startup. A database lookup adds 5 ms per request, while the hot path requires sub-millisecond checks.

A Bloom filter solves this by trading perfect accuracy for dramatic memory savings. It uses a bit array and multiple hash functions to answer "is this element in the set?" with two possible outcomes: "definitely not" (always correct) or "probably yes" (occasionally wrong). For 50 million elements at a 1% false positive rate, a Bloom filter needs roughly 57 MB instead of 3 GB.

Design the core classes for a Bloom filter that supports pluggable hash function strategies, configurable false positive rates, an optimal sizing calculator, and a counting variant that supports element deletion.

Scope

In scope: an in-memory, insert-and-query Bloom filter with configurable expected cardinality and false-positive target, pluggable hashing, atomic bit storage, and a counting-filter extension point.

Out of scope: persistence format, distributed merge protocols, cryptographic guarantees, and deletion in the standard bit-only filter. The core promise is “no false negatives for inserted items,” not exact membership.

30-Second Design Summary

BloomFilter coordinates a BloomFilterConfig, a HashFunction strategy, and a BitArray. Construction converts expected item count n and target false-positive rate p into bit-array size m and hash count k. add() sets all k positions; mightContain() returns false when any position is clear and otherwise returns “possibly present.”

5-Minute Walkthrough

1. Configuration validates n and p, then computes m ≈ -n ln(p)/(ln 2)^2 and k ≈ (m/n) ln 2.
2. Adding an element asks the hash strategy for k positions and atomically sets those bits in BitArray.
3. Querying repeats the same positions; one zero bit proves absence, while all one bits permit a false positive.
4. The filter never removes a bit because that bit may have been set by another element; the counting variant stores counters when deletion is required.
5. Memory use is predictable from m, and concurrency is isolated in the bit-storage abstraction rather than spread through membership logic.

Requirements

Clarifying Questions

Before jumping into class design, ask questions to pin down the scope. Cover four areas: core behavior, configuration, boundaries, and extensibility.

You: "How many elements do we expect to insert, and what false positive rate is acceptable?"

Interviewer: "The caller specifies both at construction time. Typical usage is 1 million to 100 million elements with a target false positive rate between 0.1% and 5%."

Good. Those two inputs drive everything: the bit array size and the optimal number of hash functions. We will compute both from the formulas at construction time.

You: "Do we need to support element deletion, or is this insert-and-query only?"

Interviewer: "Start with insert-and-query. Then add a counting variant as an extension that supports deletion."

Insert-and-query first. A standard Bloom filter cannot delete because clearing a bit might affect other elements that hash to the same position. The counting variant replaces bits with counters.

You: "Should the caller choose which hash functions to use, or do we pick them internally?"

Interviewer: "Make it pluggable. Provide a default double-hashing strategy, but let the caller swap in their own hash function implementation."

Strategy pattern for hash functions. The default uses double hashing (two base hashes combined to simulate k independent hashes). The caller can inject alternatives like Murmur3 or FNV1a.

You: "Does the filter need to be thread-safe for concurrent reads and writes?"

Interviewer: "Yes. Multiple threads may call add() and mightContain() concurrently."

Thread safety matters. We will use AtomicLongArray for lock-free concurrent access to the underlying bit array. Reads are always safe. Writes use CAS operations.

You: "Should we support serialization for persistence or network transfer?"

Interviewer: "Out of scope for now. Design it so serialization could be added later without restructuring."

Clean boundary. The internal state (bit array, config) is accessible enough that a serializer can read it, but we do not build that today.

You: "Should we support merging two Bloom filters (union operation)?"

Interviewer: "That is a nice extension. Mention it in extensibility, but do not implement it in the core design."

Union is a bitwise OR of two identically-configured filters. We will note it as an extension point.

You: "Should the filter report its current estimated false positive rate as elements are added?"

Interviewer: "Yes, that is useful for monitoring. Provide a method that computes the current estimated rate based on how many elements have been inserted."

Observable state. The formula is $(1 - e^{-kn/m})^k$ where $k$ is hash count, $n$ is inserted elements, and $m$ is bit array size.

Final Requirements

Functional Requirements:

1. Insert an element into the Bloom filter using add(element).
2. Query membership using mightContain(element), returning true (possibly present) or false (definitely not present).
3. Compute optimal bit array size $m$ and hash function count $k$ from expected elements $n$ and target false positive rate $p$.
4. Support pluggable hash function strategies (double hashing, independent hashes, custom).
5. Report the current estimated false positive probability after insertions.
6. Guarantee zero false negatives: if mightContain returns false, the element was never added.

Non-Functional Requirements:

1. Thread-safe for concurrent add() and mightContain() calls.
2. Extensible for new hash function strategies without modifying existing code.
3. Memory-efficient: use a bit array, not a boolean array.

Out of Scope:

• Persistence / serialization
• Network transfer
• Bloom filter union/intersection (noted as extension)
• UI or CLI interface

Example Inputs and Outputs

Scenario 1: Basic insert and query

• Input: Create a filter for 1000 elements at 1% false positive rate. Insert "alice@example.com". Query "alice@example.com" and "bob@example.com".
• Expected: mightContain("alice@example.com") returns true. mightContain("bob@example.com") returns false (assuming no hash collision).
• Why: Validates the core insert-then-query contract.

Scenario 2: False positive demonstration

• Input: Create a filter for 100 elements at 10% false positive rate. Insert 100 random strings. Query 1000 strings never inserted.
• Expected: Roughly 100 of the 1000 queries return true (false positives). Zero of the 100 inserted elements return false.
• Why: Validates the probabilistic guarantee: false positives happen at the configured rate, but false negatives never happen.

Scenario 3: Counting Bloom filter deletion

• Input: Create a counting filter. Insert "session-abc". Verify mightContain("session-abc") returns true. Remove "session-abc". Query again.
• Expected: After removal, mightContain("session-abc") returns false.
• Why: Validates that the counting variant supports deletion by decrementing counters instead of clearing bits.

Try It Yourself

---

Step 1: Identify Core Entities

Entities and Responsibilities

The responsibility map below separates configuration math, hash-position generation, bit storage, membership orchestration, and the deletion-capable variant so probabilistic behavior stays testable.

Start by asking: what are the main "things" in this problem? Look for nouns in your requirements. You need something that holds bits, something that hashes elements to positions, something that ties it all together, and a configuration object that captures the math.

A common mistake is stuffing everything into one giant BloomFilter class. That works for a quick prototype, but it makes the hash function strategy impossible to swap and tangles bit-level operations with high-level membership logic.

Notice that BitArray is separate from BloomFilter because bit manipulation is a distinct responsibility. The BloomFilter does not care whether the underlying storage uses long[], AtomicLongArray, or a memory-mapped file. Separating them lets us swap implementations without touching membership logic.

Step 2: Define Relationships and Class Design