Software applications often need to determine whether a particular piece of data exists before performing another operation. A database may need to check whether a record exists, a cache may need to determine whether an item has been stored, or a storage system may need to know whether a key could exist before searching through files on disk. When the number of values becomes very large, performing these checks repeatedly can become expensive.
A traditional data structure such as a HashSet can provide fast membership checks, but it has to store the actual values. For very large datasets, that storage requirement can become significant. A Bloom filter takes a different approach. Instead of storing the values themselves, it stores a compact representation of the information needed to determine whether a value might belong to a set.
A Bloom filter is a probabilistic data structure. It can tell us that an element is definitely not present, but it cannot always tell us that an element is definitely present. A positive result means that the element may be present and should normally be checked against the original data source. A negative result, however, means that the element is definitely not present in the set represented by the filter.
This property makes Bloom filters useful when a membership check is inexpensive, but the operation that follows it is expensive. Instead of immediately querying a database, reading a file, or making a network request, an application can first consult a Bloom filter and eliminate requests that are guaranteed to fail.
This article explains how Bloom filters work and how to implement one in Java.
1. What is a Bloom Filter?
A Bloom filter is built around two fundamental components: a collection of bits and one or more hash functions. When the filter is created, all of its bits are initially set to 0. When a value is added, the value is processed by several hash functions. Each hash function produces a position in the bit array, and those positions are changed from 0 to 1.
For example, imagine a Bloom filter containing 16 bits:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Suppose the value "Java" is processed by three hash functions and they produce the positions 2, 6, and 11. The filter changes those positions to 1:
0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0
The important detail is that the string "Java" is not stored in the Bloom filter. The filter only records that certain positions in its bit array have been enabled. If another value is added, its hash functions may select some of the same positions. That is expected behavior. Multiple values can share the same bits.
2. How Does a Bloom Filter Check an Element?
The lookup process is similar to insertion. Suppose "Java" was previously inserted and caused positions 2, 6, and 11 to become 1. When we ask whether "Java" is present, the same hashing process produces the same positions. The Bloom filter checks those bits.
If all three bits are 1, the filter returns a positive result. However, that result does not prove that "Java" was inserted.
Now suppose "Python" was never inserted. Its hash functions might happen to produce positions that are also already set to 1 because other values were inserted earlier. The filter would then also return a positive result for "Python".
This is known as a false positive. The important distinction is therefore:
false → definitely not present
true → possibly present
A standard Bloom filter does not produce false negatives. If one of the positions calculated for a value contains 0, the value could not have been inserted using that filter configuration because insertion would have set that position to 1. This property is one of the defining characteristics of the data structure.
3. Why False Positives Happen
False positives are caused by collisions between the hash positions of different values. Imagine a filter containing many values. Every insertion sets several bits to 1. As more values are inserted, more of the bit array becomes occupied.
Eventually, an element that was never inserted may have all of its calculated positions already set to 1. The Bloom filter cannot determine why a particular bit is set. It only knows that the bit is set.
For example, suppose three existing values have collectively enabled these positions: 2, 6, 11, 14. A new value that hashes to 2, 6, 14 would appear to be present even though it was never inserted. The more saturated the bit array becomes, the greater the chance of this happening.
This means that false positives are not an implementation error. They are part of the design of a Bloom filter. The purpose of configuring a Bloom filter is to control how frequently these false positives occur.
3.1 False-Positive Probability
The false-positive probability depends primarily on three values: the number of bits in the filter, the number of inserted elements, and the number of hash functions. These are commonly represented as:
m = number of bits
n = number of inserted elements
k = number of hash functions
These factors determine how many positions are available for storing the information produced by the hash functions and how likely different elements are to map to the same positions.
As more elements are added to the filter, more bits are changed from 0 to 1. When a large portion of the filter is already occupied, new elements are more likely to map to positions that have already been set. This increases the chance that the filter will report that an element might be present even though it was never inserted.
The size of the filter therefore needs to match the expected number of elements. A larger filter provides more available positions for the inserted values and can reduce the likelihood of false positives. The number of hash functions also affects this probability, so choosing an appropriate number is important when configuring a Bloom filter.
The design is ultimately a trade-off between memory usage and accuracy. If an application requires a lower false-positive rate, it generally needs to allocate more memory for the Bloom filter and configure it appropriately for the expected number of elements.
3.2 Choosing the Number of Hash Functions
The number of hash functions also affects the behavior of a Bloom filter. If too few hash functions are used, each inserted value sets only a small number of bits. This can result in a higher false-positive rate because different values have fewer positions that distinguish them.
Using more hash functions provides more positions for each value, but there is a cost. Every insertion and lookup has to perform more hashing, and setting too many bits can cause the filter to become saturated more quickly.
There is an optimal number of hash functions for a particular combination of filter size and expected number of elements. The commonly used approximation is:
k = (m / n) ln(2)
where m represents the number of bits and n represents the expected number of inserted elements. This is why Bloom filters should not be configured by choosing an arbitrary number of hash functions without considering the expected workload.
4. Implementing a Bloom Filter in Java
A Bloom filter can be implemented in Java using the BitSet class. BitSet provides a convenient way to manage the underlying collection of bits. The following implementation accepts a filter size and the number of hash functions. Each inserted value is hashed several times, and the resulting positions are enabled in the BitSet.
public class BloomFilter {
private final BitSet bitSet;
private final int size;
private final int numberOfHashFunctions;
public BloomFilter(int size, int numberOfHashFunctions) {
if (size <= 0) {
throw new IllegalArgumentException("Size must be greater than zero");
}
if (numberOfHashFunctions <= 0) {
throw new IllegalArgumentException("Number of hash functions must be greater than zero");
}
this.size = size;
this.numberOfHashFunctions = numberOfHashFunctions;
this.bitSet = new BitSet(size);
}
public void add(String value) {
for (int i = 0; i < numberOfHashFunctions; i++) {
int index = hash(value, i);
bitSet.set(index);
}
}
public boolean mightContain(String value) {
for (int i = 0; i < numberOfHashFunctions; i++) {
int index = hash(value, i);
if (!bitSet.get(index)) {
return false;
}
}
return true;
}
private int hash(String value, int seed) {
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
int hash = seed;
for (byte b : bytes) {
hash = 31 * hash + b;
}
hash ^= hash >>> 16;
return Math.floorMod(hash, size);
}
}
The add() method calculates the required positions and sets them in the bit array. The mightContain() method performs the reverse operation. It calculates the same positions and checks whether all of them are enabled.
If even one bit is disabled, the method immediately returns false. If all bits are enabled, it returns true. The method is named mightContain() deliberately because the value could be present, or the result could be a false positive.
Using the Bloom Filter
The implementation can be tested with a small Java program:
public class Main {
public static void main(String[] args) {
BloomFilter filter = new BloomFilter(1000, 5);
filter.add("Java");
filter.add("Quarkus");
filter.add("Docker");
IO.println(filter.mightContain("Java"));
IO.println(filter.mightContain("Quarkus"));
IO.println(filter.mightContain("Python"));
}
}
The first two checks should return true because those values were inserted. The check for Python should normally return false, although a Bloom filter can return true for a value that was never inserted if a collision occurs.
This implementation demonstrates the fundamental mechanics of a Bloom filter. Production applications should usually use a well-tested library rather than implementing the hashing and sizing strategy themselves.
5. Using Guava’s BloomFilter
Google Guava provides a ready-to-use BloomFilter implementation for Java applications. For a Maven project, add the Guava dependency:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>33.7.2-jre</version>
</dependency>
A Bloom filter for integers can then be created with an expected number of elements and an acceptable false-positive probability:
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {
public static void main(String[] args) {
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 500, 0.01);
filter.put(1);
filter.put(2);
filter.put(3);
IO.println(filter.mightContain(1));
IO.println(filter.mightContain(2));
IO.println(filter.mightContain(100));
}
}
Here, the filter is configured for approximately 500 expected insertions and a target false-positive probability of 0.01, or one percent. Guava exposes put() for adding elements and mightContain() for membership checks. The important part is how the result should be interpreted.
if (!filter.mightContain(id)) {
// Definitely not present
}
A false result can be used to avoid an expensive operation. A true result should normally be followed by another check when correctness matters:
if (filter.mightContain(id)) {
// Check the actual database or cache
}
This pattern allows the Bloom filter to reduce unnecessary work without becoming the authoritative source of application data.
6. Can a Bloom Filter Delete an Element?
A standard Bloom filter cannot safely remove an individual element because the same bit can be shared by multiple elements. When two values produce the same hash position, that position is set to 1 when both values are inserted. The filter does not keep information about which value caused the bit to be set.
If the application removes one of those values and changes the shared bit back to 0, the remaining value may no longer pass the membership check even though it is still part of the set. This can introduce a false negative, which is not allowed by the normal behaviour of a Bloom filter.
For this reason, a standard Bloom filter is designed primarily for adding values and checking membership rather than performing individual deletions. When an application needs deletion support, a different variation, such as a counting Bloom filter, can be used because it maintains additional information that allows entries to be removed more safely.
7. Where Bloom Filters Are Useful
One of the most common uses is preventing unnecessary database or storage lookups. Imagine an application that receives requests for customer IDs. The application could query the database every time a request arrives. If many requested IDs do not exist, the database receives a large number of unnecessary queries.
A Bloom filter can contain the IDs that are known to exist. The application first checks the filter:
if (!customerFilter.mightContain(customerId)) {
return null;
}
A negative result means the application does not need to query the database. A positive result means the application performs the normal database lookup:
if (customerFilter.mightContain(customerId)) {
return customerRepository.findById(customerId);
}
This pattern can also be used around caches and storage systems. The Bloom filter acts as an inexpensive first check before an operation that costs more time, memory, I/O, or network resources. Bloom filters are used in systems where avoiding unnecessary disk or storage access can provide a significant benefit.
They can also be useful when an application needs to maintain a compact membership summary for a very large collection. Because the filter stores bits rather than the original values, its memory requirements can be much smaller than storing the complete set.
8. Conclusion
A Bloom filter is a compact probabilistic data structure designed to answer membership questions efficiently. Its key property is simple: a negative result is definitive, while a positive result is only a possibility. The filter achieves this by using hash functions to map elements onto a bit array.
The trade-off is false positives. The probability of those false positives depends on factors such as the number of bits, the number of inserted elements, and the number of hash functions. Designing the filter around a realistic expected number of elements and an acceptable false-positive rate is essential.
Java developers can implement a Bloom filter with classes such as BitSet, but libraries such as Guava and Apache Commons Collections provide established implementations and additional functionality. Guava provides a straightforward API based around put() and mightContain(), while Apache Commons Collections offers more configurable Bloom filter implementations and representations.
The most important point is that a Bloom filter is normally not the final source of truth. It is a fast, memory-efficient way to eliminate work. A false result can prevent an unnecessary lookup, while a true result can be followed by a check against the actual database, cache, or storage system. That makes Bloom filters a useful tool when an application needs to perform large numbers of membership checks without storing an equally large amount of membership data in memory.
9. Download the Source Code
You can download the full source code of this example here: bloom filters explained
