Bloom Filter
Bloom filter memeriksa apakah sebuah item pernah dilihat dengan memori sangat kecil. Tiap item dipetakan oleh beberapa fungsi hash ke beberapa posisi bit yang lalu di-set menjadi 1. Saat mengecek, bila ada satu saja bit yang 0, item PASTI belum pernah ada; bila semua 1, item MUNGKIN ada (bisa keliru alias false positive). Ia menukar sedikit ketidakpastian demi kecepatan dan hemat memori yang luar biasa. Visualisasi menambah item lalu menunjukkan sebuah false positive.
Cara aplikasi cek cepat apakah username sudah dipakai, atau apakah sebuah URL masuk daftar berbahaya, tanpa menyimpan seluruh daftarnya.
Beberapa hash menyalakan bit; ada bit 0 = PASTI tidak ada, semua bit 1 = MUNGKIN ada (bisa false positive).
- ·Memahami struktur data probabilistik
- ·Menjelaskan mengapa false positive mungkin tapi false negative tidak
- ·Menilai tukar-untung memori melawan kepastian
- ·Sediakan array bit kosong dan beberapa fungsi hash.
- ·Menambah item: set bit menjadi 1 di semua posisi hasil hash-nya.
- ·Mengecek: lihat semua posisi hash item itu.
- ·Bila ada bit 0 -> pasti tidak ada; bila semua 1 -> mungkin ada (bisa keliru).
- ·Fungsi hash
- ·Array bit
- ·Operasi bit sederhana
- ·Cek cepat apakah username sudah dipakai.
- ·Filter URL berbahaya di peramban (Google Safe Browsing).
- ·Menghemat query database dan cache berukuran besar.
Complexity O(k) per operasi (k = jumlah fungsi hash)