Bloom filters: rule out membership under an intact contract

Start with m zero bits and k hash positions per key. Inserting a key sets every selected bit to one. A query finding any required bit zero can reject membership because a correctly inserted key would have set it. If all are one, other keys might have set those same bits, so the answer remains a candidate requiring the exact underlying lookup. The filter does not store row values, prove uniqueness, or enumerate matching records. A positive answer can also be a genuine member rather than an error.

The no-false-negative argument assumes the inserted key is queried with the same hashing and encoding rules, every required insertion is reflected, and no relevant bit has been lost or improperly cleared. A filter for yesterday's file cannot safely reject keys added to a different current file unless the design accounts for them. Concurrent construction and publication must preserve that version agreement. Corruption, incomplete writes, incompatible serialization, and stale metadata can violate the premise; a negative result is useful only within the system's actual integrity and lifecycle contract.

After n insertions, more selected bits are set, so absent queries are harder to reject. Increasing m relative to n lowers saturation, while changing k has a tradeoff: more queried positions initially improve rejection but also set more bits during insertion and cost additional hash work. The familiar continuous optimum is proportional to bits per key times ln two. An implementation chooses a nearby feasible integer and may generate positions using a specified practical hashing scheme. The simple formula is not an exact finite-filter guarantee for every such scheme.

Expected avoided work depends on the query mix. If nearly all queries are real members, the filter adds checking overhead while rejecting little. If most queries are absent and exact lookup is costly, even a modest filter can help. A one-percent false-positive probability among nonmembers is not a one-percent error rate among all queries or positive results. Account for cache misses to the bit array, hashing CPU, and whether multiple underlying files require multiple filter checks. Choose the parameter budget for the workload rather than treating the lowest modeled probability as automatically optimal.

Clearing the ordinary Bloom bits for a deleted key is unsafe because another live key may depend on those bits. A counting variant can support certain deletion protocols, but must prevent counter underflow, overflow, and deletion of unsupported keys. Rebuilding from an authoritative snapshot can remove obsolete influence if writes arriving during construction are handled and the new filter is published with the correct data version. An immutable storage file naturally supports a file-specific filter; moving or merging its records requires corresponding filter maintenance rather than reusing arbitrary old metadata.

The probability lab models hypothetical false-positive events, not the filter algorithm. Reset, set p=0.01 and n=20, predict a mean of 0.2 events, then Play or Step to inspect exact binomial bars. Separately Reset, set p=0.10 and n=20, predict mean two, then Play or Step. This assumes twenty independent trials with a common stipulated probability. It cannot set m or k, insert keys, or prove no false negatives. Relate the two event rates to avoided exact lookups, then state which filter-integrity premises the bars do not check.