Hard PHP

Bloom Filters in Practice: How They Work, False Positive Math, Sizing, PHP and Redis

Skip millions of database lookups with a few MB of bits. How Bloom filters work, the false positive math, sizing, PHP code and Redis BF commands.

18 Nov, 2026 10 min Updated 23 Oct, 2026 7 Code blocks
Diagram
graph LR A[Item] --> B[Hash twice: h1 and h2] B --> C[k bit positions: h1 plus i times h2 mod m] C --> D[Bit array of m bits] D --> E{All k bits set?} E -->|no| F[Definitely not present] E -->|yes| G[Probably present - confirm in DB]

Every email we send first checks a suppression list: 50 million addresses that bounced, complained or unsubscribed. The check is a primary-key lookup, fast on its own, but the newsletter job sends 3 million emails an hour, and 99.7% of those lookups return "not suppressed". We were paying for 3 million database round trips an hour mostly to learn that nothing was there.

A Bloom filter answers exactly that question cheaply: "is this item definitely not in the set?" It never gives a false "no", it sometimes gives a false "yes", and it does that in a fixed amount of memory regardless of how long the items are. For our list, 86 MiB in memory replaced almost all of those queries. The remaining 0.3% plus a 0.1% false positive rate still go to the database for the real answer.

How a Bloom Filter Works

A Bloom filter is a bit array of m bits, all zero at the start, plus k hash functions that each map an item to one of the m positions.

  • Add: hash the item k times and set those k bits to 1.
  • Query: hash the item k times. If any of those bits is 0, the item was never added, guaranteed. If all are 1, the item was probably added, or those bits were set by other items.
graph LR A[Item] --> B[Hash twice: h1 and h2] B --> C[k bit positions: h1 plus i times h2 mod m] C --> D[Bit array of m bits] D --> E{All k bits set?} E -->|no| F[Definitely not present] E -->|yes| G[Probably present - confirm in DB]

There is no way to delete in a plain Bloom filter, because clearing a bit could erase evidence of other items that share it. There is also no way to list the items: the filter stores fingerprints of membership, not data. Both are features as much as limits: the memory cost per item stays small and constant, whether the item is a 10-byte email or a 2 KB URL.

You do not need k independent hash functions. Kirsch and Mitzenmacher showed that two base hashes combined as h1 + i * h2 for i = 0 .. k-1 give the same asymptotic false positive rate. Every practical implementation does this.

The Math: False Positives and Sizing

After inserting n items, the chance that a specific bit is still 0 is about e^(-kn/m). A false positive needs all k bits of a non-member to be 1, which gives the formulas you size with:

n = items you expect to insert
m = bits in the array
k = number of hash functions
p = false positive rate

p  ~ (1 - e^(-k*n/m))^k            false positive rate for given m, n, k
m  = -n * ln(p) / (ln 2)^2         bits needed for target p
k  = (m / n) * ln 2                optimal number of hash functions

target p     bits per item     k
1%           9.59              7
0.1%         14.38             10
0.01%        19.17             13

Useful takeaways from the table:

  • Each tenfold improvement in false positive rate costs about 4.8 extra bits per item. Going from 1% to 0.1% is cheap.
  • Memory depends on n and p only, never on item length. 50 million emails at 0.1% need 718,879,379 bits, about 86 MiB. The same emails as a Redis set would be several gigabytes.
  • k grows slowly. More hash functions than optimal makes things worse, because the array fills up faster.
  • Overfilling degrades gracefully but quickly. A filter sized for 1 million items at 1% holding 2 million items is around 15% false positives. Always size for growth, and rebuild when you approach capacity.

Implementation in PHP

A PHP string is a perfectly good bit array: one byte holds eight bits, and indexing into a string is O(1). hash('xxh128'), available since PHP 8.1, is fast and well distributed; we slice two 32-bit integers out of its digest for double hashing.

namespace App\Support;

use InvalidArgumentException;

final class BloomFilter
{
    private string $bits;

