1️⃣ What is a Bloom Filter?

A Bloom Filter is a probabilistic data structure that tells you:

• “Possibly in the set” ✅
• “Definitely not in the set” ❌

It never gives false negatives, but it can give false positives.

Use case: Quickly check if an element exists in a large dataset without storing the full data.

---

2️⃣ How It Works

1. Initialize a bit array of size m (all bits = 0).

2. Use k different hash functions.

3. To add an element:

   • Hash the element with all k hash functions.
   • Set the bits at the resulting indices to 1.

4. To check if an element exists:

   • Hash the element with the same k hash functions.

   • Check the bits at the resulting indices:

     • If any bit is 0 → element is definitely not in the set
     • If all bits are 1 → element is possibly in the set (could be a false positive)

---

3️⃣ Example

Bit array size m = 10, hash functions k = 2

• Add “apple” → hash to indices 2 & 5 → set bits 2 & 5 to 1
• Add “banana” → hash to indices 3 & 7 → set bits 3 & 7 to 1

Check “apple” → bits 2 & 5 = 1 → possibly in set ✅ Check “orange” → bits 1 & 6 = 0 → definitely not in set ❌

---

4️⃣ Key Properties

• Space-efficient: Stores membership info without storing full data.
• Probabilistic: May return false positives, but no false negatives.
• Fast: O(k) for insert and lookup (k = number of hash functions).
• Cannot delete (standard Bloom Filter) → need Counting Bloom Filter to support deletes.

---

5️⃣ Use Cases in System Design

1. Databases / Caches

   • Avoid unnecessary disk or cache lookups:

     • Example: Before querying a database for a key, check Bloom Filter first.

2. Distributed Systems

   • Reduce network calls: e.g., Cassandra, HBase use Bloom Filters to check if a row exists before reading.

3. Web Crawlers / Spam Detection

   • Track which URLs/emails have been seen before.

4. Blockchain / Bitcoin

   • Light clients use Bloom Filters to filter transactions efficiently.

---

6️⃣ Pros & Cons

Pros	Cons
Very memory-efficient	False positives possible
Fast insert & lookup	Cannot retrieve actual elements
Simple to implement	Standard version cannot delete
Scales well for large datasets	False positive rate increases with more elements

---

7️⃣ Quick Analogy

Think of a Bloom Filter as a “magic checklist”:

• You check off boxes for items you see.
• If a box for an item is empty → you never saw it
• If all boxes are checked → maybe you saw it (could be coincidental)

---