Algorithms and data structures · Intermediate

Bloom filters: compactly ruling out membership

Use a bit array to avoid unnecessary lookups while understanding false positives and deletion limits.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Record several bits for each inserted key
  2. Construct a false positive explicitly
  3. Balance space and the number of hashes
  4. Place the filter before an authoritative lookup
  5. Ask Logeia about this articleCheck your understanding

Record several bits for each inserted key

A standard Bloom filter begins with an all-zero bit array and uses several hash-derived positions for each key. Inserting a key sets those positions to one without storing the complete key or its associated value. A membership query checks the same positions. If any checked bit is zero, the key was not inserted. If every checked bit is one, the key might have been inserted, but bits set by other keys can produce the same pattern. The positive answer is therefore a candidate, not a proof of membership.

Construct a false positive explicitly

Consider eight bits. Key A sets positions one and four, and key B sets positions three and six. An absent key C that maps to positions one and six finds both bits set and is reported as possibly present: this is a false positive. An absent key D mapping to positions two and four is definitely absent when position two remains zero. Under correct insertion-only operation, unchanged bits, and consistent hashing rules, an inserted key cannot encounter an unset required bit. Those conditions are part of the usual no-false-negative guarantee.

Balance space and the number of hashes

If too many keys are inserted for the available bit count, many positions become one and the filter loses its ability to reject absent keys. Increasing the number of hashes means checking more positions, but it also sets more positions per insertion, so more hashes do not improve accuracy without limit. Approximate false-positive formulas depend on the number of bits, inserted keys, and hashes, together with assumptions about hashing. Capacity planning should account for expected growth and the cost of false-positive follow-up requests rather than assuming one fixed error rate for every load.

Place the filter before an authoritative lookup

A storage service can consult the filter first and skip an expensive lookup for keys reported definitely absent. It must perform an authoritative check for keys reported possibly present. A filter alone is unsuitable as the final decision in a permission check or any other operation that cannot tolerate a false positive. Standard bit arrays also cannot safely delete a key by clearing its bits, because other keys may share them. Designs such as counting filters address different deletion requirements. Always name the variant and its update rules before claiming its guarantees.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path