bloom filter

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.