مستوى المقال: محترف — بيفترض إنك متعامل قبل كده مع الهاش والداتابيز، وعايز توفّر ذاكرة واستعلامات في نظام كبير.
لو عندك مليون إيميل مسجّل وعايز تتأكد بسرعة إن إيميل جديد مش موجود، من غير ما تضرب الداتابيز في كل مرة، الـ Bloom Filter بيعمل ده بذاكرة حوالي 1.1 ميجا بدل عشرات الميجات. المقال ده هيوريك إزاي، بمثال، بكود شغّال، وبالأرقام.
الـ Bloom Filter: تتأكد إن العنصر مش موجود بذاكرة صغيرة جدًا
المشكلة باختصار
عندك خدمة تسجيل بمليون مستخدم. كل مرة حد يكتب إيميل، بتعمل استعلام على الداتابيز عشان تشوف هل الإيميل متكرر. الاستعلام ده بياخد وقت وبيحمّل السيرفر، خصوصًا مع كل ضغطة زرار في شاشة التسجيل. الافتراض هنا إن أغلب الإيميلات الجديدة مش موجودة أصلًا، فإنت بتدفع تكلفة استعلام كامل عشان جواب أغلبه "لأ".
الفكرة: البواب اللي بيقولك "أكيد لأ" بس مش بيأكدلك "أيوه"
تخيّل بواب عند باب حفلة، ومعاه ورقة فيها علامات صغيرة بدل أسماء المدعوين كاملة. لما حد ييجي، البواب بيبص على شوية خانات مرتبطة باسمه. لو واحدة منهم فاضية، يبقى الشخص ده أكيد مش مدعو، وبيرفضه فورًا من غير ما يفتح كشف الأسماء الطويل. لكن لو كل الخانات معلّمة، البواب بيقول "غالبًا مدعو" وبيروح يتأكد من الكشف الحقيقي. ساعات بيحصل تشابه في العلامات فيوقّف حد مش مدعو للمراجعة، بس عمره ما هيرفض مدعو حقيقي بالغلط.
علميًا: الـ Bloom Filter عبارة عن مصفوفة بتات (m bit) كلها أصفار في البداية، ومعاها عدد k من دوال الهاش. عند الإضافة، بنمرّر العنصر على الـ k دوال، وكل واحدة بتطلع رقم خانة، وبنخلّي البت بتاعها = 1. عند السؤال، بنحسب نفس الخانات: لو أي بت منهم = 0 يبقى العنصر مؤكد غير موجود؛ لو كلهم = 1 يبقى غالبًا موجود (مع احتمال إيجابية خاطئة). النتيجة السلبية دايمًا يقينية 100%، والإيجابية هي بس اللي فيها احتمال خطأ.
الحل بالكود: تنفيذ شغّال في 20 سطر
الكود ده بيشتغل على بايثون من غير أي مكتبة خارجية. بيستخدم تقنية الهاش المزدوج (Kirsch-Mitzenmacher) عشان يولّد k دوال من هاشين بس:
import math, hashlib
class BloomFilter:
def __init__(self, n, p):
# m: حجم المصفوفة بالبت، k: عدد دوال الهاش المثالي
self.m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))
self.k = max(1, round((self.m / n) * math.log(2)))
self.bits = bytearray((self.m + 7) // 8)
def _positions(self, item):
data = item.encode("utf-8")
h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
for i in range(self.k):
yield (h1 + i * h2) % self.m
def add(self, item):
for pos in self._positions(item):
self.bits[pos >> 3] |= 1 << (pos & 7)
def __contains__(self, item):
return all(self.bits[pos >> 3] & (1 << (pos & 7))
for pos in self._positions(item))
# تجربة: مليون مستخدم، ومعدل خطأ مستهدف 1%
bf = BloomFilter(n=1_000_000, p=0.01)
for i in range(1_000_000):
bf.add(f"user{i}@mail.com")
print(bf.m // 8 // 1024, "كيلوبايت") # ~1170
print("k =", bf.k) # 7
print("user7@mail.com" in bf) # True (موجود)
print("ghost@mail.com" in bf) # False (غير موجود بيقين)