    private function __construct(
        public readonly int $size,      // m, number of bits
        public readonly int $hashes,    // k
        ?string $bits = null,
    ) {
        $this->bits = $bits ?? str_repeat("\0", intdiv($size + 7, 8));
    }

    /** Size the filter for $expected items at false positive rate $fpRate. */
    public static function forCapacity(int $expected, float $fpRate): self
    {
        if ($expected < 1 || $fpRate <= 0.0 || $fpRate >= 1.0) {
            throw new InvalidArgumentException('Need expected >= 1 and 0 < fpRate < 1');
        }
        $m = (int) ceil(-$expected * log($fpRate) / (M_LN2 ** 2));
        $k = max(1, (int) round($m / $expected * M_LN2));

        return new self($m, $k);
    }

    public function add(string $item): void
    {
        foreach ($this->positions($item) as $bit) {
            $byte = $bit >> 3;
            $this->bits[$byte] = chr(ord($this->bits[$byte]) | (1 << ($bit & 7)));
        }
    }

    /** false = definitely absent, true = probably present. */
    public function mightContain(string $item): bool
    {
        foreach ($this->positions($item) as $bit) {
            if ((ord($this->bits[$bit >> 3]) & (1 << ($bit & 7))) === 0) {
                return false;
            }
        }

        return true;
    }

    /** Kirsch-Mitzenmacher double hashing: k positions from two base hashes. */
    private function positions(string $item): array
    {
        $digest = hash('xxh128', $item, true);
        $h1 = unpack('N', $digest, 0)[1];
        $h2 = unpack('N', $digest, 4)[1] | 1;   // odd, so the stride never collapses to 0

        $out = [];
        for ($i = 0; $i < $this->hashes; $i++) {
            $out[] = ($h1 + $i * $h2) % $this->size;
        }

        return $out;
    }

    public function serialize(): string
    {
        return pack('JJ', $this->size, $this->hashes) . $this->bits;
    }

    public static function unserialize(string $data): self
    {
        ['m' => $m, 'k' => $k] = unpack('Jm/Jk', $data);

        return new self($m, $k, substr($data, 16));
    }
}

Positions are computed modulo m with 32-bit base hashes, which is fine for filters up to a few billion bits. The serialize() format is just a 16-byte header plus the raw bit array, so you can store it in a file, in object storage, or as a plain Redis string and load it in milliseconds.

Using it as a pre-check in front of the database looks like this:

use App\Support\BloomFilter;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Storage;

// Build once (nightly job): 50M suppressed emails at 0.1% -> about 86 MiB.
$filter = BloomFilter::forCapacity(50_000_000, 0.001);
DB::table('suppressed_emails')->orderBy('id')->lazyById(10_000)->each(
    fn ($row) => $filter->add(strtolower($row->email)),
);
Storage::put('bloom/suppressed.bin', $filter->serialize());

// Hot path: most addresses are NOT suppressed and never touch the database.
function isSuppressed(BloomFilter $filter, string $email): bool
{
    $email = strtolower($email);
    if (! $filter->mightContain($email)) {
        return false;                       // definite answer, no query
    }

    return DB::table('suppressed_emails')->where('email', $email)->exists();
}

The filter only ever short-circuits the "no" answer. A "maybe" falls through to the authoritative store, so correctness never depends on the filter.

Verifying the Math

Before trusting the formula with production traffic, measure it. This throwaway script builds a filter for 100,000 members at 1% and probes 200,000 non-members:

# Check the formula against reality before trusting it in production.
import hashlib
import math


def positions(item: str, m: int, k: int) -> list[int]:
    d = hashlib.blake2b(item.encode(), digest_size=16).digest()
    h1 = int.from_bytes(d[:8], "big")
    h2 = int.from_bytes(d[8:], "big") | 1
    return [(h1 + i * h2) % m for i in range(k)]


