Bloom filter ni nini na kompromiso gani inayofanya?

Question

Accepted Answer

**Bloom filter** ni muundo wa **uwezekano** unaobahatisha nafasi ambao unajibisha swali la uanachama wa seti kwa mtego mmoja: inaweza kuwa na **positiba za kauni** lakini **asilia kamwe ya kauni**. "Hakuna katika nnasaka" ni uhakika; "labda ipo" inahitaji ukaguzi halisi.

## Jinsi inavyofanya kazi

Kigezo cha biti kwa `m` biti na `k` kazi za hash. Ili **kuongeza** kitu, weka biti za `k` ambazo inakosa kwa njia ya hash. Ili **kuhoji**, angalia biti hizo za `k` — ikiwa kuna 0, kitu chake ni hakika haipo.

```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"
```

## Kod

```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)
```

| Operesheni | Wakati | Nafasi |
|---|---|---|
| add | O(k) | O(m) biti |
| query | O(k) | — |

Hakuna kauni za kauni; kiwango cha positiba za kauni kinapungua kadri `m` (na `k` iliyoboreswa) inavyokua.

## Kompromiso

- **Nguvu:** alama ndogo ya kumbukumbu ikilinganisha na kuhifadhi funguo kamili; operesheni za muda wa mara kwa mara.
- **Udhaifu:** positiba za kauni; **haiwezi kufuta** (Bloom filter ya kawaida); haiwezi kuorodhesha wanachama.

## Kwa nini inakubaliana

Bloom filters huachana kwa njia rahisi kwa kazi ghali: hifadhidata (mfano Cassandra, HBase) hutumia ili kuepuka kusoma diski kwa funguo ambazo **hakika** hazipo kwenye diski.

Zinawakilisha kompromiso ya kawaida ya mifumo — kukubali kiwango kidogo, kilichofungwa cha kosa ili mabadiliko makubwa ya kumbukumbu na I/O.