Bloom filters - Eli Bendersky's website

A probabilistic cache for set membership

Bloom filters were introduced by Burton Bloom in a 1970 paper, "Space/Time Trade-offs in Hash Coding with Allowable Errors," to solve a specific problem: efficiently checking whether an item belongs to a set when the cost of a definitive answer is high. The classic motivating scenario is a disk-based lookup: before reading an entire file to find an entry, we want a cheap pre-check that can reliably tell us when the entry is not there.

The filter provides two guarantees with different strengths:

• If the filter says a key is not present, that answer is 100% certain — we can skip the disk read entirely.
• If it says a key is present, there is a small chance of a false positive; in that case we just proceed with the actual read, and the cost is only the wasted I/O.

This design is most effective when most queries are negative — "is this key in that file?" answered "no" — which is exactly the regime Bloom's paper targeted. As Bloom put it:

The new hash-coding methods to be introduced are suggested for applications in which the great majority of messages to be tested will not belong to the given set.

Structure and operations

A Bloom filter is essentially a hash table with open addressing, but it stores no keys — only bits. It consists of:

• An array of m bits, all initially 0.
• A set of k hash functions, each mapping an input to an integer in [0, m-1].

Inserting an item means computing all k hashes and setting the corresponding bits to 1. Testing membership is similar: compute the k hashes; if any bit is 0, the answer is definitively "false." If all bits are 1, the answer is "true" — but with a probability of error, because those bits may have been set by other items that hash to the same positions.

Consider a small example with m=16 and k=3. After inserting "x" (bits 1, 6, 15 set) and "y" (bits 6, 9, 13 set; bit 6 is shared), a test for "x" succeeds as a true positive. A test for "w", whose hashes point to bits 3, 9, and 13, fails immediately because bit 3 is zero — a true negative. But a test for "v", with hashes landing on bits 9, 13, and 15, returns "true" even though "v" was never inserted: that is a false positive.

Note that by the law of contraposition, every "false" result is guaranteed correct; errors only occur in one direction.

Implementing a filter

A straightforward Go implementation is compact. The key trick is to avoid implementing k independent hash functions; instead, use double hashing to derive k hashes from just two seed hashes. The repository also includes a CalculateParams function that, given an expected number of items and a desired false-positive rate, returns the optimal m and k.

// New creates a new BloomFilter with capacity m, using k hash functions.
// You can calculate m and k from the number of elements you expect the
// filter to hold and the desired error rate using CalculateParams.
func New(m uint64, k uint64) *BloomFilter {
  return &BloomFilter{
    m:      m,
    k:      k,
    bitset: newBitset(m),
    seed1:  maphash.MakeSeed(),
    seed2:  maphash.MakeSeed(),
  }
}

type BloomFilter struct {
  m      uint64
  k      uint64
  bitset []uint64

  // seeds for the double hashing scheme.
  seed1, seed2 maphash.Seed
}

// Insert a data item into the bloom filter.
func (bf *BloomFilter) Insert(data []byte) {
  h1 := maphash.Bytes(bf.seed1, data)
  h2 := maphash.Bytes(bf.seed2, data)
  for i := range bf.k {
    loc := (h1 + i*h2) % bf.m
    bitsetSet(bf.bitset, loc)
  }
}

// Test if the given data item is in the bloom filter. If Test returns false,
// it's guaranteed that data was never added to the filter. If it returns true,
// there's an eps probability of this being a false positive. eps depends on
// the parameters the filter was created with (see CalculateParams).
func (bf *BloomFilter) Test(data []byte) bool {
  h1 := maphash.Bytes(bf.seed1, data)
  h2 := maphash.Bytes(bf.seed2, data)
  for i := range bf.k {
    loc := (h1 + i*h2) % bf.m
    if !bitsetTest(bf.bitset, loc) {
      return false
    }
  }
  return true
}

// CalculateParams calculates optimal parameters for a Bloom filter that's
// intended to contain n elements with error (false positive) rate eps.
func CalculateParams(n uint64, eps float64) (m uint64, k uint64) {
  // The formulae we derived are:
  // (m/n) = -ln(eps)/(ln(2)*ln(2))
  // k = (m/n)ln(2)

  ln2 := math.Log(2)
  mdivn := -math.Log(eps) / (ln2 * ln2)
  m = uint64(math.Ceil(float64(n) * mdivn))
  k = uint64(math.Ceil(mdivn * ln2))
  return
}

Real-world sizing and speed

To see why these filters matter, consider a realistic requirement: cache membership for about 1 billion items with a false-positive rate of 1%. Running CalculateParams for these inputs yields approximately m = 9.6 billion bits and k = 7 — that is, roughly 1.2 GB of memory to serve as a gatekeeper for arbitrarily large items.

CalculateParams(1000000000, 0.01) ===> (9585058378 7)

The lookup cost is constant: seven hash evaluations, independent of the number of items inserted and with no worst-case data patterns that degrade asymptotic performance. In the simple Go implementation above, a benchmark on a typical machine shows about 80 nanoseconds per lookup — far faster than querying disk even when the on-disk data is indexed. Reading just a few KiB for an index would take orders of magnitude longer.

The asymmetry is the point: for the 99% of queries that are true negatives, the filter avoids any disk access. For the remaining 1%, where the filter says "present" but the data is absent, the cost is one wasted read — a small price for the vast speedup on the common path.

The math behind the error rate

Given m, n (keys inserted), and k (hash functions), and assuming the hashes distribute bits uniformly at random:

• The probability that a specific hash from a specific insertion does not set a given bit is 1 - 1/m.
• After k hashes for n insertions, the probability that a bit remains 0 is approximately e^(-kn/m).
• Thus the probability a bit is set to 1 is 1 - e^(-kn/m).

The false-positive rate (probability that all k hashes of a new, absent key land on already-set bits) is then (1 - e^(-kn/m))^k. Minimizing this expression with respect to k gives the optimal number of hash functions:

k_opt = (m/n) * ln(2)

Substituting this back into the error equation yields:

error = (1/2)^k = (0.6185)^(m/n)

More often, you start with a target error rate and solve for the required bits per element:

m/n = -ln(error) / (ln 2)^2

For a 1% false-positive rate, this is approximately 9.6 bits per element. For 100,000 elements, the filter needs at least 958,000 bits, and the optimal number of hash functions is about 7.