What is a Bloom Filter? How do you calculate the False Positive rate?

Difficulty: 5/10

probabilistic data structures, false positive analysis, hash functions

Bloom Filter

A Bloom Filter is a space-efficient probabilistic data structure for testing set membership. It uses a bit array and multiple hash functions. It can produce false positives, meaning it may report that an absent item exists, but a correctly implemented Bloom Filter never produces false negatives for inserted items.

javascript

1
False positive: possible.
2
False negative: not possible under standard insert/query semantics.
3
m controls memory usage.
4
k controls the number of hash functions.
5
Optimal k is approximately (m/n) ln(2).
6
Common uses include caches, databases, and distributed systems.

Scenario Questions

0-2 years experience

Follow-up Questions