What Is a Bloom Filter?

Suppose you are running a signup form for a service with 200 million registered users. Every time someone types a candidate username, you need to know whether it is already taken. Checking the database on every keystroke is expensive. Holding all 200 million usernames in memory on every application server is worse — that is tens of gigabytes per node, duplicated across your entire fleet, just to answer a yes-or-no question.

Most of the time, the answer is "no, that username is free." What if you had a structure that could answer "definitely free" instantly, using a tiny fraction of the memory, and only fell back to the database in the rare cases where the answer might be "taken"?

That is exactly what a Bloom filter does. But what is a Bloom filter, how does it work, and what is the catch?

Bloom Filter Definition

A Bloom filter is defined as a space-efficient probabilistic data structure used to test whether an element is a member of a set. It returns one of two answers: "definitely not in the set" or "possibly in the set."

That asymmetry is the whole idea. A Bloom filter can produce false positives — telling you an element might be present when it never was — but it can never produce a false negative. If a Bloom filter says an element is absent, that is a guarantee.

The structure was introduced by Burton Howard Bloom in his 1970 paper Space/time trade-offs in hash coding with allowable errors. It trades perfect accuracy for a dramatic reduction in memory. A Bloom filter needs roughly 9.6 bits per element to hold a 1% false positive rate — and, critically, that cost is the same whether your elements are 8-character usernames or 2-kilobyte URLs. The filter stores no elements, only bits.

How Does a Bloom Filter Work?

A Bloom filter has two components: a bit array of length m, initially all zeros, and k independent hash functions, each of which maps any element to one position in that array.

To add an element, hash it with all k functions and set the bits at all k resulting positions to 1.

To query an element, hash it the same way and inspect those k bits. If any of them is 0, the element was definitely never added — because adding it would have set that bit. If all of them are 1, the element is probably present.

A small worked example makes the trade-off obvious. Take a 16-bit array and three hash functions, and add two elements:

• alice hashes to positions 2, 7, 11 → set those bits
• bob hashes to positions 5, 7, 13 → set those bits (position 7 was already set)

index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
value:  0  0  1  0  0  1  0  1  0  0  0  1  0  1  0  0

Now query two elements that were never added:

• carol hashes to 3, 7, 11. Position 3 is 0, so carol is definitely not present. Correct.
• dave hashes to 2, 5, 13. All three bits are 1 — but they were set by alice and bob, not by dave. The filter reports possibly present. This is a false positive.

This also explains why you cannot delete from a Bloom filter. Clearing dave's bits would clear bits belonging to alice and bob, and subsequent queries for those elements would return "definitely not present" — a false negative, which breaks the structure's one guarantee.

False Positives and Sizing a Bloom Filter

The false positive rate is not a mystery; it is a function of how many bits you allocate per element and how many hash functions you use. Given n expected insertions and a target false positive probability p, the optimal bit array size is:

m = -(n × ln p) / (ln 2)²

And the optimal number of hash functions is:

k = (m / n) × ln 2

Working through the numbers for a realistic case — 55,000,000 expected insertions at a 3% false positive rate:

• 7.30 bits per element
• ~401 million bits total, or roughly 50 MB
• k = 5 hash functions

Compare that to a Java HashSet holding the same 55 million strings. Between the String objects, their backing byte arrays, and the HashMap node wrappers, a short username costs roughly 90 bytes of heap — around 5 GB in total, and more if your entries are longer. The Bloom filter is about 100 times smaller.

Tightening the error rate costs surprisingly little:

Going from 1% to 0.01% — a hundredfold improvement in accuracy — costs only twice the memory.

One warning that catches people in production: a Bloom filter does not fail loudly when you exceed its configured capacity. Insert far more than n elements and the bit array simply saturates. Nothing throws, nothing logs, but the false positive rate climbs well past the rate you configured, and eventually the filter answers "possibly present" to almost everything. Size for your real ceiling, and monitor the fill rate.

What a Bloom Filter Cannot Do

A standard Bloom filter cannot:

• Delete elements, for the reason shown above. A counting Bloom filter replaces each bit with a small counter to make deletion safe, at several times the memory cost.
• Count occurrences or report how many times an element was added.
• Enumerate its members. You cannot ask a Bloom filter what it contains — only whether a specific element might be in it.
• Resize after creation. Growing the bit array would invalidate every existing hash position. Scalable variants work by chaining additional filters as each one fills.

If you need deletion with better memory efficiency than a counting Bloom filter, a Cuckoo filter is usually the better choice.

Bloom Filter Use Cases

• Cache penetration guard. When a request arrives for a key that exists in neither the cache nor the database, it produces a cache miss and a wasted database round trip every time. A Bloom filter of all valid keys rejects these requests before they ever reach the database — an important defensive pattern in distributed caching.
• Username and email availability checks, as in the opening example.
• Web crawler URL deduplication. Crawlers use Bloom filters to avoid re-fetching pages they have already visited, where an occasional skipped page is an acceptable cost.
• Database storage engines. Cassandra, HBase, RocksDB, and Google Bigtable all keep a Bloom filter per SSTable so a lookup can skip files that definitely do not contain the requested key, avoiding expensive disk reads.
• Malicious URL and breached password checks. Early versions of Google Chrome's Safe Browsing used a Bloom filter to hold a list of dangerous URLs locally, consulting the server only on a hit. (Chrome has since moved to a different structure, but the pattern remains widely used.)
• Notification and ad deduplication, to avoid showing the same item to the same user twice.

