A Brief Introduction to Bloom Filters

1. Introducing the Scenario

Scenario: Deduplicating URLs at the Hundred-Million Scale

Take large-scale web crawling as an example. When a crawler targets a specific keyword, the number of URLs to fetch can reach hundreds of millions. Duplicate URLs not only waste crawling resources but can also send the crawler into an infinite loop or make it fetch useless pages, seriously hurting crawl efficiency and data quality.

Traditional Approaches

Store them in a database and add a unique constraint
- I/O bottleneck
Use a cache such as a HashSet
- High memory overhead

Optimizing the Approach

Since deduplicating a URL crawler can tolerate false positives, and with such large data volumes a small number of mistakes is perfectly acceptable:

Use a bitmap with single-hash compressed storage, using a binary array to record whether a URL has appeared, which takes up much less memory
- Memory estimate for ten billion URLs at a $1\%$ false positive rate: with $n=10^{10}$ items, the bitmap is $m=10^{12}$ in size, using $125G$
Optimize the bitmap further—this is the Bloom filter. It uses multiple ($k$) hash functions to map each element onto multiple ($k$) bits in the binary array, representing one element with several bits

2. Bloom Filter Basics

Concept

A Bloom filter is a probabilistic data structure built on a bit array. It can efficiently tell you that an element "might be present" or "definitely isn't present".

Space efficient: it stores data in a bit array, saving a great deal of space.
Fast queries: insertion and lookup both run in constant time $O(k)$ , where $k$ is the number of hash functions.
Possible false positives: it can misjudge, i.e. it may report an element that was never inserted as being present (a false positive), but it will never misjudge an element as absent.

Diagram

Initializing a Bloom filter

Inserting X and Y

Querying: definitely absent vs. possibly present Definitely absent: query and insert Z. When Z is queried, one bit is found to be 1 while the other is 0, which proves it definitely isn't present.

Possibly present: When D is queried, both bits are 1, so there's no way to tell whether it actually exists—it might be a false positive or a true positive; in reality it's a false positive.

When X' is queried, both bits are 1, so again there's no way to tell—it might be a false positive or a true positive; in reality it's a true positive.

Parameters

Parameter meanings

Number of elements to insert, $n$
Length of the bit array, $m$
Number of hash functions, $k$
False positive rate, $p$

Derivation

Probability that a given bit is still $0$ after inserting $1$ element with $k$ hashes: $(1−\frac{1}{m})^k$
Probability that a given bit is still $0$ after inserting $n$ elements with $k$ hashes: $(1−\frac{1}{m})^{nk}$
Probability that a given bit has been set to $1$ after inserting $n$ elements with $k$ hashes: $1−(1−\frac{1}{m})^{nk}$
Probability that all the bits produced by $k$ hashes of one inserted element have already been set to $1$ : $(1−(1−\frac{1}{m})^{nk})^k$
From this we can derive the false positive rate $p=(1−e^{−\frac{nk}{m}})^k$

Estimating parameters Given the number of insertions $n$ and the false positive rate $p$ :

Bit array length $m=−\frac{nlnp}{(ln2)^2}$
Number of hash functions $k=\frac{m}{n}ln2$

Characteristics

Insert and query, but no delete Clearly a Bloom filter can't support deletion, because multiple elements may hash to the same location in the filter—see the diagram above.

Space usage Memory estimate for ten billion URLs at a $1\%$ false positive rate:

Bitmap: length $m=10^{12}$ , using $125G$
Bloom filter: bit array length $m=9.59∗10^{10}$ , using about $12G$

3. Bloom Filters in Practice: Using Guava

In real projects you'll usually use the Bloom filter from Google's Guava library. Guava Maven repository

A Small Example

Add the Guava dependency

CodeBlock Loading...

The core Bloom filter methods in the Guava library:

put(): insert an element
mightContain(): check whether an element might be present

Example

CodeBlock Loading...

Insert $1e7$ items and query $1e7$ items; $100075$ were misjudged.

4. A Deep Dive into the Guava BloomFilter Source Code

The BloomFilter Class

It wraps the core Bloom filter logic—adding and querying elements, computing initialization parameters (such as bit array size and number of hash functions), and so on.

create(Funnel, int, double): the lightweight user-facing API
create(Funnel, long, double): the advanced API
create(funnel, expectedInsertions, fpp, Strategy): the core implementation

The factory creates a BloomFilter

CodeBlock Loading...

Core methods

CodeBlock Loading...

The Funnel interface

The Funnel interface's main job is to "inject" an object's state into a PrimitiveSink, producing a continuous byte sequence—that's what makes it possible to use a Bloom filter with custom structures.

