Bloom फिल्टर म्हणजे काय आणि ते कोणती देणघेण करते?

Question

Accepted Answer

**Bloom फिल्टर** हे एक अंतराळ-कार्यक्षम **संभाव्य** संरचना आहे जे संच सदस्यता प्रश्नाचे उत्तर देते परंतु एक वळण असलेले: ते **खोट्या सकारात्मक** परिणाम असू शकते परंतु **कधीही खोट्या नकारात्मक नसते**. "निश्चितपणे उपस्थित नाही" हे निश्चित आहे; "संभवतः उपस्थित" साठी वास्तविक तपासणी आवश्यक आहे.

## कसे काम करते

`m` बिट्स आणि `k` हॅश फंक्शन्स चा बिट अ्रे. आयटम **जोडण्यासाठी**, त्याने हॅश केलेल्या `k` बिट्स सेट करा. **क्वेरी** करण्यासाठी, त्या `k` बिट्स तपासा — जर कोणताही 0 असेल तर आयटम निश्चितपणे उपस्थित नाही.

```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) बिट्स |
| query | O(k) | — |

कोणतेही खोटे नकारात्मक नाहीत; खोट्या सकारात्मक दर `m` (आणि समायोजित `k`) वाढीसह कमी होतात.

## देणघेण

- **शक्तिशाली बाजू:** पूर्ण की संचयित करण्याच्या तुलनेत अत्यंत लहान मेमरी फूटप्रिंट; स्थिर-वेळ ऑपरेशन्स.
- **कमजोर बाजू:** खोटे सकारात्मक परिणाम; **हटवू शकत नाही** (मानक Bloom फिल्टर); सदस्य सूची करू शकत नाही.

## हे महत्वाचे का आहे

Bloom फिल्टर्स स्वस्तीने महाग कार्य टाळतात: डेटाबेसेस (जसे Cassandra, HBase) ते व्यवहार करतात की ज्या की **निश्चितपणे** डिस्कवर नाहीत त्यांच्यासाठी डिस्क वाचन टाळण्यासाठी.

ते एक शास्त्रीय प्रणाली देणघेण मूर्त रूप देतात — मेमरी आणि I/O मध्ये विशाल कपात करण्याच्या बदल्यात एक लहान, मर्यादित त्रुटी दर स्वीकार करा.