Bloom filter คืออะไร และมันทำการประนีประนวมแบบไหน

Question

Accepted Answer

**Bloom filter** เป็นโครงสร้าง **ความน่าจะเป็น** ที่มีประสิทธิภาพด้านพื้นที่ซึ่งตอบคำถามเกี่ยวกับการเป็นสมาชิกของชุดด้วยกลจังหวา: สามารถมี **ผลบวกเท็จ** แต่ **ไม่มีผลลบเท็จเลย** "ไม่มีอย่างแน่นอน" นั้นแน่นอน; "อาจมี" ต้องการการตรวจสอบจริง

## มันทำงานอย่างไร

อาร์เรย์บิตขนาด `m` บิต และ `k` ฟังก์ชัน hash เพื่อ **เพิ่ม** รายการ ให้ตั้งค่าบิต `k` ที่มันแฮช ให้ **ค้นหา** ให้ตรวจสอบบิต `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) บิต |
| query | O(k) | — |

ไม่มีผลลบเท็จ อัตราผลบวกเท็จลดลงเมื่อ `m` (และ `k` ที่ปรับแต่ง) เพิ่มขึ้น

## การประนีประนวม

- **จุดแข็ง:** ลายเท้าหน่วยความจำน้อยมากเมื่อเทียบกับการจัดเก็บคีย์แบบเต็ม; ดำเนินการเวลาคงที่
- **จุดอ่อน:** ผลบวกเท็จ; **ไม่สามารถลบได้** (Bloom filter มาตรฐาน); ไม่สามารถแสดงรายชื่อสมาชิก

## ทำไมจึงสำคัญ

Bloom filter ข้ามงานที่มีค่าแพงได้ราคาถูก: ฐานข้อมูล (เช่น Cassandra, HBase) ใช้เพื่อหลีกเลี่ยงการอ่านจากดิสก์สำหรับคีย่ที่ **ไม่มีอยู่** บนดิสก์อย่างแน่นอน

พวกเขาเป็นตัวแทนของการประนีประนวมระบบแบบดั้งเดิม — ยอมรับอัตราข้อผิดพลาดเล็กน้อยและมีขอบเขต เพื่อแลกกับการลดหน่วยความจำและ I/O ที่มหาศาล