Contoh dan Dasar Bloom Filter

Bloom filter adalah struktur data probabilistik yang cepat dan hemat memori untuk memeriksa keanggotaan elemen.

Bloom filter dapat memastikan elemen 'definitif tidak ada' atau 'mungkin ada', tetapi berpotensi menghasilkan false positive.

Struktur dasar bloom filter berupa bit vector yang diatur dengan beberapa fungsi hash independen dan cepat.

Penambahan elemen dilakukan dengan meng-hash string beberapa kali lalu mengatur bit pada indeks hash menjadi 1.

Tingkat false positive dapat dikontrol dengan memilih jumlah bit (m) dan jumlah hash (k) berdasarkan perkiraan jumlah elemen (n).

Operasi penambahan dan pengecekan keanggotaan memiliki kompleksitas waktu O(k) karena penggunaan k fungsi hash.