n, p = 100_000, 0.01
m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
k = max(1, round(m / n * math.log(2)))
bits = bytearray(m)
for i in range(n):
    for pos in positions(f"member-{i}", m, k):
        bits[pos] = 1

trials = 200_000
false_hits = sum(
    all(bits[pos] for pos in positions(f"stranger-{i}", m, k)) for i in range(trials)
)
print(f"m={m} k={k} measured={false_hits / trials:.4%} target={p:.2%}")
# m=958506 k=7 measured=~1.0% target=1.00%

If the measured rate is far above the target, the usual culprits are a weak hash (for example crc32 on very similar keys), positions that are not reduced modulo m correctly, or more items than planned.

Bloom Filters in Redis

When several app servers need the same filter and it changes during the day, keep it in Redis instead of rebuilding per process. Redis 8 includes Bloom filters natively; on older versions they come from Redis Stack or the RedisBloom module.

# Redis 8 ships Bloom filters in the core distribution
# (older versions: Redis Stack or the RedisBloom module).
redis-cli BF.RESERVE emails:suppressed 0.001 50000000
redis-cli BF.MADD emails:suppressed [email protected] [email protected]
redis-cli BF.EXISTS emails:suppressed [email protected]      # 1 = probably
redis-cli BF.EXISTS emails:suppressed [email protected]      # 0 = definitely not
redis-cli BF.INFO emails:suppressed

BF.RESERVE takes the error rate and the capacity and does the sizing math for you. If you insert beyond capacity, RedisBloom by default adds a new sub-filter (scaling) instead of silently degrading, at the cost of extra memory and slightly slower lookups. From Laravel, send the commands raw:

namespace App\Support;

use Illuminate\Support\Facades\Redis;

final class RedisBloom
{
    public function __construct(private string $key) {}

    public function add(string ...$items): void
    {
        Redis::executeRaw(['BF.MADD', $this->key, ...$items]);
    }

    public function mightContain(string $item): bool
    {
        return (int) Redis::executeRaw(['BF.EXISTS', $this->key, $item]) === 1;
    }
}

Typical Redis use cases: "has this user already seen this post" for feed deduplication, crawler URL frontiers ("have we fetched this URL"), username or coupon-code availability pre-checks, and rate limiting "first time we see this IP" logic. If plain Redis is all you have, the same algorithm works with SETBIT/GETBIT on a string key, computing the positions in PHP and pipelining the commands.

Testing It

Three properties matter: no false negatives ever, a false positive rate close to the target, and lossless serialization. With a fixed set of generated keys, these tests are deterministic, because the hash is deterministic.

// tests/Unit/BloomFilterTest.php
use App\Support\BloomFilter;

it('never returns a false negative', function () {
    $filter = BloomFilter::forCapacity(10_000, 0.01);
    foreach (range(1, 10_000) as $i) {
        $filter->add("user-{$i}@example.com");
    }

    foreach (range(1, 10_000) as $i) {
        expect($filter->mightContain("user-{$i}@example.com"))->toBeTrue();
    }
});

it('keeps the false positive rate near the target', function () {
    $filter = BloomFilter::forCapacity(10_000, 0.01);
    foreach (range(1, 10_000) as $i) {
        $filter->add("user-{$i}");
    }

    $hits = 0;
    foreach (range(1, 50_000) as $i) {
        $hits += $filter->mightContain("stranger-{$i}") ? 1 : 0;
    }

    expect($hits / 50_000)->toBeLessThan(0.02);
});

it('survives a serialize round trip', function () {
    $filter = BloomFilter::forCapacity(1_000, 0.01);
    $filter->add('hello');

    $copy = BloomFilter::unserialize($filter->serialize());

    expect($copy->size)->toBe($filter->size)
        ->and($copy->hashes)->toBe($filter->hashes)
        ->and($copy->mightContain('hello'))->toBeTrue()
        ->and($copy->mightContain('world'))->toBeFalse();
});

The false positive test asserts against twice the target rather than the exact target: the measured rate fluctuates a little with the specific keys, and the test is there to catch a broken hash or sizing bug, which shows up as 10% or 50%, not 1.1%.

