Can we prove the key is absent without reading it?

Most lookups in a hypothetical storage node ask for keys that do not exist. Every miss checks several sorted tables. The disks are busy proving absence.

You could keep every key in RAM, but the key set is too large. What if the cheap structure answered a weaker question?

Spend uncertainty where it is harmless

Use a bit array initially filled with zeros. Each inserted key sets $k$ hashed positions. A query that finds any of its positions zero is absent from the inserted set. If all are one, the answer is only “possibly present.” Read the authoritative data to find out.

Suppose A hashes to {3,7,11} and B to {7,11,14}. After both insertions, a never-inserted C hashing to {3,11,14} passes. Its bits were supplied by other keys.

“No false negatives” assumes every relevant insertion reached this filter, hashing is consistent, bits were not lost, and no unsupported deletion occurred. A stale filter can say absent for a new record. A concurrent non-atomic read/modify/write can lose a set bit. Use synchronized or atomic bit updates, or build an immutable filter and atomically publish it with its matching table.

Calculate the memory instead of guessing

For $n$ inserted keys, $m$ bits and $k$ approximately uniform hashes:

$$p \approx (1-e^{-kn/m})^k,\qquad k^*\approx (m/n)\ln 2$$

Choosing a target false-positive probability gives:

$$m\approx -\frac{n\ln p}{(\ln 2)^2}$$

For one million keys and $p=0.01$, this is about 9.59 million bits, or 1.20 MB before overhead, with roughly seven hash probes. These are approximations under a hashing model; integer rounding, filter layout, duplicates, and hash quality affect the actual result.

One practical coordinate scheme derives probes as (h1 + i*h2) mod m. The source's two-hash discussion explains the asymptotic false-positive result; arbitrary poor hashes are not rescued by the formula. A point query costs $O(k)$ probes. A range query needs a different summary.

The filter fills up

If you size for a million keys and insert ten million, most bits become one and the shortcut rarely rules anything out. Watch observed false positives and occupancy. A false positive still costs the full lookup, so tune against workload I/O, not memory alone.

Deleting on a mere probabilistic hit is unsafe even with a deletion-capable structure: the hit may represent another key. Counting filters need correct membership bookkeeping, not just counters.

For immutable SSTables, build the filter from exactly that table's keys and publish both together. Compaction creates a new table/filter pair. For a rotating dedup window, expiration means “we no longer remember,” not “this event never happened.” If a false positive causes you to drop a payment or a new user, the filter is at the wrong correctness boundary.

Mental model: a Bloom filter buys cheap negative evidence about a particular inserted set. A positive is a request to check, not proof.

Transfer: a revocation shortcut

---

Source trail: 03-bloom-filters-and-counting-filters. See the source map for consolidation and reference-retained material.