Bloom filter là gì và nó tạo ra đánh đổi gì?

Question

Accepted Answer

**Bloom filter** là một cấu trúc **xác suất (probabilistic)** tiết kiệm không gian, trả lời tính thành viên của tập với một điểm khác biệt: nó có thể có **false positive** (dương tính giả) nhưng **không bao giờ có false negative** (âm tính giả). "Chắc chắn không hiện diện" là chắc chắn; "có thể hiện diện" cần một kiểm tra thật.

## Cách hoạt động

Một bit array gồm `m` bit và `k` hash function. Để **thêm** một phần tử, đặt `k` bit mà nó hash tới. Để **truy vấn**, kiểm tra `k` bit đó — nếu bất kỳ bit nào là 0, phần tử chắc chắn vắng mặt.

```text
bits: [0 0 0 0 0 0 0 0]
thêm "cat":  hash->bit 1,4,6  -> [0 1 0 0 1 0 1 0]
truy vấn "dog": hash tới 1,3,6 -> bit 3 là 0 -> CHẮC CHẮN vắng mặt
truy vấn "cat": cả 1,4,6 đều set -> "có thể hiện diện"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list các hàm hash
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = chắc chắn; True = có thể
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| Thao tác | Thời gian | Không gian |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |

Không có false negative; tỷ lệ false positive giảm khi `m` (và `k` được tinh chỉnh) tăng.

## Đánh đổi

- **Điểm mạnh:** dấu chân bộ nhớ nhỏ xíu so với lưu trữ đầy đủ các key; thao tác thời gian hằng số.
- **Điểm yếu:** false positive; **không thể xóa** (Bloom filter tiêu chuẩn); không thể liệt kê các thành viên.

## Tại sao điều này quan trọng

Bloom filter bỏ qua công việc tốn kém một cách rẻ tiền: database (ví dụ Cassandra, HBase) dùng chúng để tránh đọc đĩa cho các key **chắc chắn** không có trên đĩa.

Chúng thể hiện một đánh đổi hệ thống kinh điển — chấp nhận một tỷ lệ lỗi nhỏ, có giới hạn để đổi lấy một sự giảm khổng lồ về bộ nhớ và I/O.