Çox böyük çoxluqda «element var mı?» sualına cavab vermək lazımdır, amma set çox yaddaş yeyir. Bloom filteri (Bloom filter) yaddaşa qənaət edən ehtimallı strukturdur: o yalnız iki cavab verir: «mütləq yoxdur» və ya «ola bilər». Yəni yalançı müsbət (false positive) mümkündür, yalançı mənfi isə heç vaxt olmur.

Bit massivi: `w6` yalançı müsbət verir, `cow` isə «mütləq yoxdur»
Bit massivi: w6 yalançı müsbət verir, cow isə «mütləq yoxdur»

İdeya

  • m bitlik massiv, əvvəlcə hamısı 0.
  • k müxtəlif heş funksiyası.
  • add(x): k heşin göstərdiyi k biti 1 edir.
  • x in filter: həmin k bitə baxır; hamısı 1-dirsə, «ola bilər», biri 0-dırsa, «mütləq yoxdur».

Bitlər yalnız 0 → 1 keçir, ona görə əlavə edilmiş element həmişə tapılır (yalançı mənfi yoxdur). Amma başqa elementlər həmin bitləri 1 etmiş ola bilər, ona görə heç vaxt əlavə olunmayan element də «ola bilər» cavabı alır.

Reallaşdırma

k heş funksiyası əvəzinə iki heşdən istifadə edirik: h1 + i * h2 (Kirsch və Mitzenmacher üsulu). Heşləri deterministik olsun deyə hashlib.sha256-dan alırıq (hash() isə proseslər arasında dəyişir, heş funksiyaları).

python
import hashlib
import math

class BloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bytearray((m + 7) // 8)