In this chapter, we will explore the low-level design of bloom filter in detail.

Lets start by clarifying the requirements:

Before starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.

Here is an example of how a discussion between the candidate and the interviewer might unfold:

Based on the discussion, here’s a summary of the functional requirements:

Now that we understand what we're building, let's identify the building blocks of our system.

Unlike systems that model real-world concepts like users or bookings, a Bloom filter is a data structure design problem. The core challenge is about choosing the right internal components and computing optimal parameters to achieve the desired probabilistic guarantees.

2.1 The Need for Space-Efficient Membership Testing

"The filter should use significantly less memory than storing all elements explicitly"

The simplest way to test set membership is a HashSet. It gives O(1) lookup and zero false positives. So why not just use one?

Because a HashSet stores every element. If you're tracking 10 million URLs for a safe browsing check, that's hundreds of megabytes of memory.

A Bloom filter can answer the same question, "Is this URL in the blacklist?", using a fraction of the space. The trade-off is that it might occasionally say "yes" when the answer is actually "no" (a false positive), but it will never say "no" when the answer is "yes" (no false negatives).

2.2 How Bit Arrays Enable Membership Testing

The foundation of a Bloom filter is a bit array: a fixed-size array where each position is either 0 or 1.

To add an element, we hash it to produce k different positions in the array and set those bits to 1. To check membership, we hash the element the same way and check if all k positions are 1. If any position is 0, the element was definitely never added. If all are 1, the element is probably in the set, but those bits might have been set by other elements.

2.3 Why Multiple Hash Functions Reduce False Positives

With a single hash function, many different elements map to the same position. The collision rate is high, and false positives are frequent. By using k independent hash functions, each element maps to k different positions. For a false positive to occur, ALL k positions must have been set by other elements. The probability of this happening drops exponentially with k.

2.4 Entity Overview

Here's how these entities relate to each other:

These entities form the core abstractions of our Bloom filter. They separate concerns cleanly: hashing is pluggable, configuration is computed once and immutable, and the main class coordinates everything.

With our entities identified, let's define their attributes, behaviors, and relationships.

Now that we know what entities we need, let's flesh out their details. For each class, we'll define what data it holds (attributes) and what it can do (methods). Then we'll look at how these classes connect to each other.

We'll work bottom-up: simple types first, then interfaces, then implementations, then the main class.

Interfaces

HashStrategy

We need a way to hash elements to bit positions. We could hardcode a single hash algorithm, but different scenarios benefit from different algorithms. A URL blacklist might prioritize speed, while a spell checker might prioritize distribution quality. An interface lets us swap algorithms without changing the BloomFilter class.

HashStrategy defines the contract for hashing an element to a position in the bit array.

The seed parameter is what gives us k independent hash values from a single algorithm. Instead of implementing k different hash functions, we call the same function k times with different seeds (0, 1, 2, ..., k-1). Each seed produces a different bit position for the same element.

Core Class

BitArray

The bit array is the storage backbone of the Bloom filter. We could use a raw boolean array directly in BloomFilter, but wrapping it in a dedicated class gives us a clean API for set/get/clear operations and keeps the BloomFilter class focused on coordination rather than low-level bit manipulation.

BitArray wraps a fixed-size array of bits with set, get, and clear operations.

BloomFilterConfig

Construction of a Bloom filter requires several related parameters, and some of them (bit array size, number of hash functions) are derived from others (expected elements, false positive rate). We need an object to hold these computed values so the BloomFilter can reference them without recomputing.

BloomFilterConfig is an immutable configuration object that holds both the caller's inputs and the computed optimal parameters.

All fields are read-only. Once the config is created, it never changes. This makes it safe to share across threads without synchronization.

BloomFilter

This is the main class that ties everything together. It coordinates the hash strategy and bit array to provide the probabilistic membership testing API.

BloomFilter accepts string inputs, uses a configurable hash strategy to compute k bit positions, and manages the bit array.

Key Design Principles:

BloomFilter.Builder

The BloomFilter has several construction parameters: expected elements (required), false positive rate (has a sensible default of 0.01), and hash strategy (has a sensible default of Murmur hashing). Rather than a constructor with many parameters, a Builder lets the caller specify only what they care about and rely on defaults for the rest. It also computes the derived values (bit array size, number of hash functions) automatically.