Common Pitfalls

  • Treating "maybe" as "yes". A Bloom filter can only skip work on "no". Anything that blocks a user, charges money or deletes data on a "maybe" must confirm against the source of truth.
  • Undersizing. The false positive rate grows quickly past capacity. Size for the expected maximum, monitor the number of inserted items, and rebuild or switch to a scalable filter before you get there.
  • Trying to delete. Clearing bits creates false negatives. If you need deletions, use a counting Bloom filter or a Cuckoo filter (CF.* commands in Redis), or rebuild periodically from the database.
  • Inconsistent normalization. [email protected] and [email protected] hash differently. Normalize exactly the same way on insert and on query.
  • Weak or correlated hashes. crc32 of similar strings, or two hashes derived from the same 32 bits, cluster positions and raise the false positive rate. Use a good 64- or 128-bit hash and derive h1 and h2 from different parts of it.
  • Using a filter where a set fits. For 10,000 items, a PHP array or a Redis set is exact and still tiny.

When to Use a Bloom Filter and When Not To

Use one when:

  • most lookups are for items that are not in the set, and a negative answer saves a database query, disk read or network call;
  • the set is large (millions of items) and memory matters;
  • a small rate of extra "maybe" lookups is acceptable because a slower exact check follows;
  • you need to ship membership data to many nodes or clients cheaply.

Do not use one when:

  • you need exact answers with no fallback;
  • you need to delete items, enumerate them or attach values to them;
  • the set is small enough that an exact structure costs only a few megabytes;
  • most queries are for members, because then almost every lookup still hits the database and the filter saves nothing.

For our suppression list the filter turned 3 million queries an hour into about 12,000, and the database stopped showing up in the newsletter job's profile at all.

Interactive challenge

Try the challenge

Practice what you just learned. Write your solution, reveal hints if you get stuck.

Instructions

Implement Bloom filter sizing and a small Bloom filter. optimalSize(int $n, float $p): array (Python: optimal_size(n, p) returning a tuple) returns [m, k] where m = ceil(-n * ln(p) / (ln 2)^2) and k = max(1, round(m / n * ln 2)); throw InvalidArgumentException (Python: ValueError) unless n >= 1 and 0 < p < 1. BloomFilter(m, k) has: indexes(item) returning the k bit positions using double hashing, h1 = crc32 of the item's UTF-8 bytes, h2 = crc32 of those bytes reversed, bitwise OR 1, and position i = (h1 + i * h2) mod m for i from 0 to k-1, in that order (PHP: crc32($item) and crc32(strrev($item)); Python: zlib.crc32(data) and zlib.crc32(data[::-1])); add(item) sets all those bits; mightContain(item) (Python: might_contain) returns false if any of the item's bits is unset, true otherwise; bitCount() (Python: bit_count) returns the number of distinct bits currently set.

Starter code

php
/**
 * Optimal Bloom filter size for $n items at false positive rate $p.
 *
 * @return array{0: int, 1: int} [m bits, k hash functions]
 */
function optimalSize(int $n, float $p): array
{
    // TODO: throw InvalidArgumentException unless $n >= 1 and 0 < $p < 1
    // TODO: m = ceil(-n * ln(p) / (ln 2)^2), k = max(1, round(m / n * ln 2))
    throw new LogicException('TODO');
}

final class BloomFilter
{
    /** @var array<int, bool> */
    private array $bits = [];

    public function __construct(public readonly int $m, public readonly int $k) {}

    /** @return list<int> */
    public function indexes(string $item): array
    {
        // TODO: h1 = crc32($item), h2 = crc32(strrev($item)) | 1
        // TODO: return [(h1 + i * h2) % m for i = 0 .. k-1]
        throw new LogicException('TODO');
    }

    public function add(string $item): void
    {
        // TODO: set every bit returned by indexes()
        throw new LogicException('TODO');
    }

