Apa itu Bloom filter dan trade-off apa yang dilakukannya?

Question

Accepted Answer

**Bloom filter** adalah struktur yang **probabilistik** dan hemat ruang yang menjawab keanggotaan himpunan dengan satu keunikan: dapat memiliki **positif semu** tetapi **tidak pernah negatif semu**. "Pasti tidak ada" adalah pasti; "mungkin ada" memerlukan pemeriksaan nyata.

## Cara Kerjanya

Sebuah larik bit dengan `m` bit dan `k` fungsi hash. Untuk **menambah** item, atur `k` bit yang di-hash-nya. Untuk **kueri**, periksa `k` bit tersebut — jika ada yang 0, item pasti tidak ada.

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

## Kode

```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 | Waktu | Ruang |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |

Tidak ada negatif semu; laju positif semu turun seiring `m` (dan `k` yang disesuaikan) bertambah.

## Trade-off

- **Kekuatan:** jejak memori yang sangat kecil dibandingkan menyimpan kunci lengkap; operasi waktu konstan.
- **Kelemahan:** positif semu; **tidak dapat dihapus** (Bloom filter standar); tidak dapat mencantumkan anggota.

## Mengapa ini penting

Bloom filter murah menghindari pekerjaan mahal: database (mis. Cassandra, HBase) menggunakannya untuk menghindari bacaan disk untuk kunci yang **pasti** tidak ada di disk.

Mereka mewujudkan trade-off sistem klasik — terima tingkat kesalahan kecil dan terbatas sebagai imbalan pengurangan besar dalam memori dan I/O.