Bloom Filter · Analysis

01 · Frame the problem

Understand the central challenge

Implement an insert-only Bloom filter for byte keys. Positive answers may be false positives; valid insertions must never become false negatives. Deletion is outside this model.

Membership answers are probabilistic in one direction: positives may be false, while inserted keys must not become negative under compatible state. Analyse bit count, hash count and update semantics before sizing storage.

02 · Find the design pressure

Start simple, then identify the gap

Begin with a fixed bit array and specified deterministic hashes. Clearing bits for deletion can erase evidence shared by other keys. Choose parameters for the expected population and verify positive answers against authoritative storage when correctness requires certainty.

Represent membership as a fixed bit array and deterministic key-to-position mapping. Insert sets all positions and lookup checks them; configuration compatibility and safe bit updates preserve the no-false-negative property. Validate positive bounded bit/hash counts and a supported deterministic byte hashing strategy. Allocate a zeroed bit array and immutable configuration. Compute exactly k bounded positions per key. Under a shared synchronization contract, insert ORs bits and lookup checks whether every required bit is set. Serialize the exact bit count, hash parameters, seed, encoding version and payload length. Reject malformed or incompatible input before allocation. Merge compatible filters using OR under synchronization. Track approximate occupancy for saturation warnings; rebuilding requires the original source keys, which the filter does not retain.

03 · Define success

Requirements to preserve

Validate bit count, hash count and supported hash version.
Use deterministic byte encoding and bit positions.
Only merge filters with identical configuration.
Define concurrency and serialization behavior.

04 · Identify the correctness boundary

Invariants, representation and mutation boundaries

A key maps deterministically to k bit positions in an m-bit array. With compatible hashing and atomic bit setting, lookup can have false positives but not false negatives for inserted keys. Estimate false-positive rate as approximately (1 - exp(-k*n/m))^k, then validate actual workload assumptions.

05 · Make it concrete

Reason through a worked example

A filter reports maybe-present for an unseen key; the caller confirms against authoritative storage. It reports definitely-absent only when a required bit is zero. Combining filters is valid only when their size and hash specification match. Clearing bits to delete one key can invalidate another key's membership.