# Bloom Filter
Three hashes set three bits per word. A 0 bit is a definite no, a full row of 1s only a maybe.
**Time:** O(k)
**Space:** O(m)
**Difficulty:** MEDIUM
*[Interactive widget: bloom-filter-visualizer (Bloom Filter Visualizer) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/bloom-filter
---
A Bloom filter answers set membership with two answers instead of one: a confident definitely not, or an uncommitted maybe\. It never says a plain yes\. In exchange for the uncertainty it stores almost nothing: no words, only a row of bits\.

The figure above runs one with sixteen bits and three hash functions\. Three words are already in: apple, banana, and cherry\. Press play and the figure queries `lime`, a word nobody added\. Watch what the filter gets wrong, then read on to see why that wrong answer is the point\.

## Adding a word sets three bits

To add a word, the filter hashes it three times\. Hash functions `h₁`, `h₂`, and `h₃` each map the word to one position in the bit array, and the filter sets those bits to 1\. That is the entire insert\. The word itself is never stored, which is why the filter stays small, and also why it can never list its contents\.

Try it in either figure\. Type `kiwi` and press **Add**\. The badges read `h₁ → 11`, `h₂ → 14`, and `h₃ → 2`, and a line drops from each badge to its cell\. Bit 14 was already 1, because banana set it earlier\. Shared bits are normal, and they are where the maybe comes from\.

## A query reads the same three bits

A query runs the same three hashes and reads the bits instead of writing them\. If any checked bit is 0, the word was never added\. Had the word been added, that bit would be 1, and bits are never cleared\. This answer is exact\. If every checked bit is 1, the answer is maybe\. The word might be in, or other words might have covered its bits\.

Query `mango` in the figure\. The first check reads bit 3 and finds a 1, set by apple\. The second check reads bit 2 and finds a 0, and the filter stops there\. One 0 is proof, so the third bit is never read\.

The other direction is guaranteed\. Add `kiwi`, then click its chip under the array\. All three checks read 1, because the add set those bits and nothing ever clears a bit\. A member always reads maybe\. Bloom filters have false positives, but never false negatives\.

The whole data structure fits in one class\. The hash functions differ from the figure's, but the shape is the same\. The implementation panel below carries this class in Python and JavaScript:

```python
class BloomFilter:
	def __init__(self, m=16, seeds=(1, 2, 3)):
		self.bits = [0] * m
		self.m = m
		self.seeds = seeds

	def _positions(self, word):
		for seed in self.seeds:
			h = seed
			for ch in word:
				h = (h * 131 + ord(ch)) % (1 << 32)
			yield h % self.m

	def add(self, word):
		for pos in self._positions(word):
			self.bits[pos] = 1

	def __contains__(self, word):
		return all(self.bits[pos] for pos in self._positions(word))
```

## Where the maybe comes from

Bits are shared, and a bit does not record who set it\. So a word that was never added can find all of its bits on, when other words happen to cover them\. That is a false positive: a maybe for a word that was never added\.

The figure above opens on exactly that case\. `lime` hashes to bits `4`, `14`, and `7`:

1. `h₁` maps lime to bit 4\. It reads 1, set by apple and cherry\.
2. `h₂` maps lime to bit 14\. It reads 1, set by banana\.
3. `h₃` maps lime to bit 7\. It reads 1, set by banana again\.

Three 1s for a word nobody added, so the filter answers maybe\. The figure below replays the query\. Then try to fool the filter yourself\. Add words and watch the array fill: the fuller the array, the more often a maybe lies\.

*[Interactive widget: bloom-filter-visualizer — open the HTML page]*

## Sizing the filter

The maybe rate is a dial, not fate\. Three numbers set it: `m` the number of bits, `n` the number of words you plan to add, and `k` the number of hash functions\. The false\-positive rate is approximately `(1 − e^(−kn/m))^k`, where `kn/m` measures how full the array is\.

The knobs behave the way you would hope\. More bits per word push the rate down\. More words into the same array push it up\. The hash count has a sweet spot\. Too few, and one shared bit can fake a match\. Too many, and every query needs a crowded row of 1s\. For a given `m` and `n`, the best `k` is `(m/n) ln 2`\. The figure below plots the rate against `k` for the current `m` and `n`, so drag the sliders and watch the sweet spot move\.

*[Interactive widget: bloom-filter-tuning — open the HTML page]*

With `k` at its best value, the rate falls off fast:

| Bits per word | False\-positive rate |
| --- | --- |
| `6` | `5.6%` |
| `8` | `2.1%` |
| `10` | `0.8%` |
| `12` | `0.3%` |

Ten bits per word buys a wrong maybe about once in 125 queries\. The demo filter is small on purpose\. Sixteen bits for three words with `k = 3` gives a maybe rate near 8%, so false positives show up within a few tries instead of once in a hundred\.

## What a Bloom filter cannot do

Three limits follow straight from the design:

- **Delete\. **Clearing a word's bits can clear bits that other words share, so removal is unsafe\. When deletes matter, a counting Bloom filter swaps each bit for a small counter\.
- **List\. **The words were never stored, so there is nothing to enumerate\.
- **Confirm\. **The filter has no plain yes\. When an exact answer matters, a maybe must be checked against the real data\.

## Where it earns its keep

A Bloom filter earns its keep as a screen in front of an expensive check\. The cheap filter answers most queries with a fast definitely not, and only the maybes pay for the slow lookup\. Keep the filter in memory while the real data sits on disk, and almost every miss skips the disk\.

- Storage engines such as RocksDB and Cassandra keep a Bloom filter per data file, so a read for a missing key never opens the file\.
- CDNs screen one\-hit wonders: a URL is cached only after the filter says it was requested before\.
- Breach\-password checks answer against huge lists that never ship to the device\.

Keep the two answers straight and the practice problems below get easier: a 0 bit is a proof, and a 1 bit is only a rumor\. Each one is membership in disguise\. Solve it with a hash set first, then ask what a bit array would trade\.

## Code examples

### Bloom filter membership (JavaScript)

```javascript
/** Probabilistic membership set: answers "definitely not" or "maybe". */
class BloomFilter {
  constructor(m = 1024, seeds = [1, 2, 3]) {
    this.bits = new Uint8Array(m);
    this.m = m;
    this.seeds = seeds;
  }

  *positions(word) {
    for (const seed of this.seeds) {
      let h = seed >>> 0;
      for (const ch of word) {
        h = (Math.imul(h, 131) + ch.codePointAt(0)) >>> 0;
      }
      yield h % this.m;
    }
  }

  add(word) {
    for (const pos of this.positions(word)) {
      this.bits[pos] = 1;
    }
  }

  has(word) {
    for (const pos of this.positions(word)) {
      if (this.bits[pos] === 0) return false;
    }
    return true;
  }
}

```

### Bloom filter membership (Python)

```python
class BloomFilter:
    """Probabilistic membership set: answers "definitely not" or "maybe"."""

    def __init__(self, m: int = 1024, seeds: tuple[int, ...] = (1, 2, 3)) -> None:
        self.bits = bytearray(m)
        self.m = m
        self.seeds = seeds

    def _positions(self, word: str):
        for seed in self.seeds:
            h = seed
            for ch in word:
                h = (h * 131 + ord(ch)) % (1 << 32)
            yield h % self.m

    def add(self, word: str) -> None:
        for pos in self._positions(word):
            self.bits[pos] = 1

    def __contains__(self, word: str) -> bool:
        return all(self.bits[pos] for pos in self._positions(word))

```

### Bloom filter membership (Java)

```java
import java.nio.charset.StandardCharsets;

public class BloomFilter {
    private static final int FNV_PRIME = 0x01000193;

    private final int m;
    private final int k;
    private final byte[] bits;

    public BloomFilter(int expectedItems, double falsePositiveRate) {
        if (expectedItems <= 0)
            throw new IllegalArgumentException("expectedItems must be > 0");
        if (falsePositiveRate <= 0 || falsePositiveRate >= 1)
            throw new IllegalArgumentException("falsePositiveRate must be in (0, 1)");

        double ln2 = Math.log(2);
        this.m = (int) Math.ceil(-expectedItems * Math.log(falsePositiveRate) / (ln2 * ln2));
        this.k = Math.max(1, (int) Math.round((double) this.m / expectedItems * ln2));
        this.bits = new byte[(this.m + 7) / 8];
    }

    private static int fnv1a(byte[] data, int seed) {
        int h = seed;
        for (byte b : data) {
            h ^= (b & 0xFF);
            h *= FNV_PRIME;
        }
        return h;
    }

    private int[] indexes(String item) {
        byte[] data = item.getBytes(StandardCharsets.UTF_8);
        int h1 = fnv1a(data, 0x811C9DC5);
        int h2 = fnv1a(data, 0x9E3779B9) | 1; // odd => never a dead stride

        int[] idx = new int[k];
        for (int i = 0; i < k; i++) {
            idx[i] = (int) (Integer.toUnsignedLong(h1 + i * h2) % m);
        }
        return idx;
    }

    public void add(String item) {
        for (int i : indexes(item)) {
            bits[i >>> 3] |= (byte) (1 << (i & 7));
        }
    }

    public boolean mightContain(String item) {
        for (int i : indexes(item)) {
            if ((bits[i >>> 3] & (1 << (i & 7))) == 0) return false; // definitely absent
        }
        return true; // probably present
    }
}
```

### Bloom filter membership (C)

```c
#include <math.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    size_t   m;     /* bits in the array   */
    size_t   k;     /* hash functions      */
    uint8_t *bits;
} BloomFilter;

static uint32_t fnv1a(const char *s, uint32_t seed) {
    uint32_t h = seed;
    for (const unsigned char *p = (const unsigned char *)s; *p; ++p) {
        h ^= *p;
        h *= 0x01000193u;
    }
    return h;
}

/* Returns NULL on bad arguments or allocation failure. */
BloomFilter *bloom_create(size_t expected_items, double fp_rate) {
    if (expected_items == 0 || fp_rate <= 0.0 || fp_rate >= 1.0) return NULL;

    BloomFilter *bf = malloc(sizeof *bf);
    if (!bf) return NULL;

    const double ln2 = log(2.0);
    bf->m = (size_t)ceil(-(double)expected_items * log(fp_rate) / (ln2 * ln2));
    bf->k = (size_t)lround((double)bf->m / (double)expected_items * ln2);
    if (bf->k < 1) bf->k = 1;

    bf->bits = calloc((bf->m + 7) / 8, 1);
    if (!bf->bits) { free(bf); return NULL; }
    return bf;
}

void bloom_free(BloomFilter *bf) {
    if (!bf) return;
    free(bf->bits);
    free(bf);
}

void bloom_add(BloomFilter *bf, const char *item) {
    uint32_t h1 = fnv1a(item, 0x811C9DC5u);
    uint32_t h2 = fnv1a(item, 0x9E3779B9u) | 1u; /* odd => never a dead stride */

    for (size_t i = 0; i < bf->k; ++i) {
        size_t idx = (size_t)(h1 + (uint32_t)i * h2) % bf->m;
        bf->bits[idx >> 3] |= (uint8_t)(1u << (idx & 7));
    }
}

int bloom_might_contain(const BloomFilter *bf, const char *item) {
    uint32_t h1 = fnv1a(item, 0x811C9DC5u);
    uint32_t h2 = fnv1a(item, 0x9E3779B9u) | 1u;

    for (size_t i = 0; i < bf->k; ++i) {
        size_t idx = (size_t)(h1 + (uint32_t)i * h2) % bf->m;
        if (!(bf->bits[idx >> 3] & (1u << (idx & 7)))) return 0; /* definitely absent */
    }
    return 1; /* probably present */
}
```

### Bloom filter membership (CPP)

```cpp
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>

class BloomFilter {
public:
    BloomFilter(std::size_t expectedItems, double falsePositiveRate = 0.01) {
        if (expectedItems == 0)
            throw std::invalid_argument("expectedItems must be > 0");
        if (falsePositiveRate <= 0.0 || falsePositiveRate >= 1.0)
            throw std::invalid_argument("falsePositiveRate must be in (0, 1)");

        const double ln2 = std::log(2.0);
        m_ = static_cast<std::size_t>(std::ceil(
            -static_cast<double>(expectedItems) * std::log(falsePositiveRate) / (ln2 * ln2)));
        k_ = std::max<std::size_t>(1, static_cast<std::size_t>(std::llround(
            static_cast<double>(m_) / static_cast<double>(expectedItems) * ln2)));
        bits_.assign((m_ + 7) / 8, 0);
    }

    void add(const std::string& item) {
        uint32_t h1, h2;
        seeds(item, h1, h2);
        for (std::size_t i = 0; i < k_; ++i) {
            std::size_t idx = index(h1, h2, i);
            bits_[idx >> 3] |= static_cast<uint8_t>(1u << (idx & 7));
        }
    }

    bool mightContain(const std::string& item) const {
        uint32_t h1, h2;
        seeds(item, h1, h2);
        for (std::size_t i = 0; i < k_; ++i) {
            std::size_t idx = index(h1, h2, i);
            if ((bits_[idx >> 3] & (1u << (idx & 7))) == 0) return false; // definitely absent
        }
        return true; // probably present
    }

private:
    static uint32_t fnv1a(const std::string& s, uint32_t seed) {
        uint32_t h = seed;
        for (unsigned char c : s) {
            h ^= c;
            h *= 0x01000193u;
        }
        return h;
    }

    static void seeds(const std::string& s, uint32_t& h1, uint32_t& h2) {
        h1 = fnv1a(s, 0x811C9DC5u);
        h2 = fnv1a(s, 0x9E3779B9u) | 1u; // odd => never a dead stride
    }

    std::size_t index(uint32_t h1, uint32_t h2, std::size_t i) const {
        return static_cast<std::size_t>(h1 + static_cast<uint32_t>(i) * h2) % m_;
    }

    std::size_t m_ = 0;
    std::size_t k_ = 0;
    std::vector<uint8_t> bits_;
};
```

### Bloom filter membership (CSharp)

```csharp
using System;
using System.Text;

public class BloomFilter
{
    private const uint FnvPrime = 0x01000193;

    private readonly int m;
    private readonly int k;
    private readonly byte[] bits;

    public BloomFilter(int expectedItems, double falsePositiveRate = 0.01)
    {
        if (expectedItems <= 0)
            throw new ArgumentOutOfRangeException(nameof(expectedItems));
        if (falsePositiveRate <= 0 || falsePositiveRate >= 1)
            throw new ArgumentOutOfRangeException(nameof(falsePositiveRate));

        double ln2 = Math.Log(2);
        m = (int)Math.Ceiling(-expectedItems * Math.Log(falsePositiveRate) / (ln2 * ln2));
        k = Math.Max(1, (int)Math.Round((double)m / expectedItems * ln2));
        bits = new byte[(m + 7) / 8];
    }

    private static uint Fnv1a(byte[] data, uint seed)
    {
        unchecked   // FNV relies on 32-bit wraparound
        {
            uint h = seed;
            foreach (byte b in data)
            {
                h ^= b;
                h *= FnvPrime;
            }
            return h;
        }
    }

    private int[] Indexes(string item)
    {
        byte[] data = Encoding.UTF8.GetBytes(item);
        uint h1 = Fnv1a(data, 0x811C9DC5);
        uint h2 = Fnv1a(data, 0x9E3779B9) | 1;  // odd => never a dead stride

        var idx = new int[k];
        unchecked
        {
            for (int i = 0; i < k; i++)
                idx[i] = (int)((h1 + (uint)i * h2) % (uint)m);
        }
        return idx;
    }

    public void Add(string item)
    {
        foreach (int i in Indexes(item))
            bits[i >> 3] |= (byte)(1 << (i & 7));
    }

    public bool MightContain(string item)
    {
        foreach (int i in Indexes(item))
            if ((bits[i >> 3] & (1 << (i & 7))) == 0) return false;  // definitely absent
        return true;  // probably present
    }
}
```