Apakah Bloom filter dan apakah pertukaran yang dilakukannya?

Question

Accepted Answer

**Bloom filter** adalah struktur **probabilistik** yang efisien ruang yang menjawab keanggotaan himpunan dengan satu putaran: ia dapat memiliki **positif palsu** tetapi **tidak pernah negatif palsu**. "Pasti tidak ada" adalah pasti; "mungkin ada" memerlukan pemeriksaan nyata.

## Cara kerjanya

Array bit `m` bit dan `k` fungsi hash. Untuk **menambah** item, atur `k` bit yang di-hash. Untuk **kueri**, periksa `k` bit itu — 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"
```

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

Tidak ada negatif palsu; tingkat positif palsu menurun saat `m` (dan `k` yang disetel) bertambah.

## Pertukaran

- **Kekuatan:** jejak memori sangat kecil dibandingkan dengan menyimpan kunci penuh; operasi waktu konstan.
- **Kelemahan:** positif palsu; **tidak dapat menghapus** (Bloom filter standar); tidak dapat mencantumkan anggota.

## Mengapa hal ini penting

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

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