Bloom Filter Idea

## The structure in one paragraph A bloom filter is a fixed array of `m` bits, all zero to begin with, plus `k` independent hash functions that map an element to `k` positions in that array. To add an element you compute its `k` positions and set those bits to 1. To test an element you compute the same `k` positions and look at those bits. That is the entire structure. Notice what is missing: the elements themselves are never written down anywhere. The filter holds bits, not keys, which is exactly why it can represent an enormous set in a few megabytes — and exactly why its answers cannot both be exact. ## Why a negative is a fact Suppose an element `x` was inserted at some point. Insertion set all `k` of its bits to 1, and in the standard form of the structure nothing ever resets a bit to 0. So every one of `x`'s positions is still 1 today, and a query for `x` cannot possibly find a zero. Contrapositive: if a query finds even one zero bit, `x` was never inserted. That is a proof, not a probability. This is what people mean by *no false negatives*, and it is the guarantee the whole design rests on — the entire value of putting a filter in front of an expensive lookup is that the negatives let you skip work with no risk of skipping something real. ## Why a positive is only a hint Now suppose `y` was never inserted. Its `k` positions were chosen by the hash functions without regard to what else is in the filter, and every other element you inserted has been setting bits all over the array. If it happens that all `k` of `y`'s positions were already set — possibly each by a different, unrelated element — the query finds no zero and reports 'maybe present'. That is a *false positive*. It does not mean the structure malfunctioned; it is the advertised behaviour, and its rate is a design input you buy with bits. Two consequences follow immediately. First, the false-positive rate is not fixed for all time: it climbs as you insert more elements, because a fuller array makes accidental coverage likelier. A filter sized for ten million entries and loaded with forty million will answer positive far more often than its design promised, silently. Second, the rate is a property of the filter, not of the query: repeating the same query gives the same answer forever, so a false positive for a particular element is permanent until the filter is rebuilt. ## The failure mode this question is really about The common wrong answer is to treat a hit as a fact. Imagine a login service that keeps a filter of accounts flagged for a forced password reset and blocks any account that tests positive. Every flagged account is caught — the no-false-negative guarantee delivers that. But a small percentage of ordinary accounts, never flagged, will also test positive and be blocked, and no amount of retrying will clear it, because the filter's answer for that username never changes. The correct shape is: negative means proceed, positive means *go ask the authoritative source*. The filter's job is to remove the vast majority of pointless authoritative lookups, not to answer the question itself. If there is no cheap authoritative source to ask, a bloom filter is the wrong structure for that decision. ## What the structure cannot do at all Because it stores bits and not elements, a bloom filter cannot enumerate its contents, cannot return a stored value alongside a key, and cannot tell you how many distinct elements it holds. You cannot ask it 'what is in here?' — only 'was this particular thing possibly added?'. In the standard form you also cannot remove an element, because bits are shared and clearing one may destroy another element's evidence, breaking the very no-false-negative guarantee that makes the structure useful. ## Where the tradeoff pays An exact set must store the keys, so its memory grows with both the number of elements and their length; a bloom filter's cost is a fixed number of bits per element regardless of whether the element is a six-character token or a two-hundred-character address. That is the whole bargain: give up exactness in one direction, and in exchange the memory bill stops caring how big your elements are. Everything else about using the structure well follows from being precise about which direction you gave up.