مستوى المقال: محترف. يفترض أنك تعرف دوال الهاش، تحليل التعقيد Big-O، وأساسيات قراءة قواعد البيانات من القرص.
فلتر بلوم: تعرف إن العنصر "أكيد مش موجود" قبل ما تلمس قاعدة البيانات
لو خدمتك بتضرب قاعدة البيانات في كل مرة عشان تتأكد إن إيميل أو مفتاح مش موجود، إنت بتدفع تكلفة قرص وشبكة في أغلب الأحيان على إجابة "لا". فلتر بلوم بيرد على السؤال ده في خانة ذاكرة واحدة، من غير ما يفتح القرص أصلًا.
المشكلة باختصار
عندك 50 مليون اسم مستخدم. مع كل تسجيل جديد لازم تتأكد إن الاسم مش متسجّل قبل كده. لو خزّنت الأسماء كلها في set في الذاكرة، ده حوالي 1 جيجابايت (بمتوسط 20 بايت للاسم مع overhead البنية). ولو رحت للقرص في كل طلب، كل استعلام بياخد ملّي ثانية أو اتنين على الأقل. المشكلة الحقيقية: أغلب الأسماء الجديدة فعلًا مش موجودة، فإنت بتصرف أغلى مواردك على إجابة سلبية متكررة.
الفكرة ببساطة قبل التعريف العلمي
تخيّل حارس على باب نادي معاه دفتر فيه 10 خانات صغيرة فاضية، مش أسماء. أول ما عضو يدخل، الحارس بيحسب من اسمه 3 أرقام ثابتة (مثلًا 1 و4 و7) ويعلّم الخانات دي. بعدين ييجي حد يسأل: "فلان دخل؟" الحارس بيحسب نفس الـ 3 أرقام من الاسم؛ لو لقى أي خانة منهم فاضية، يبقى الشخص ده أكيد ما دخلش. لو الثلاثة كلهم متعلّمين، يقول "غالبًا دخل" ويروح يراجع كشف الحضور الحقيقي عشان يتأكد.
علميًا: فلتر بلوم بنية بيانات احتمالية اخترعها Burton H. Bloom سنة 1970. هو مصفوفة من m بت كلها أصفار في البداية، مع k دوال هاش مستقلة. عملية الإضافة add(x): احسب k مواضع من x وحوّل البتات في المواضع دي لـ 1. عملية الفحص contains(x): احسب نفس الـ k مواضع؛ لو كلها 1 رجّع "ربما موجود"، ولو أي واحدة 0 رجّع "أكيد غير موجود". الخاصية المفتاحية: مفيش false negative إطلاقًا (اللي دخل مستحيل يظهر إنه مش موجود)، لكن ممكن يحصل false positive.
إزاي بيشتغل بالظبط — كود شغّال
ده تنفيذ مختصر بالـ Python باستخدام bytearray و hashlib. ركّز إن التخزين بتات فعلية على مستوى البايت، مش set بيخزّن العناصر:
import hashlib, math
class BloomFilter:
def __init__(self, m_bits, k):
self.m = m_bits
self.k = k
self.bits = bytearray(m_bits // 8 + 1)
def _positions(self, item):
h = hashlib.sha256(item.encode()).digest()
h1 = int.from_bytes(h[:8], "big")
h2 = int.from_bytes(h[8:16], "big")
# double hashing: g_i = h1 + i*h2 (Kirsch-Mitzenmacher)
for i in range(self.k):
yield (h1 + i * h2) % self.m
def add(self, item):
for p in self._positions(item):
self.bits[p // 8] |= (1 << (p % 8))
def contains(self, item):
return all(self.bits[p // 8] & (1 << (p % 8))
for p in self._positions(item))
# 50 مليون عنصر, 10 بت لكل عنصر
n = 50_000_000
m = 10 * n # 500 مليون بت = ~62.5 ميجابايت
k = round((m / n) * math.log(2)) # ≈ 7
bf = BloomFilter(m, k)
bf.add("ahmed@haies.com")
print(bf.contains("ahmed@haies.com")) # True (مضمون)
print(bf.contains("random@nope.com")) # False (غالبًا)