A Bloom Filter is a probabilistic data structure used to efficiently determine whether an element is a member of a set. It is designed to be extremely fast and highly memory-efficient, making it ideal for applications that need to handle large datasets while using minimal memory.

A Bloom Filter can return two possible results:

• Definitely Not Present – If the Bloom Filter indicates that an element is not in the set, it is guaranteed to be absent. False negatives are impossible.

• Possibly Present – If the Bloom Filter indicates that an element is in the set, the element may or may not actually exist in the set. This is because Bloom Filters can produce false positives.

In simple terms:

• No false negatives – If it says "not present", the element is definitely not in the set.

• Possible false positives – If it says "present", the element might actually be present, or it could be a false positive.

Because of this trade-off, Bloom Filters are widely used in systems where speed and memory efficiency are more important than perfect accuracy, such as databases, caches, web browsers, distributed systems, and networking applications.

1. Clarifying Requirements

Candidate: What type of elements will the Bloom Filter store? Should it support only strings, or also integers and arbitrary objects?
Interviewer: Let's keep it simple and support strings. That covers most real-world use cases, such as URLs, usernames, email addresses, and API keys.
Candidate: What operations should the Bloom Filter provide? Should it only support add()and mightContain(), or should it also support deletion?
Interviewer: A standard Bloom Filter supports only add()and mightContain(). Deletion is not required because it can lead to false negatives. If deletion is needed, a Counting Bloom Filter would be a better choice.
Candidate: Should the desired false positive rate be configurable, or should we use a fixed value?
Interviewer: The false positive rate should be configurable by the caller. If no value is provided, use a sensible default, such as 1% (0.01).
Candidate: Will this Bloom Filter be used in a multi-threaded environment? Should it be thread-safe?
Interviewer: Yes. Assume multiple threads may add elements and check membership concurrently, such as in a web service that maintains a URL blacklist or cache.
Candidate: Should the caller be able to choose the hash function or hashing algorithm?
Interviewer: Yes. The design should allow the hash function to be configurable or pluggable, so different applications can choose the algorithm that best fits their performance and distribution requirements.

2. Identifying Core Components

Whiteboard

2.4 Entity overview

Whiteboard

Core Components

Design Summary

These components form the core architecture of our Bloom Filter. Each component has a well-defined responsibility, resulting in a modular and extensible design.

• Hashing is abstracted behind the HashStrategy interface, allowing different hashing algorithms to be plugged in without modifying the Bloom Filter.
• Configuration is computed once during construction and stored in an immutable BloomFilterConfig object.
• The BitArray efficiently stores the filter's state using a compact sequence of bits.
• The BloomFilter acts as the central coordinator, combining the bit array and hash strategy to provide fast, memory-efficient membership testing.
• The Builder simplifies object creation by computing optimal parameters and exposing a flexible configuration API.

Note

In a real Low-Level Design (LLD) interview, you are not expected to know or implement specific hash algorithms such as MurmurHash, FNV-1a, or DJB2. These implementations are included here to demonstrate a production-quality design.

For an interview, a much simpler approach is sufficient. You can implement a basic polynomial rolling hash (for example, hash = hash × seed + character) and use different seed values to simulate multiple independent hash functions.

What interviewers are evaluating is your design, not your knowledge of hashing algorithms. They expect you to demonstrate:

• The use of the Strategy Design Pattern to make hashing pluggable.
• How multiple independent hash functions reduce the false positive rate.
• How hash values are mapped to valid bit array indices.
• A clean, modular, and extensible object-oriented design.

With the core components identified, the next step is to define their attributes, behaviors, and relationships in the class diagram.

3. Designing Classes and Relationships

Now that we have identified the core components of our Bloom Filter, the next step is to design the classes that implement these components.

For each class, we will define:

• Attributes – the data the class stores.
• Methods – the operations the class performs.
• Relationships – how the class interacts with other classes.

By the end of this section, we'll have a complete object-oriented design that is modular, extensible, and easy to maintain.