This problem is data-structure-heavy: the core challenge is algorithmic, choosing the right structure and computing optimal parameters, not behavioral. Two patterns earn their place.

Strategy Pattern (Hash Strategy)

The Problem: Hash algorithms trade off speed, distribution quality, and collision resistance. A URL blacklist checking millions of URLs per second might prioritize speed, while a spell checker might prioritize distribution quality.

The Solution: The Strategy pattern puts a family of hash algorithms behind a common interface. The BloomFilter delegates hashing to whatever strategy it is given, so new algorithms are added as new classes instead of by editing the BloomFilter class, following the Open/Closed Principle.

Builder Pattern (BloomFilter.Builder)

The Problem: A BloomFilter takes a required expected element count plus an optional false positive rate and hash strategy, and it must derive the bit array size and hash function count from them. A single constructor carrying all of this is hard to read.

The Solution: The Builder separates construction. The caller sets only the parameters they care about, and the builder validates inputs, applies defaults, and computes the derived values. new BloomFilter.Builder(1000000).falsePositiveRate(0.001).build() reads clearly.

Before reading the full implementation, try building this yourself. Below are template stubs for the classes from the design. The enums, data classes, and the demo are already written for you. The job is to fill in the core logic where the TODO comments appear.

Your task: Implement every TODO using the design from the previous sections. When you are done, run the demo. A correct implementation produces the expected output shown below.

Now let's translate our design into working code. We'll build bottom-up: foundational types first, then interfaces, then implementations, then the main class. This order matters because each layer depends on the ones below it.

Bloom filters are commonly shared across threads. Think of a web server where multiple request-handling threads check a URL blacklist, or a database where multiple query threads check a Bloom filter before performing expensive disk lookups. These are real scenarios where concurrent access is expected.

Concern 1: Concurrent add() and mightContain()

In a web server checking a URL blacklist, one thread might be adding newly discovered malicious URLs while another thread is checking whether an incoming request's URL is in the blacklist.

Setup

Thread A adds "malicious.com" (which hashes to positions 3, 7, and 11). Thread B simultaneously checks "malicious.com".

Without synchronization:

Result

Thread B gets a false negative. "malicious.com" was being added to the filter, but the check returned false because only some of the k bits were set at the time of the check. In a safe browsing scenario, this means a known malicious URL slips through.

With synchronization:

Thread A acquires the lock, sets all three bits atomically, and releases the lock. Thread B then acquires the lock, checks all three bits (all true), and returns true. No false negatives from partial writes.

The design holds up well as new requirements arrive, because each concern lives in its own class. The hash logic sits behind HashStrategy, the storage sits behind BitArray, and the derived parameters sit in BloomFilterConfig. Every extension below adds new classes or fields without rewriting the existing add and mightContain logic.

Scenario: "We need to remove elements, not just add them."

A standard Bloom filter cannot support deletion. Clearing a bit during a remove would also clear it for every other element that hashed to the same position, which introduces false negatives. A Counting Bloom Filter replaces each single bit with a small counter. Adding an element increments the k counters, removing it decrements them, and a position is considered set whenever its counter is above zero. This keeps the same hashing flow used in BloomFilter and only swaps BitArray for a counter array.

The cost is memory. Each position now needs several bits instead of one, so a typical 4-bit counter makes the structure four times larger than a plain BitArray. Counters can also overflow if the same position is incremented many times, so production implementations cap each counter at its maximum value and stop decrementing it once it saturates.

Scenario: "We do not know the element count in advance, and the false positive rate climbs once we exceed the planned capacity."

A fixed BloomFilterConfig is sized for a chosen number of elements. Once you add far more than that, the bit array fills up and the false positive rate rises past the target. A Scalable Bloom Filter handles this by keeping a list of BloomFilter instances. When the newest filter reaches its capacity, it adds a larger filter with a tighter false positive rate so the combined rate stays bounded. A membership check returns true if any filter reports a possible match.

The trade-off is lookup cost. A membership check now scans every filter in the list, so a query touches more bits as the structure grows. Halving the false positive rate at each step keeps the total bounded, because the sum of a shrinking geometric series converges.