Experiments and implementations · Intermediate

Measure Bloom-filter false positives by condition

Separate inserted and absent datasets, vary bits, hashes and seeds, and compare every observation with the approximation.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Use absent queries as the denominator
  2. Predict the effect of m and k
  3. Use deterministic hashing and disjoint sets
  4. Check inserted keys as a separate invariant
  5. Do not add deletion by clearing shared bits
  6. Connect false positives to downstream work
  7. Reuse matched datasets without claiming independence
  8. Exercise: calculate the defined conditional rate
  9. Ask Logeia about this articleCheck your understanding

Use absent queries as the denominator

A Bloom filter answers definitely absent when any required bit is zero and possibly present when all are set. Insert one thousand keys, then query five thousand different keys known to be absent. The false-positive rate is positive absent queries divided by those five thousand absent queries. Mixing inserted keys into the denominator would measure a different conditional quantity.

A false positive can mean extra work for a downstream exact lookup, not permission to treat uncertain membership as authorization or a confirmed deletion target. This experiment fixes inserted and query sets, varies bit count m and hash count k, and compares a theoretical approximation with finite-sample observations. Define the denominator and the use of uncertain answers before interpreting the resulting percentage.

Predict the effect of m and k

Under the approximation of independent uniform hashes, false-positive probability after n insertions is (one minus exp of minus kn/m) raised to k. With n one thousand, m eight thousand and k three, it is about3.06percent. Halving m gives about14.69percent; keeping eight thousand bits and using six hashes gives about2.16percent. A finite run is not required to equal those values.

More hashes are not always better: they set more bits, can saturate the filter and increase query computation. The approximate optimum near (m/n) times ln2 must be rounded and weighed against actual costs. We compare three specified settings rather than claiming a universal optimum. Record the prediction assumptions and chosen conditions before observing samples so the explanation does not retroactively fit a favorable result.

nmkApproximate false-positive rate
10004000314.69%
1000800033.06%
1000800062.16%

Use deterministic hashing and disjoint sets

The code hashes a four-byte hash-function index followed by UTF-8 key bytes with SHA-256 and reduces the resulting integer modulo m. This avoids Python's process-randomized built-in hash. Indexed SHA-256 inputs provide reproducible positions, not a proof that the resulting functions form a perfectly independent mathematical family. Cryptographic hashing does not eliminate Bloom-filter false positives.

For seeds zero through four, choose six thousand distinct integers. Insert the first thousand and query the remaining five thousand, asserting disjointness explicitly. This prevents an actually inserted query from being counted as a false positive. Reuse the corresponding seeded datasets across the three parameter settings so input changes do not confound the comparison. Only Python's standard library is required.

Check inserted keys as a separate invariant

After insertion, assert that every inserted key tests positive. In this insertion-only bit-setting structure, a negative answer for an inserted key indicates an implementation or input-identity problem. That invariant is separate from observing false positives among absent keys. No false negatives does not imply no false positives, and a positive response is not proof of actual membership.

Print all five seeded observations for each m/k setting together with the approximation, rather than only a rounded average. A formal statistical test would need a specified purpose and assumptions about trials. The deterministic assertions here check disjoint input sets and retained inserted keys; they do not demand exact agreement with a probability approximation. Avoid inventing an arbitrary fixed acceptance threshold simply because the output contains percentages.

python
import hashlib,math,random
class Bloom:
    def __init__(self,m,k):self.m=m;self.k=k;self.data=bytearray((m+7)//8)
    def locations(self,key):
        for i in range(self.k):yield int.from_bytes(hashlib.sha256(i.to_bytes(4,'big')+key.encode()).digest(),'big')%self.m
    def add(self,key):
        for bit in self.locations(key):self.data[bit//8]|=1<<(bit%8)
    def contains(self,key):return all(self.data[b//8]>>(b%8)&1 for b in self.locations(key))
for m,k in [(4000,3),(8000,3),(8000,6)]:
    observations=[]
    for seed in range(5):
        rng=random.Random(seed);values=rng.sample(range(1000000),6000);inserted=['x'+str(x) for x in values[:1000]];queries=['x'+str(x) for x in values[1000:]]
        assert not set(inserted)&set(queries)
        f=Bloom(m,k)
        for key in inserted:f.add(key)
        assert all(f.contains(key) for key in inserted)
        positives=sum(f.contains(key) for key in queries);observations.append(positives/len(queries))
    approximation=(1-math.exp(-k*1000/m))**k
    print('n=1000 queries=5000 seeds=0..4 m=',m,'k=',k,'observed=',observations,'approximation=',approximation)
print('no false negatives for inserted keys; approximation is not an exact finite-sample guarantee')

Do not add deletion by clearing shared bits

Clearing every bit used by a deleted key can erase positions shared with another key. That other inserted key may then test negative. A basic Bloom bitmap therefore cannot acquire correct deletion support through that simple change. Counting variants and other probabilistic structures require additional state and update rules. Interpret this experiment only under its insertion-without-clearing contract.

Serialization must preserve m, k, encoding and hash-input construction along with the bits. An identical bitmap read using another position rule may reject keys that were inserted under the old rule. Changing hash count or format is not automatically compatible. Membership semantics depend jointly on stored bits and deterministic key-to-position mapping. A successful in-process run does not establish a versioned interchange format for future readers.

Connect false positives to downstream work

A rate near three percent suggests roughly150 extra exact lookups for five thousand absent queries. The service-wide impact also depends on how many queries are absent in the real workload. Compare filter CPU work with the downstream I/O or network cost. A lower false-positive percentage does not automatically imply lower end-to-end latency.

More bits increase storage and transfer size, while more hashes increase computation per query. A complete performance comparison would fix present/absent query proportions, include downstream work and verify final exact results. This experiment measures false-positive observations rather than that full latency tradeoff. When applying its result, identify which costs have been measured and which remain assumptions instead of ranking configurations solely by the smallest reported percentage.

Reuse matched datasets without claiming independence

For a given seed, all parameter settings use the same inserted and absent-query sets. Otherwise parameter and input changes would be confounded. Matched datasets do not make the three resulting measurements statistically independent.

Adding deletion or concurrent writes introduces new correctness requirements. A lost bit update can create false negatives through an implementation bug unrelated to the abstract insertion-only Bloom-filter property. This experiment deliberately stays single-threaded and insertion-only so the comparison focuses on approximation and false-positive observations. Preserve that scope when interpreting or extending its evidence.

Exercise: calculate the defined conditional rate

Suppose160 of five thousand absent queries test positive and all one thousand inserted keys also test positive. The false-positive rate is160/5000, or3.2percent. Dividing by all positive answers or all six thousand queries measures another quantity. The inserted-key results check false negatives and do not belong in this denominator.

Now double inserted count while keeping m and k fixed. The approximation predicts increased occupancy and a higher false-positive rate. Regenerate datasets while preserving disjoint inserted and absent queries. One sample moving unexpectedly does not refute the probability model; inspect every seed, sample size and hashing assumptions. The experiment creates no external resources. Retain source and complete observations so another reader can reproduce the comparison and understand exactly which rate was measured.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 5

Prepare for AI systems · STEP 2

Choose a learning path