Bloom filter کیا ہے اور یہ کون سا trade-off کرتا ہے؟

Question

Accepted Answer

ایک **Bloom filter** ایک جگہ کے لحاظ سے موثر **probabilistic** ڈھانچہ ہے جو set membership کے سوالات کا جواب دیتا ہے، لین ایک خاصیت کے ساتھ: یہ **false positives** رکھ سکتا ہے لیکن **کبھی false negatives نہیں** ہو سکتے۔ "یقیناً موجود نہیں" یقینی ہے؛ "شاید موجود ہے" کو حقیقی جانچ کی ضرورت ہے۔

## یہ کیسے کام کرتا ہے

`m` bits کا ایک bit array اور `k` hash functions۔ **شامل کرنے** کے لیے، `k` bits سیٹ کریں جو یہ hash کرتا ہے۔ **تلاش کرنے** کے لیے، ان `k` bits کو چیک کریں — اگر کوئی بھی 0 ہے، تو item یقیناً موجود نہیں ہے۔

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| آپریشن | وقت | جگہ |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

کوئی false negatives نہیں؛ false-positive rate `m` (اور tuned `k`) بڑھنے کے ساتھ کم ہوتی ہے۔

## Trade-offs

- **طاقتیں:** مکمل keys محفوظ کرنے کے مقابلے میں بہت چھوٹا میموری footprint؛ constant-time ops۔
- **کمزوریاں:** false positives؛ **delete نہیں کر سکتے** (ایک معیاری Bloom filter)؛ members کو درج نہیں کر سکتے۔

## یہ کیوں اہم ہے

Bloom filters سستے طریقے سے مہنگے کام کو چھوڑ دیتے ہیں: databases (مثال کے طور پر Cassandra، HBase) انہیں keys کے لیے disk reads سے بچنے کے لیے استعمال کرتے ہیں جو **یقیناً** disk پر نہیں ہیں۔

یہ ایک کلاسیکی systems trade-off کو ظاہر کرتے ہیں — میموری اور I/O میں بہت بڑی کمی کے بدلے میں ایک چھوٹی، محدود error rate قبول کریں۔