Ba'zi katta platformalarda username tanlayotganingizda aslida mavjud bo'lmagan username kiritsangiz ham "Username already exists" deb chiqishi mumkin. Ko'p hollarda bunga sabab platforma usernameni tekshirish uchun bloom filter ishlatgani va false positive holat uchun ikkinchi darajali qidiruv ishlatilmagani sabab bo'ladi. Natijada qidiruv tezligi oshsa-da, ba'zida bir username boshqasini "to'sib" qo'yadi.

Bloom filter nima?

Agar O(1) vaqtda kiritilgan ma'lumot sizdagi ma'lumotlar to'plami ichida bor yoki yo'qligini tekshirish so'ralsa qanday yechim qilasiz? Menimcha, Joma akaning eng kuchli quroli – hashmap ishlatasiz. Lekin sizdagi ma'lumot hajmi juda kattalashib ketsa hashtable anchagina joy talab qiladi.

Bloom filter ham hash tablega o'xshash data structure, faqat ancha kam joy oladi. Buning uchun u bitta hash function o'rniga bir nechta hash function kombinatsiyasini ishlatadi. Lekin buning natijasida bloom filter probabilistic data structurega aylanadi. Ya'ni u "bor" yoki "yo'q" emas, "yo'q" yoki "bor bo'lishi mumkin" degan javoblar qaytaradi. Bor bo'lishi mumkin degani bor degani emas.

Masalan A qiymatni bloom filterga (hash functionlarga) kiritganda 1 va 2 qiymatlari qaytdi va bit arrayda shu qiymatlar "band" deb belgilandi. B qiymat esa 2 va 3 natija qaytardi. Endi 3 ham band qilindi. Keyin C ma'lumot hash functionlarga kiritilganda 1 va 3 natijalar qaytdi. Aslida oldin bunday ma'lumot kiritilmagan bo'lsa ham 1 ham 3 ham "band" bo'lgani uchun bloom filter bu ma'lumot oldindan bor degan natijani qaytaradi. Xuddi mana shu holat false positive deb hisoblanadi.

Bloom filterning eng katta kamchiliklaridan biri esa unga kiritilgan ma'lumotni o'chirib bo'lmasligida. Sababi, bit arraydagi 1 ta bitni bir nechta kiritilgan bir nechta qiymatlar har xil boshqa kombinatsiyalarda belgilagan bo'lishi mumkin. Masalan, A (1, 2) bitlarni, B (2, 3) bitlarni belgilagan. Ikkalasi ham bit 2 ni belgilagan. Agar A (1, 2) ni o'chirsa B (2, 3) ham bit 2 o'chgani sabab invalid bo'lib qoladi. Shuning uchun bloom filterga kiritilgan ma'lumotni qaytib o'chirib bo'lmaydi.
(G'oya: Browsing history uchun ishlatish kerak edi buni🙂)

@boboshersnotes