JAVA

public interface Funnel<T> {
    void funnel(T from, PrimitiveSink into);
}

T from: the object to convert.
PrimitiveSink into: the container that receives the object's data. PrimitiveSink provides many methods for writing primitive types and strings into one unified byte stream.

Guava ships with built-in funnels such as integerFunnel(), stringFunnel(Charset), byteArrayFunnel(), and so on.

Example

Goods

JAVA

@Data  
@AllArgsConstructor  
public class Goods {  
    private final int id;  
    private final String name;  
}

PojoBloomFilter

CodeBlock Loading...

What Funnel does

Ensures consistency: Funnel guarantees that the same structure gets the same preprocessing before hashing.
Controls granularity: for a custom class, if you want to use a Bloom filter, you can pick which fields to inject—for example, inject Goods' id and name.

The Strategy Interface (default implementation: MURMUR128MITZ64)

The Strategy interface defines the Bloom filter's hashing strategy plus the concrete operations for inserting and querying elements. The default is MURMUR128MITZ64.

MURMUR128: the 128-bit variant of MurmurHash3
MITZ: named after Google engineer Mitz Pettel, who devised the "double hashing" trick described below
64: uses 64 bits each time

You'll notice it doesn't really use $k$ hash functions; the implementation computes one hash and splits it into two fields. "Less Hashing, Same Performance: Building a Better Bloom Filter" proposes an optimization: you only need to compute two independent hash functions to build a Bloom filter equivalent to one using many hash functions. $$gi(x)=h1(x)+i·h_2(x)$$

CodeBlock Loading...

The index passed into the BitArray is index = (combinedHash & Long.MAX_VALUE) % bitSize), the purpose being to make combinedHash positive—otherwise you can't take the modulo by bitSize (a negative index would throw an exception).

The BitArray Module

BitArray is the heart of the Bloom filter's low-level implementation, responsible for storing and managing the bit array.

CodeBlock Loading...

Uses a long (64-bit) array
bitCount is the number of bits set to $1$ ; the native Long.bitCount() method is used to gauge how full the filter is
In get, the index is logically shifted right to get the long element index, and an AND is used to get the specific bit index after the modulo
set uses compareAndSet for atomic updates
putAll ORs two BitArrays together, used for merging Bloom filters

5. Bloom Filter Variants

Counting Bloom Filter

Adds delete operations on top of an ordinary Bloom filter
Done through bit counting
Drawback: it takes up more space

Bloomfilter

Counting Bloomfilter

Periodically Rebuilding the Bloom Filter

Rebuild periodically
Delete the old Bloom filter
Rebuild a new Bloom filter

6. Real-World Scenarios

Product IDs at Large Scale

A user requests a product
Unlike URL filtering for a crawler, a mistake isn't allowed
Use a database?
Use a cache?
Use a Bloom filter?

1. Introducing the Scenario

Scenario: Deduplicating URLs at the Hundred-Million Scale

Traditional Approaches

Store them in a database and add a unique constraint
- I/O bottleneck
Use a cache such as a HashSet
- High memory overhead

Optimizing the Approach

Since deduplicating a URL crawler can tolerate false positives, and with such large data volumes a small number of mistakes is perfectly acceptable:

Use a bitmap with single-hash compressed storage, using a binary array to record whether a URL has appeared, which takes up much less memory
- Memory estimate for ten billion URLs at a $1\%$ false positive rate: with $n=10^{10}$ items, the bitmap is $m=10^{12}$ in size, using $125G$
Optimize the bitmap further—this is the Bloom filter. It uses multiple ($k$) hash functions to map each element onto multiple ($k$) bits in the binary array, representing one element with several bits

2. Bloom Filter Basics

Concept

A Bloom filter is a probabilistic data structure built on a bit array. It can efficiently tell you that an element "might be present" or "definitely isn't present".

Space efficient: it stores data in a bit array, saving a great deal of space.
Fast queries: insertion and lookup both run in constant time $O(k)$ , where $k$ is the number of hash functions.
Possible false positives: it can misjudge, i.e. it may report an element that was never inserted as being present (a false positive), but it will never misjudge an element as absent.

Diagram

Initializing a Bloom filter

Inserting X and Y

Querying: definitely absent vs. possibly present Definitely absent: query and insert Z. When Z is queried, one bit is found to be 1 while the other is 0, which proves it definitely isn't present.

Possibly present: When D is queried, both bits are 1, so there's no way to tell whether it actually exists—it might be a false positive or a true positive; in reality it's a false positive.

When X' is queried, both bits are 1, so again there's no way to tell—it might be a false positive or a true positive; in reality it's a true positive.

