ما هو Bloom filter وما هو المقابل الذي يفرضه؟

Question

Accepted Answer

**Bloom filter** هي بنية بيانات **احتمالية** موفرة للمساحة تجيب على استعلامات عضوية المجموعة بقلب واحد: يمكن أن تحتوي على **إيجابيات خاطئة** لكنها **لا تحتوي أبداً على سلبيات خاطئة**. "بالتأكيد غير موجود" مؤكد؛ "ربما موجود" يحتاج إلى فحص حقيقي.

## كيفية عملها

mصفيف بتات بـ `m` بتات و `k` دوال hash. لـ **إضافة** عنصر، اضبط البتات `k` التي يتم hash إليها. لـ **الاستعلام**، تحقق من تلك البتات `k` — إذا كانت أي منها 0، فالعنصر بالتأكيد غير موجود.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## الكود

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| العملية | الوقت | المساحة |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

لا توجد سلبيات خاطئة؛ معدل الإيجابيات الخاطئة ينخفض مع نمو `m` (و `k` المضبوط).

## المقابلات

- **نقاط القوة:** بصمة ذاكرة صغيرة جداً مقابل تخزين المفاتيح الكاملة؛ عمليات بوقت ثابت.
- **نقاط الضعف:** إيجابيات خاطئة؛ **لا يمكن حذف** (Bloom filter قياسي)؛ لا يمكن إدراج الأعضاء.

## لماذا يهم

تتجنب Bloom filters بتكلفة منخفضة العمل المكلف: قواعد البيانات (على سبيل المثال Cassandra و HBase) تستخدمها لتجنب قراءات القرص للمفاتيح التي **بالتأكيد** ليست على القرص.

تجسد المقابلات الكلاسيكية للأنظمة — قبول معدل خطأ صغير ومحدود مقابل تقليل هائل في الذاكرة والإدخال/الإخراج.