Note

To keep the discussion focused on the design, we will omit trivial getter and setter methods and concentrate only on the core behaviors of each class.

3.1 Class Definitions

We'll follow a bottom-up approach, starting with the simplest building blocks and gradually moving toward the main class.

The design will be covered in the following order:

1. Interfaces – Define contracts for interchangeable behaviors.
2. Data Classes – Store the application's state and configuration.
3. Implementations – Provide concrete implementations of the interfaces.
4. Core Classes – Coordinate all components to implement the Bloom Filter.

3.1.1 Interface: HashStrategy

A Bloom Filter relies on hash functions to map elements to positions in the bit array.

One option would be to hardcode a single hashing algorithm inside the BloomFilter class. However, different applications have different requirements:

• A URL blacklist may prioritize high performance.
• A spell checker may prioritize better hash distribution to reduce collisions.
• Other applications may require a completely different hashing strategy.

To keep the design flexible and extensible, we introduce the Strategy Design Pattern.

The HashStrategy interface defines a common contract for all hashing algorithms. The BloomFilter depends only on this interface, allowing different hashing implementations to be plugged in without modifying the Bloom Filter itself.

Responsibilities

• Define a common interface for generating hash values.
• Map an element to one or more valid positions in the bit array.
• Allow different hashing algorithms to be used interchangeably.
• Promote extensibility by decoupling the Bloom Filter from specific hash implementations.

This design follows the Open/Closed Principle: the Bloom Filter is open for extension (new hash algorithms can be added) but closed for modification (existing code remains unchanged).

Whiteboard

Methods

Why Do We Need the seed Parameter?

The seed parameter allows us to generate multiple independent hash values using a single hashing algorithm.

Instead of implementing k different hash functions, we invoke the same hash() method k times, each with a different seed value:

• Seed 0 → First hash value
• Seed 1 → Second hash value
• Seed 2 → Third hash value
• ...
• Seed k − 1 → k^th hash value

Each seed produces a different hash value for the same element, resulting in k distinct bit positions in the bit array.

This approach keeps the implementation simple while achieving the effect of multiple independent hash functions.

3.1.2 Data Class: BitArray

The BitArray is the storage backbone of the Bloom Filter. It maintains the sequence of bits that records whether particular hash positions have been set.

One option would be to store a raw boolean[] (or BitSet) directly inside the BloomFilter class. However, encapsulating it within a dedicated BitArray class provides a cleaner and more maintainable design.

The BitArray class abstracts low-level bit operations and exposes a simple API for manipulating bits, allowing the BloomFilter to focus solely on coordinating hash functions and membership testing.

Responsibilities

• Store a fixed-size array of bits.
• Set a bit at a specified position.
• Retrieve the value of a bit.
• Clear all bits, resetting the array to its initial state.
• Hide low-level bit manipulation behind a simple, reusable interface.

By separating storage logic from business logic, the design follows the Single Responsibility Principle (SRP) and makes the Bloom Filter easier to understand, test, and maintain.

Whiteboard

Attributes

Attribute	Type	Description	Mutable?
bits	boolean[]	The underlying bit array used to store the Bloom Filter's state.	Yes (individual bits can be updated)
size	int	The total number of bits in the bit array.	No

Methods

Method	Description
BitArray(size)	Creates a bit array of the specified size with all bits initialized to false.
set(position)	Sets the bit at the specified position to true.
get(position)	Returns the value of the bit at the specified position.
clear()	Resets all bits in the array to false, restoring it to its initial empty state.

---

BloomFilterConfig

Constructing a Bloom Filter requires several configuration parameters. Some of these parameters are provided by the caller, while others are derived automatically.

For example:

• Caller-provided parameters
  • Expected number of elements (n)
  • Desired false positive probability (p)
• Computed parameters
  • Optimal bit array size (m)
  • Optimal number of hash functions (k)

Instead of recomputing these derived values whenever they are needed, we encapsulate them in a dedicated configuration object.

