Apa iku Bloom filter lan apa trade-off sing ditindakake?

Question

Accepted Answer

**Bloom filter** minangka struktur **probabilistik** sing efisien ruang sing njawab keanggotaan himpunan kanthi siji puntir: bisa duwe **positif palsu** nanging **ngandhani ora duwe negatif palsu**. "Pasti ora ana" iku pasti; "bisa uga ana" butuh checking nyata.

## Cara kerja

Array bit saka `m` bit lan `k` fungsi hash. Kanggo **nambah** item, setel `k` bit sing di-hash. Kanggo **query**, periksa sing `k` bit — yen ana sing 0, item pasti ora ana.

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

| Operasi | Wektu | Spasi |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |

Tanpa negatif palsu; tingkat positif palsu mudhun nalika `m` (lan `k` sing diatur) abot.

## Trade-off

- **Kekuwatan:** tapak ingatan cilik banget lawan nyimpen tombol lengkap; operasi wektu konstan.
- **Kalemahan:** positif palsu; **ora bisa dibusak** (Bloom filter standar); ora bisa listem anggota.

## Mengapa penting

Bloom filter murah supaya isin laku larang: database (cth Cassandra, HBase) ngunakake kanggo ngilangi wacan disk kanggo kunci sing **mesthi** ora ana ing disk.

Sawijining trade-off sistem klasik — nanggap tingkat kesalahan cilik sing terbatas dadi tukar panganan pisan ing memori lan I/O.