Bloom Filtreleri Örneği

Bloom filtresi, bir öğenin kümede kesinlikle bulunmadığını veya muhtemelen bulunabileceğini hızlı ve bellek açısından verimli bir şekilde söyleyen olasılıksal bir veri yapısıdır.

Ekleme ve sorgulama işlemi, öğeyi birkaç bağımsız hash fonksiyonundan geçirip bit vektöründeki ilgili bitleri 1 yapmak veya kontrol etmekle gerçekleştirilir.

Bloom filtresi yanlış pozitiflere izin verir ancak yanlış negatif üretmez.

Yanlış pozitif oranı yaklaşık olarak (1 - e^{-kn/m})^k formülüyle hesaplanır ve m (bit sayısı) ile k (hash fonksiyonu sayısı) değerleriyle ayarlanabilir.

İdeal hash fonksiyonları bağımsız, eşit dağılımlı ve hızlı (örn. Murmur, xxHash, FNV) olmalıdır.

Ekleme ve sorgulama işlemlerinin her biri O(k) zaman karmaşıklığına sahiptir.

Bloom filtrelerinin boyutu ve hash sayısı hedef eleman sayısına ve kabul edilebilir hata oranına göre belirlenmelidir.