    public function mightContain(string $item): bool
    {
        // TODO: false as soon as one bit is not set, true otherwise
        throw new LogicException('TODO');
    }

    public function bitCount(): int
    {
        // TODO: number of distinct bits that are set
        throw new LogicException('TODO');
    }
}
python
import math
import zlib


def optimal_size(n: int, p: float) -> tuple[int, int]:
    """Return (m bits, k hash functions) for n items at false positive rate p."""
    # TODO: raise ValueError unless n >= 1 and 0 < p < 1
    # TODO: m = ceil(-n * ln(p) / (ln 2)^2), k = max(1, round(m / n * ln 2))
    raise NotImplementedError


class BloomFilter:
    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        self.bits: set[int] = set()

    def indexes(self, item: str) -> list[int]:
        # TODO: data = item.encode(); h1 = zlib.crc32(data); h2 = zlib.crc32(data[::-1]) | 1
        # TODO: return [(h1 + i * h2) % m for i in range(k)]
        raise NotImplementedError

    def add(self, item: str) -> None:
        # TODO: set every bit returned by indexes()
        raise NotImplementedError

    def might_contain(self, item: str) -> bool:
        # TODO: False as soon as one bit is not set, True otherwise
        raise NotImplementedError

    def bit_count(self) -> int:
        # TODO: number of distinct bits that are set
        raise NotImplementedError

Your solution

Hints

All hints revealed
Hint 1

Use log() / math.log() for the natural logarithm; ceil m before computing k from it

Hint 2

A set (or an array keyed by position) is enough to store which bits are on; bitCount is its size

Hint 3

Force h2 to be odd with | 1 so consecutive positions never repeat when h2 would be 0

Solution · php
/**
 * Optimal Bloom filter size for $n items at false positive rate $p.
 *
 * @return array{0: int, 1: int} [m bits, k hash functions]
 */
function optimalSize(int $n, float $p): array
{
    if ($n < 1 || $p <= 0.0 || $p >= 1.0) {
        throw new InvalidArgumentException('Need n >= 1 and 0 < p < 1');
    }
    $m = (int) ceil(-$n * log($p) / (log(2) ** 2));
    $k = max(1, (int) round($m / $n * log(2)));

    return [$m, $k];
}

final class BloomFilter
{
    /** @var array<int, bool> */
    private array $bits = [];

    public function __construct(public readonly int $m, public readonly int $k) {}

    /** @return list<int> */
    public function indexes(string $item): array
    {
        $h1 = crc32($item);
        $h2 = crc32(strrev($item)) | 1;
        $out = [];
        for ($i = 0; $i < $this->k; $i++) {
            $out[] = ($h1 + $i * $h2) % $this->m;
        }

        return $out;
    }

    public function add(string $item): void
    {
        foreach ($this->indexes($item) as $i) {
            $this->bits[$i] = true;
        }
    }

    public function mightContain(string $item): bool
    {
        foreach ($this->indexes($item) as $i) {
            if (!isset($this->bits[$i])) {
                return false;
            }
        }

        return true;
    }

    public function bitCount(): int
    {
        return count($this->bits);
    }
}
Solution · python
import math
import zlib


def optimal_size(n: int, p: float) -> tuple[int, int]:
    """Return (m bits, k hash functions) for n items at false positive rate p."""
    if n < 1 or not 0 < p < 1:
        raise ValueError("need n >= 1 and 0 < p < 1")
    m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
    k = max(1, round(m / n * math.log(2)))
    return m, k


class BloomFilter:
    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        self.bits: set[int] = set()

    def indexes(self, item: str) -> list[int]:
        data = item.encode()
        h1 = zlib.crc32(data)
        h2 = zlib.crc32(data[::-1]) | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item: str) -> None:
        self.bits.update(self.indexes(item))

    def might_contain(self, item: str) -> bool:
        return all(i in self.bits for i in self.indexes(item))

    def bit_count(self) -> int:
        return len(self.bits)

More from PHP