Parameters

Parameter meanings

Number of elements to insert, $n$
Length of the bit array, $m$
Number of hash functions, $k$
False positive rate, $p$

Derivation

Probability that a given bit is still $0$ after inserting $1$ element with $k$ hashes: $(1−\frac{1}{m})^k$
Probability that a given bit is still $0$ after inserting $n$ elements with $k$ hashes: $(1−\frac{1}{m})^{nk}$
Probability that a given bit has been set to $1$ after inserting $n$ elements with $k$ hashes: $1−(1−\frac{1}{m})^{nk}$
Probability that all the bits produced by $k$ hashes of one inserted element have already been set to $1$ : $(1−(1−\frac{1}{m})^{nk})^k$
From this we can derive the false positive rate $p=(1−e^{−\frac{nk}{m}})^k$

Estimating parameters Given the number of insertions $n$ and the false positive rate $p$ :

Bit array length $m=−\frac{nlnp}{(ln2)^2}$
Number of hash functions $k=\frac{m}{n}ln2$

Characteristics

Insert and query, but no delete Clearly a Bloom filter can't support deletion, because multiple elements may hash to the same location in the filter—see the diagram above.

Space usage Memory estimate for ten billion URLs at a $1\%$ false positive rate:

Bitmap: length $m=10^{12}$ , using $125G$
Bloom filter: bit array length $m=9.59∗10^{10}$ , using about $12G$

3. Bloom Filters in Practice: Using Guava

In real projects you'll usually use the Bloom filter from Google's Guava library. Guava Maven repository

A Small Example

Add the Guava dependency

XML

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->  
<dependency>  
    <groupId>com.google.guava</groupId>  
    <artifactId>guava</artifactId>  
    <version>32.1.2-jre</version>  
</dependency>

CodeBlock Loading...

The core Bloom filter methods in the Guava library:

put(): insert an element
mightContain(): check whether an element might be present

Example

JAVA

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample
{
    private static Integer expectedInsertions = 10000000;
    private static Double fpp = 0.01;

    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

    public static void main(String[] args)
    {
        for (int i = 0; i < expectedInsertions; i++)
        {
            bloomFilter.put(i);
        }

        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions * 2; i++)
        {
            if (bloomFilter.mightContain(i))
            {
                count++;
            }
        }

        System.out.println("一共误判了：" + count);
    }
}

CodeBlock Loading...

Insert $1e7$ items and query $1e7$ items; $100075$ were misjudged.

4. A Deep Dive into the Guava BloomFilter Source Code

The BloomFilter Class

It wraps the core Bloom filter logic—adding and querying elements, computing initialization parameters (such as bit array size and number of hash functions), and so on.

create(Funnel, int, double): the lightweight user-facing API
create(Funnel, long, double): the advanced API
create(funnel, expectedInsertions, fpp, Strategy): the core implementation

The factory creates a BloomFilter

JAVA

public static <T extends @Nullable Object> BloomFilter<T> create(  
    Funnel<? super T> funnel, int expectedInsertions, double fpp) {  
  return create(funnel, (long) expectedInsertions, fpp);  
}

public static <T extends @Nullable Object> BloomFilter<T> create(  
    Funnel<? super T> funnel, long expectedInsertions, double fpp) {  
  return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);  
}

CodeBlock Loading...

Core methods

JAVA

public boolean put(@ParametricNullness T object) {  
    return strategy.put(object, funnel, numHashFunctions, bits);  
}

public boolean mightContain(@ParametricNullness T object) {  
    return strategy.mightContain(object, funnel, numHashFunctions, bits);  
}

static int optimalNumOfHashFunctions(long n, long m) {  
    // (m / n) * log(2), but avoid truncation due to division!  
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));  
}

static long optimalNumOfBits(long n, double p) {  
    if (p == 0) {  
        p = Double.MIN_VALUE;  
    }  
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));  
}

CodeBlock Loading...

The Funnel interface

JAVA

public interface Funnel<T> {
    void funnel(T from, PrimitiveSink into);
}

T from: the object to convert.
PrimitiveSink into: the container that receives the object's data. PrimitiveSink provides many methods for writing primitive types and strings into one unified byte stream.

Guava ships with built-in funnels such as integerFunnel(), stringFunnel(Charset), byteArrayFunnel(), and so on.

Example

Goods

JAVA

@Data  
@AllArgsConstructor  
public class Goods {  
    private final int id;  
    private final String name;  
}

PojoBloomFilter

JAVA

