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 Optimal Parameters

The math behind Bloom filters gives us formulas for the optimal bit array size (m) and number of hash functions (k):

Where n is the expected number of elements and p is the desired false positive probability.

For example, if we want to store 1,000,000 elements with a 1% false positive rate:

Compare that to a HashSet storing 1 million strings, which could easily consume 50-100 MB. The Bloom filter uses roughly 1% of the space.

2.5 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.

Composition (Strong Ownership)

Association (Uses)

Creates

Implements

This problem falls into the data-structure-heavy category. The core challenge is algorithmic (choosing the right data structure, computing optimal parameters), not behavioral (managing states, coordinating observers). So we keep patterns minimal: two patterns that genuinely earn their place.

Strategy Pattern (Hash Strategy)

The Problem: Different hash algorithms offer different trade-offs between speed, distribution quality, and collision resistance. A URL blacklist checking millions of URLs per second might prioritize speed. A spell checker where false positives are more noticeable might prioritize distribution quality.

The Solution: The Strategy pattern lets us define a family of hash algorithms behind a common interface. The BloomFilter delegates hashing to whatever strategy it's given, without knowing which specific algorithm is being used.

Without it, we'd need to hardcode the hash algorithm or use if-else chains to select one. Every new algorithm would require modifying the BloomFilter class. With Strategy, we add new algorithms by creating new classes, following the Open/Closed Principle.

Builder Pattern (BloomFilter.Builder)

The Problem: Constructing a BloomFilter requires an expected element count (required), a false positive rate (optional, has default), and a hash strategy (optional, has default). On top of that, the bit array size and number of hash functions must be computed from these inputs. A constructor with all these parameters is confusing, and computing derived values inside a constructor violates single responsibility.

The Solution: The Builder pattern separates the construction logic. The caller sets only the parameters they care about, and the builder handles validation, default values, and derived parameter computation.

A telescoping constructor (multiple overloaded constructors) would work but scales poorly. With two optional parameters we'd need four constructors. The Builder makes intent clear: new BloomFilter.Builder(1000000).falsePositiveRate(0.001).build() is self-documenting.

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.