Bloom filter — yaddaşda çox az yer tutaraq böyük verilənlər dəstində bir elementin ola biləcəyini (və ya qətiyyən olmadığını) yoxlamağa imkan verən ehtimallı bir məlumat quruluşudur.
Əsas məqsədi — çox sürətli və yaddaş baxımından səmərəli axtarış aparmaqdır.
Bloom filter bir bit massivindən (məsələn, 1000 bitlik bir array) və bir neçə hash funksiyasından ibarətdir.
Məsələn:
10 bitlik array götürək - [ 0 0 0 0 0 0 0 0 0 0 ]
"cat" sözünün 3 fərlqli hash funksiyası ilə indexlərini tapaq
hash 1 - 2
hash 2 - 5
hash 3 - 8
sonra bit array-də həmin yerləri 1 edirik
[ 0 0 1 0 0 1 0 0 1 0 ] (index 0-dan başladığı üçün 0,1,2,3 sayılaraq dəyişilir)
yenidən axtarış üçün "cat" sözü sorğuda göndərildikdə 3 ayrı hash funksiyası ilə indexlərin yeri tapılır və bit arraydə uyğunluq düz gəlirsə "bəlkədə var" nəticəsini alırıq.
bloom filter - çox sürətli işləyir, yaddaşa qənaət edir, yanlış pozitivlər mümkündür(filter bəzən var deyir amma əslində yoxdur), yanlış neqativlər yoxdur(filter yoxdur deyirsə həqiqətən yoxdur).
istifadə olunan sahələr:
məsələ instagramda hesab açırsız username seçəndə , həmin username-in bazada mövcud olub olmamasını yoxlamaq üçün bloom filter istifadə olunur. bununla da milyardlarla username içində sizin seçdiyiniz username-in həqiqətən bazada olmadığı müəyyən edilir. [1]