The BloomFilterConfig class is an immutable configuration object that stores both the caller-provided inputs and the computed optimal parameters. Once created, its state cannot be modified, ensuring that every BloomFilter instance operates with a consistent and valid configuration throughout its its lifetime.

Whiteboard

Attributes

Attribute	Type	Description	Mutable?
expectedElements	int	The expected number of elements that the Bloom Filter is designed to store.	No
falsePositiveRate	double	The desired false positive probability (for example, 0.01 for a 1% false positive rate).	No
bitArraySize	int	The computed optimal size of the bit array (m).	No
numHashFunctions	int	The computed optimal number of hash functions (k).	No

Methods

Method	Description
BloomFilterConfig(expectedElements, falsePositiveRate)	Creates a configuration object by storing the caller-provided parameters and computing the optimal bit array size (m) and number of hash functions (k).

All fields in BloomFilterConfig are immutable. Once a configuration object is created, its state cannot be modified. This ensures that every BloomFilter instance operates with a consistent configuration and allows the configuration object to be safely shared across multiple threads without requiring synchronization.

---

3.1.4 Core Class: BloomFilter

The BloomFilter is the central class of the system. It coordinates all the other components to provide a fast, memory-efficient API for probabilistic membership testing.

Rather than implementing hashing or bit manipulation itself, the BloomFilter delegates these responsibilities to dedicated components:

• HashStrategy generates hash values for each element.
• BitArray stores and manages the bits corresponding to those hash values.
• BloomFilterConfig provides the configuration parameters, including the bit array size and the number of hash functions.

The BloomFilter accepts string elements, uses the configured HashStrategy to generate k hash values, maps them to valid bit positions, and updates or queries the BitArray accordingly.

Responsibilities

• Provide the public add() operation for inserting elements.
• Provide the public mightContain() operation for membership testing.
• Coordinate hashing and bit array operations.
• Use the immutable configuration to determine the bit array size and the number of hash functions.
• Expose a simple, easy-to-use API while hiding the internal implementation details.

The BloomFilter acts as the orchestrator of the system, ensuring that all components work together to deliver fast and memory-efficient probabilistic set membership testing.

Whiteboard

Attributes

Attribute	Type	Description	Mutable?
config	BloomFilterConfig	Stores the immutable configuration, including the optimal bit array size and number of hash functions.	No
bitArray	BitArray	Maintains the bit array used for probabilistic membership tracking.	Yes (bits are updated when elements are added)
hashStrategy	HashStrategy	Defines the hashing algorithm used to generate bit positions.	No

Methods

Method	Description
add(element)	Computes k hash values for the element and sets the corresponding bits in the bit array.
mightContain(element)	Computes k hash values for the element and returns true only if all corresponding bits are set; otherwise, returns false.
clear()	Resets the bit array by clearing all bits, restoring the Bloom Filter to its initial empty state.

---

Key Design Principles

1. Single Responsibility Principle (SRP)

The BloomFilter is responsible for coordinating the overall membership-testing process. It delegates specific responsibilities to specialized components:

• HashStrategy generates hash values.
• BitArray manages bit storage and manipulation.
• BloomFilterConfig provides the immutable configuration.

This separation of concerns keeps each class focused on a single responsibility.

---

2. Encapsulation

The internal implementation details, including bit manipulation and hash computations, are hidden from the caller.

The public API exposes only three operations:

• add()
• mightContain()
• clear()

This simplifies usage while allowing the internal implementation to evolve without affecting client code.

---

3. Thread Safety

The Bloom Filter is intended to support concurrent access.

To prevent race conditions when multiple threads operate on the same filter:

• add() should be thread-safe because it modifies the bit array.
• mightContain() should safely read the bit array while updates may be occurring.

A production implementation can achieve thread safety using synchronization, locks, or atomic bit operations, depending on the performance requirements.

---

3.1.5 Builder Class: BloomFilter.Builder

Constructing a BloomFilter requires several configuration parameters. Some are mandatory, while others have sensible defaults.

