What is a Bloom Filter? When is it used? (Cache penetration, Spell check)

Difficulty: 6/10

probabilistic data structures, cache penetration, spell checking

Bloom Filter

A Bloom Filter is a probabilistic, space-efficient data structure used to test whether an element is possibly present in a set. It can produce false positives, meaning it may say an element exists when it does not, but a properly configured standard Bloom Filter does not produce false negatives for inserted items.

javascript

1
Very memory efficient compared with storing all keys directly.
2
False positive: possible.
3
False negative: not expected for correctly inserted entries in a standard Bloom Filter.
4
Cannot normally remove individual entries safely without a counting variant.
5
Useful as a cache-penetration guard before querying an expensive database.
6
Useful for spell checking, URL filtering, deduplication, and membership prechecks.
7

Scenario Questions

0-2 years experience

Follow-up Questions