Bloom Filter
1. Giới thiệu
Bloom Filter là một cấu trúc dữ liệu xác suất được sử dụng để kiểm tra xem một phần tử có thuộc tập hợp hay không. Nó có thể cho kết quả dương tính giả nhưng không bao giờ cho kết quả âm tính giả.
2. Đặc điểm chính
- Tiết kiệm bộ nhớ
- Thời gian tìm kiếm O(k), với k là số hàm băm
- Không thể xóa phần tử
- Có thể có false positive nhưng không có false negative
3. Cách hoạt động
- Khởi tạo một mảng bit có kích thước m, tất cả các bit đều là 0
- Chọn k hàm băm khác nhau
- Khi thêm một phần tử:
- Áp dụng k hàm băm cho phần tử
- Set các bit tại vị trí tương ứng thành 1
- Khi kiểm tra một phần tử:
- Áp dụng k hàm băm cho phần tử
- Kiểm tra các bit tại vị trí tương ứng
- Nếu tất cả đều là 1 -> phần tử có thể có trong tập
- Nếu có ít nhất 1 bit là 0 -> phần tử chắc chắn không có trong tập
4. Ví dụ Implementation
public class BloomFilter<T> {
private BitSet bitSet;
private int size;
private int numHashFunctions;
public BloomFilter(int size, int numHashFunctions) {
this.size = size;
this.numHashFunctions = numHashFunctions;
this.bitSet = new BitSet(size);
}
public void add(T item) {
for (int i = 0; i < numHashFunctions; i++) {
bitSet.set(getHash(item, i));
}
}
public boolean mightContain(T item) {
for (int i = 0; i < numHashFunctions; i++) {
if (!bitSet.get(getHash(item, i))) {
return false;
}
}
return true;
}
private int getHash(T item, int seed) {
int h = item.hashCode();
h = h ^ (h >>> 16);
h = h * 0x3fff + seed;
return Math.abs(h % size);
}
}
5. Ứng dụng thực tế
- Kiểm tra mật khẩu yếu trong database lớn
- Cache filtering trong hệ thống phân tán
- Kiểm tra URL độc hại trong trình duyệt web
- Lọc spam email
- Đề xuất nội dung (content recommendation)
6. Bài tập thực hành
- Implement Bloom Filter với các hàm băm tùy chỉnh
- Xây dựng ứng dụng kiểm tra URL độc hại
- Tối ưu kích thước Bloom Filter dựa trên tỉ lệ false positive mong muốn