Insertion sets selected bit positions
A basic Bloom filter starts with zero bits and selected hash mappings. Insertion sets the item’s chosen positions to one, retaining bits already set rather than storing a separate complete copy of every element.
A query checks the same positions. Any zero rules out insertion under the filter’s current rules. All ones establish only possible membership because different inserted items can collectively have set those positions.
The error is one-sided under its assumptions
In the insertion-only model, with unchanged mappings and intact storage, an inserted item’s bits do not revert to zero. Further insertions therefore do not create false negatives. An absent item can nevertheless have all its positions already set, producing a false positive.
Possible membership is not an exact-set answer. When accuracy is required, a positive report needs checking against the underlying records. Bit count, hash count, and expected population govern the space/error tradeoff, while continued insertion fills more positions.
Deletion and hashing have additional limits
Deleting an item cannot simply clear all its bits because other items may share them, breaking the no-false-negative condition. Deletion requires additional machinery, such as suitable counters, rather than unchanged basic bit operations.
Queries compute hashes and read selected bits, so their cost includes hash count and input processing. The filter also cannot enumerate a set whose full elements it never stored. It reduces expensive follow-up queries without encoding all original contents for unrestricted recovery.