لو عندك قايمة بمليون email مسجّل ومحتاج تشيك كل طلب جديد "هل موجود قبل كده"، hash table بتاخد 75MB ذاكرة. Bloom Filter بيعمل نفس الشغل في 1.2MB مع زمن بحث أقل من 10 ميكروثانية. في المقابل، فيه ثمن صريح هتدفعه، والمقال ده بيوريهولك بالظبط.
المشكلة باختصار
أي نظام بيعمل deduplication أو rate limiting أو URL blacklist بيحتاج يسأل نفس السؤال: هل شفت العنصر ده قبل كده؟ الحل الكلاسيكي hash set في الذاكرة. لمّا القايمة توصل ملايين العناصر، الذاكرة تحط سقف، والتخزين الدائم بيطلب I/O يبطّأ الاستجابة.
Bloom Filter بيحل الجزء ده بطريقة probabilistic: بيجاوب بسرعة وذاكرة قليلة جدًا، مقابل نسبة false positive محددة مسبقًا.
إيه هو الـ Bloom Filter بالظبط
Bloom Filter هو array من bits (أصفار وواحدات) + مجموعة hash functions. لمّا تضيف عنصر، بتمرره على كل hash function، كل واحدة بترجّع رقم index داخل الـ bit array، وبتقلب الـ bit اللي عند الـ index ده لواحد.
لمّا تسأل "هل العنصر ده موجود؟"، بتمرره على نفس الـ hash functions. لو كل الـ bits اللي بتشاور ليهم واحد، ترد "غالبًا موجود". لو أي bit منهم صفر، ترد "أكيد مش موجود".
الفرق الدقيق هنا: No قاطع، Yes احتمالي. ده اللي بيخلّي الهيكل مفيد ومخيف في نفس الوقت.
الـ 3 قواعد الأساسية
- مفيش false negatives: لو Bloom Filter قال "مش موجود"، تثق فيه 100%.
- في false positives: لو قال "موجود"، ممكن يكون غلطان. النسبة بتحددها انت في التصميم (1%، 0.1%، 0.01%).
- مفيش حذف: لمّا تضيف عنصر بتقلب bits مشتركة مع عناصر تانية. لو شيلت الـ bits، هتكسر البحث عنها.
الحل بكود Python شغّال
import hashlib
from bitarray import bitarray
class BloomFilter:
def __init__(self, size: int, hash_count: int):
self.size = size
self.hash_count = hash_count
self.bits = bitarray(size)
self.bits.setall(0)
def _hashes(self, item: str):
for i in range(self.hash_count):
digest = hashlib.sha256(f"{i}:{item}".encode()).hexdigest()
yield int(digest, 16) % self.size
def add(self, item: str) -> None:
for idx in self._hashes(item):
self.bits[idx] = 1
def contains(self, item: str) -> bool:
return all(self.bits[idx] for idx in self._hashes(item))
# مقاس بـ false positive rate 1% لمليون عنصر
bf = BloomFilter(size=9_585_059, hash_count=7)
bf.add("ahmed@example.com")
print(bf.contains("ahmed@example.com")) # True دايمًا
print(bf.contains("unknown@example.com")) # False في 99% من الحالات