Required Parameter

• Expected number of elements

Optional Parameters

• False positive rate (default: 1% or 0.01)
• Hash strategy (default: MurmurHashStrategy)

Using a constructor with multiple parameters can quickly become difficult to read and maintain, especially as additional options are introduced.

To address this, we use the Builder Design Pattern.

The BloomFilter.Builder allows callers to specify only the parameters they want to customize while relying on sensible defaults for the rest. During construction, the builder also computes the derived configuration values, such as the optimal bit array size (m) and the optimal number of hash functions (k), before creating the BloomFilter instance.

Responsibilities

• Collect caller-provided configuration values.
• Apply default values for optional parameters.
• Validate input parameters.
• Compute the optimal bit array size (m) and number of hash functions (k).
• Construct and return a fully configured BloomFilter instance.

Using the Builder pattern improves readability, flexibility, and maintainability, while keeping the BloomFilter constructor simple and focused.

Whiteboard

Methods

Method	Description
Builder(expectedElements)	Creates a builder with the required expected number of elements.
falsePositiveRate(rate)	Sets the desired false positive probability. If not specified, the default value is 0.01 (1%).
hashStrategy(strategy)	Specifies the hash strategy to use. If not provided, the builder uses MurmurHashStrategy by default.
build()	Validates the input parameters, computes the optimal bit array size (m) and number of hash functions (k), and returns a fully configured BloomFilter instance.

---

3.2 Key Design Patterns

Although a Bloom Filter is primarily an algorithmic data structure, applying the right design patterns results in a cleaner, more modular, and extensible implementation.

In this design, two patterns provide the greatest value:

1. Strategy Pattern – Makes the hashing algorithm interchangeable.
2. Builder Pattern – Simplifies the construction of a BloomFilter with configurable parameters and sensible defaults.

---

3.2.1 Strategy Pattern (Hash Strategy)

The Problem

Different hashing algorithms have different characteristics. Some prioritize speed, while others provide better hash distribution to reduce collisions.

For example:

• A URL blacklist that processes millions of requests per second may prioritize fast hashing.
• A spell checker or deduplication system may prioritize uniform distribution to minimize false positives.

Hardcoding a single hashing algorithm inside the BloomFilter would tightly couple the class to one implementation, making it difficult to change or extend.

---

The Solution

The Strategy Design Pattern encapsulates each hashing algorithm behind a common HashStrategy interface.

Instead of performing hashing directly, the BloomFilter delegates the responsibility to the configured HashStrategy.

This design allows different hashing algorithms to be plugged in without modifying the BloomFilter class.

New hashing algorithms can be introduced simply by creating a new class that implements the HashStrategy interface.

Benefits

• Extensible: New hashing algorithms can be added without changing existing code.
• Interchangeable: Different hash strategies can be selected based on application requirements.
• Loosely Coupled: The BloomFilter depends only on the HashStrategy interface, not on concrete implementations.
• Open/Closed Principle: The system is open for extension but closed for modification, since new strategies are added through new classes rather than changes to existing ones.

This makes the Bloom Filter flexible enough to support different performance and distribution requirements while maintaining a clean object-oriented design.

Whiteboard

3.2.2 Builder Pattern (BloomFilter.Builder)

The Problem

A BloomFilter requires several configuration parameters during construction.

• Required parameter:
  • Expected number of elements
• Optional parameters:
  • False positive rate
  • Hash strategy

In addition, the bit array size (m) and the number of hash functions (k) are derived automatically from these inputs.

Using a constructor with multiple parameters makes object creation difficult to read, error-prone, and hard to extend as new configuration options are added.

---

The Solution

The Builder Design Pattern separates the construction of a BloomFilter from its representation.

The caller specifies only the configuration values they want to customize, while the builder:

• Validates the input parameters.
• Applies sensible default values for optional parameters.
• Computes the optimal bit array size (m) and number of hash functions (k).
• Constructs and returns a fully configured BloomFilter instance.

This results in a clean, readable, and flexible API.