Bloom Filter vs. Other Probabilistic Data Structures

Bloom filters are one member of a family of structures that trade exactness for space. Choosing between them comes down to what question you need answered:

If you need exact membership and can afford the memory, a Redis Set gives you constant-time lookups with no false positives at all.

Bloom Filters in Valkey and Redis

Redis and Valkey both offer Bloom filters, but they ship them differently — a distinction worth checking before you write any code against them.

In Redis 8 and later, Bloom filters are part of Redis Open Source itself. They were previously available only through the RedisBloom module or Redis Stack, so on Redis 7 and earlier you need that module loaded.

In Valkey, Bloom filters come from valkey-bloom, an official Valkey module supporting Valkey 8.0 and above. It is not built into the server — you have to load the module explicitly. Some managed services do this for you.

Both expose the same BF.* command set, which is API-compatible across the two:

• BF.RESERVE — create a filter with a given error rate and capacity
• BF.ADD / BF.MADD — add one element, or many at once
• BF.EXISTS / BF.MEXISTS — test one element, or many at once
• BF.CARD — return the number of elements added
• BF.INSERT — create and add in a single call
• BF.INFO — inspect capacity, size, number of hash functions, and fill

Filters can be created as non-scaling, which return an error once full, or scaling, which chain additional sub-filters as capacity is reached at some cost to lookup speed.

The alternative is to build a Bloom filter yourself on top of a plain Redis bitmap using SETBIT and GETBIT, hashing on the client side. This works on any server, module or not, and gives you full control over the hashing — which is exactly the approach Redisson's portable implementation takes. It also sits alongside the standard Redis data types you are probably already using for caching.

Bloom Filters in Java With Redisson

Redisson exposes Valkey and Redis Bloom filters as ordinary Java objects, with three implementations covering different scale points.

RBloomFilter<T> is the portable implementation, available in the Community Edition. It hashes on the client using a 64-bit hash derived from a 128-bit hash (xxHash and FarmHash) and stores the bits server-side. It is thread-safe, extends RExpirable so you can attach a TTL, and offers Sync, Async, Reactive, and RxJava APIs.

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;

public class BloomFilterExample {

    public static void main(String[] args) {
        // connects to 127.0.0.1:6379 by default
        RedissonClient redisson = Redisson.create();

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("visited-urls");

        // Must be sized before first use.
        // Returns false if the filter was already initialized.
        bloomFilter.tryInit(55_000_000L, 0.03);

        bloomFilter.add("https://redisson.pro/glossary/");
        bloomFilter.add("https://redisson.pro/blog/");

        // false -> definitely never added
        // true  -> probably added (3% chance of a false positive)
        boolean visited = bloomFilter.contains("https://redisson.pro/docs/");

        bloomFilter.getExpectedInsertions(); // 55000000
        bloomFilter.getFalseProbability();   // 0.03
        bloomFilter.getSize();               // bit array size
        bloomFilter.getHashIterations();     // number of hash functions
        bloomFilter.count();                 // approximate elements added

        redisson.shutdown();
    }
}

Note that tryInit must be called before any add or contains, and that a single RBloomFilter holds up to 2³² bits.

For larger workloads, Redisson PRO adds two more options. RClusteredBloomFilter partitions a filter's state across every node in a cluster, raising the ceiling to 2⁶³ bits while shrinking the memory consumed by unused bits. RBloomFilterNative delegates to the server's native Bloom filter commands instead of hashing client-side, cutting network round trips for bulk operations.

For complete code examples of all three, see Bloom Filter for Valkey & Redis on Java.

Frequently Asked Questions

What Does a Bloom Filter Do?

It tests whether an element belongs to a set using a fraction of the memory required to store the set itself. It answers "definitely not present" with certainty, and "possibly present" with a configurable error rate.

What Are the Disadvantages of a Bloom Filter?

False positives, no deletion, no way to enumerate members or count occurrences, and no resizing after creation. It also degrades silently rather than failing when you exceed its configured capacity.

What Is the Difference Between Redis and a Bloom Filter?

They are different categories of thing. Redis is a data store; a Bloom filter is a data structure. Redis supports Bloom filters as one of the many data types it can store, alongside strings, hashes, sets, and sorted sets.

What Is Better Than a Bloom Filter?

It depends on the question. Use a Cuckoo filter when you need deletion, a HyperLogLog when you need distinct counts rather than membership, and a plain Redis Set when you need exact answers and can afford the memory.

Redisson provides more than 50 distributed Java objects and services on Valkey and Redis, Bloom filters among them. Learn more about Redisson PRO.

Similar Terms

• HyperLogLog
• Java BitSet
• Redis Set
• Cache Miss