# Bloom Filters

A **Bloom Filter** is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.

## 1. The Core Concept

It tells you one of two things:
1.  The element is **definitely not** in the set.
2.  The element is **probably** in the set.

It never returns a false negative (if it says "no", it means "no"), but it can return a false positive (it might say "yes" when the answer is actually "no").

## 2. How it Works

A Bloom filter is essentially a bit array of $m$ bits, all initially set to 0.

### Adding an Element
To add an element:
1.  Feed it to $k$ different hash functions.
2.  Each function returns an index position.
3.  Set the bits at those positions to 1.

### Checking for an Element
To check if an element exists:
1.  Feed it to the same $k$ hash functions to get the index positions.
2.  Check the bits at those positions.
    *   If **any** bit is 0: The element is **definitely not** in the set.
    *   If **all** bits are 1: The element is **probably** in the set.

## 3. Why "Probably"? (False Positives)

It's possible that other elements just happened to set those specific bits to 1. This is a collision. As the filter fills up (more bits become 1), the probability of false positives increases.

## 4. Pros and Cons

*   **Pros:** Extremely space-efficient (much smaller than a Hash Table) and fast ($O(k)$).
*   **Cons:** Can't remove items (standard Bloom Filter), and allows false positives.

## 5. Use Cases

*   **Databases:** To quickly check if a row exists on disk before doing an expensive disk read (e.g., Cassandra, HBase).
*   **Web Browsers:** Checking if a URL is in a list of known malicious sites.
*   **CDNs:** To avoid caching "one-hit wonders" (only cache if seen twice).

[[programming/hash-tables]]
[[programming/algorithms]]
[[programming/caching-strategies]]