Bloom filtreleri ve olasılıksal veri yapıları

Kısaca: Bloom filtresi, bir öğenin bir kümede olabileceğini yer tasarruflu biçimde denetler. Ya “kesinlikle yok” ya da “muhtemelen var” yanıtını verir, asla yanlışlıkla “yok” demez.

Biraz daha ayrıntılı: Filtre, birkaç özet işlevli bir bit dizisidir. Eklerken k bit ayarlanır; ararken k bitin hepsi ayarlı olmalıdır. Yanlış pozitifler mümkündür, yanlış negatifler değildir. Silme mümkün değildir (sayaçlı çeşitler hariç).