public static void main(String[] args)  
{  
    // 预计插入10000个Person对象，误判率设为0.01  
    BloomFilter<Goods> personBloomFilter = BloomFilter.create(  
            PersonFunnel.INSTANCE,  
            10000,  
            0.01  
    );  
  
    // 创建并插入一个Goods对象  
    Goods apple = new Goods(1, "apple");  
    personBloomFilter.put(apple);  
  
    // 查询某个对象是否可能存在  
    Goods queryGoods1 = new Goods(1, "apple");  
    if (personBloomFilter.mightContain(queryGoods1))  
    {  
        System.out.println(queryGoods1 + "可能存在于布隆过滤器中");  
    }  
    else  
    {  
        System.out.println(queryGoods1 + "肯定不存在于布隆过滤器中");  
    }  
  
    Goods queryGoods2 = new Goods(2, "banana");  
    if (personBloomFilter.mightContain(queryGoods2))  
    {  
        System.out.println(queryGoods2 + "可能存在于布隆过滤器中");  
    }  
    else  
    {  
        System.out.println(queryGoods2 + "肯定不存在于布隆过滤器中");  
    }  
}

CodeBlock Loading...

What Funnel does

Ensures consistency: Funnel guarantees that the same structure gets the same preprocessing before hashing.
Controls granularity: for a custom class, if you want to use a Bloom filter, you can pick which fields to inject—for example, inject Goods' id and name.

The Strategy Interface (default implementation: MURMUR128MITZ64)

The Strategy interface defines the Bloom filter's hashing strategy plus the concrete operations for inserting and querying elements. The default is MURMUR128MITZ64.

MURMUR128: the 128-bit variant of MurmurHash3
MITZ: named after Google engineer Mitz Pettel, who devised the "double hashing" trick described below
64: uses 64 bits each time

JAVA

public <T extends @Nullable Object> boolean put(  
    @ParametricNullness T object,  
    Funnel<? super T> funnel,  
    int numHashFunctions,  
    LockFreeBitArray bits) {  
        long bitSize = bits.bitSize();  
        byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();  
        long hash1 = lowerEight(bytes);  
        long hash2 = upperEight(bytes);  
        boolean bitsChanged = false;  
        long combinedHash = hash1;  
        for (int i = 0; i < numHashFunctions; i++) {  
            // Make the combined hash positive and indexable  
            bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);  
            combinedHash += hash2;  
        }  
    return bitsChanged;  
}

CodeBlock Loading...

The BitArray Module

BitArray is the heart of the Bloom filter's low-level implementation, responsible for storing and managing the bit array.

JAVA

static final class LockFreeBitArray {
    private static final int LONG_ADDRESSABLE_BITS = 6;  
    final AtomicLongArray data;  
    private final LongAddable bitCount;
    
    LockFreeBitArray(long bits) {  
        checkArgument(bits > 0, "data length is zero!");  
        // Avoid delegating to this(long[]), since AtomicLongArray(long[]) will clone its input and  
        // thus double memory usage.  
        this.data =  new AtomicLongArray(Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING)));  
        this.bitCount = LongAddables.create();  
    }
    
    boolean set(long bitIndex) {  
      if (get(bitIndex)) {  
          return false;  
      }  
      int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);  
      long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex  
      long oldValue;  
      long newValue;  
      do {  
          oldValue = data.get(longIndex);  
          newValue = oldValue | mask;  
          if (oldValue == newValue) {  
              return false;  
          }  
      } while (!data.compareAndSet(longIndex, oldValue, newValue));  
      // We turned the bit on, so increment bitCount.  
      bitCount.increment();  
      return true;  
    }
    
    boolean get(long bitIndex) {  
      return (data.get((int) (bitIndex >>> LONG_ADDRESSABLE_BITS)) & (1L << bitIndex)) != 0;  
    }
}

CodeBlock Loading...

Uses a long (64-bit) array
bitCount is the number of bits set to $1$ ; the native Long.bitCount() method is used to gauge how full the filter is
In get, the index is logically shifted right to get the long element index, and an AND is used to get the specific bit index after the modulo
set uses compareAndSet for atomic updates
putAll ORs two BitArrays together, used for merging Bloom filters

5. Bloom Filter Variants

Counting Bloom Filter

Adds delete operations on top of an ordinary Bloom filter
Done through bit counting
Drawback: it takes up more space

Bloomfilter

Counting Bloomfilter

Periodically Rebuilding the Bloom Filter

Rebuild periodically
Delete the old Bloom filter
Rebuild a new Bloom filter

6. Real-World Scenarios

Product IDs at Large Scale

A user requests a product
Unlike URL filtering for a crawler, a mistake isn't allowed
Use a database?
Use a cache?
Use a Bloom filter?