Bloom Filter trong PHP

1. Mở đầu

Bạn có khi nào tự hỏi: “Làm sao để kiểm tra nhanh một phần tử có trong danh sách hay không, mà không cần lưu hết dữ liệu?” Ví dụ như kiểm tra xem một email đã từng xuất hiện trong hệ thống hay chưa, nhưng bạn lại không muốn lưu hàng triệu email để kiểm tra từng cái. Lúc này, Bloom Filter là vị cứu tinh — nhẹ nhàng, thông minh, và rút gọn được rất nhiều bộ nhớ mà vẫn đủ nhanh để làm việc.

---

2. Bloom Filter là gì?

Bloom Filter là một cấu trúc dữ liệu xác suất (probabilistic), nghĩa là nó xin “mượn chút may mắn” để tiết kiệm bộ nhớ và thời gian. Nói đơn giản:

• Không bao giờ bỏ sót phần tử có thật (không có false negative).

• Có thể báo nhầm rằng phần tử có trong tập, mặc dù thực ra không (có false positive).

Ví dụ thực tế

• Ví dụ 1: Bạn có một bit array (mảng chứa 0 và 1). Khi thêm “sinhvien1”, hệ thống đánh dấu một vài vị trí thành 1. Nếu sau này hỏi “sinhvien2”, mấy vị trí đó đều là 1 thì Bloom Filter sẽ trả lời “có thể có trong tập”.

• Ví dụ 2: Trong cuộc sống, Bloom Filter giống như một chiếc “nhớ mờ”: bạn chắc chắn không từng đến siêu thị A, nhưng nếu nhớ “có thể” từng đến siêu thị B.

---

3. Nguyên tắc hoạt động (từ cơ bản đến nâng cao)

a) Cơ bản: Bit array + các hàm băm (hash functions)

• Khởi tạo mảng bit kích thước size, toàn bộ gán bằng 0.

• Mỗi phần tử cần kiểm tra, bạn chạy qua n hash, sau đó đánh dấu vị trí hash % size thành 1.

b) Thêm phần tử (add)

Gửi item vào các hàm hash → lấy ra các vị trí → gán 1 cho các vị trí đó.

c) Kiểm tra (contains)

Chạy các hash → kiểm tra từng vị trí:

• Nếu có bất kỳ vị trí nào là 0, chắc chắn “không thuộc tập”.

• Nếu tất cả là 1, thì “có thể thuộc tập” (hoặc là false positive).

---

4. Một đoạn code PHP dễ hiểu

<?php
class BloomFilter {
    protected $bitArray, $size, $hashCount;

    public function __construct($size = 1000, $hashCount = 3) {
        $this->bitArray = array_fill(0, $size, 0); // Mảng ban đầu toàn 0
        $this->size = $size;
        $this->hashCount = $hashCount;
    }

    public function add($item) {
        $hashes = $this->getHashes($item);
        foreach ($hashes as $h) {
            $this->bitArray[$h % $this->size] = 1; // đánh dấu 1
        }
    }

    public function contains($item) {
        foreach ($this->getHashes($item) as $h) {
            if ($this->bitArray[$h % $this->size] === 0) {
                return false; // chắc chắn không có
            }
        }
        return true; // có thể có (hoặc nhầm)
    }

    protected function getHashes($item) {
        // Ở đây chỉ là minh họa: có thể dùng md5 + i để giả lập nhiều hash
        $hashes = [];
        for ($i = 0; $i < $this->hashCount; $i++) {
            $hashes[] = crc32($item . $i);
        }
        return $hashes;
    }
}

require_once 'BloomFilter.php';

use App\Services\BloomFilter;

// Create a Bloom Filter with 1000 bits and 3 hash functions
$bloomFilter = new BloomFilter(1000, 3);

// Add elements to the Bloom Filter
$bloomFilter->add("apple");
$bloomFilter->add("banana");
$bloomFilter->add("cherry");

// Check if elements are in the Bloom Filter
echo $bloomFilter->contains("apple") ? "Possibly in the set\n" : "Definitely not in the set\n";
echo $bloomFilter->contains("grape") ? "Possibly in the set\n" : "Definitely not in the set\n";

// output
Possibly in the set
Definitely not in the set

(Trong nguyên gốc có hàm getHashes, tương tự như ví dụ trên) (dailycomputerscience)

---

5. Minh họa rõ hơn bằng đồ họa ASCII

Bit array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Thêm "A" (hash → vị trí 2, 5):
[0, 0, 1, 0, 0, 1, 0, 0, 0, 0]

Thêm "B" (hash → vị trí 5, 7):
[0, 0, 1, 0, 0, 1, 0, 1, 0, 0]

Kiểm tra "C" (hash → 2, 3):
 vị trí 3 là 0 → chắc chắn C không có trong
Kiểm tra "D" (hash → 5, 7):
 cả hai đều là 1 → "có thể có" (hoặc nhầm)

---

6. So sánh thực tế (Bloom Filter vs Hashtable)

Ví dụ: Bloom Filter thường được áp dụng cho caching, kiểm tra nhanh trước khi truy vấn database nặng, hoặc CDN dùng để tránh lưu những đối tượng chỉ được truy cập một lần (GeeksforGeeks, Wikipedia).

---

7. Phần tương tác nhẹ

Thử thách nhỏ:

• Cho bạn cấu hình: size = 100, hashCount = 4. Bạn sẽ thử nghiệm với các phần tử như “sv1”, “sv2”... và đo xem làm sao để giảm false positive? Câu hỏi gợi mở: “Nên tăng size hay tăng số hash? Tại sao?”

---

8. Kết luận

Bloom Filter là một công cụ cực kỳ hữu ích khi bạn cần kiểm tra xem một phần tử có thuộc một tập hay không — với yêu cầu bộ nhớ cực thấp và tốc độ rất nhanh. Điểm quan trọng:

• Không có false negative → nếu Bloom báo “không”, thì chắc chắn là không.

• Có thể có false positive → nếu báo “có”, bạn vẫn cần kiểm tra lại.

Lời khuyên chân thành: Khi dùng Bloom Filter, hãy cân nhắc kỹ về kích thước mảng bit và số hàm băm để giữ tỷ lệ false positive ở mức chấp nhận được. Nếu cần xóa phần tử, bạn sẽ cần đến biến thể đặc biệt như Counting Bloom Filter.

---

9. Tài liệu tham khảo để đọc thêm

• Giống như Wikipedia: giải thích chi tiết Bloom Filter, công thức tính tỷ lệ false positive và ứng dụng thực tế (Wikipedia).

• So sánh Bloom với các cấu trúc khác như Cuckoo Filter hoặc ứng dụng trong hệ thống thật (ví dụ Cassandra) (Stack Overflow).

• Ví dụ trực quan dễ hiểu từ “Bloom Filters by Example” (llimllib.github.io).

---

Chúc các bạn học lập trình vui vẻ, khám phá thêm nhiều cấu trúc dữ liệu thú vị — và đừng quên thử chạy thử Bloom Filter để thấy sự “thần kỳ” của nó nhé