Bộ lọc Bloom (Bloom filter) được định nghĩa là cấu trúc dữ liệu được thiết kế để xác định sự hiện diện của một phần tử trong một tập hợp (set) một cách nhanh chóng và tiết kiệm bộ nhớ.
Một cấu trúc dữ liệu cụ thể gọi là cấu trúc dữ liệu xác suất (probabilistic data structure) được cài đặt như bloom filter. Cấu trúc này giúp xác định một phần tử có mặt hoặc vắng mặt trong tập hợp.
Vector bit (Bit Vector) được dùng làm cấu trúc dữ liệu cơ sở. Đây là một ví dụ nhỏ để giải thích:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Mỗi ô trống trong bảng chỉ định một bit và số dưới đó là chỉ số (index) hoặc vị trí của nó. Để thêm phần tử vào Bloom filter, ta đơn giản băm nó vài lần và thiết lập các bit trong vector bit tại vị trí của các băm đó thành 1.
Cài đặt chi tiết của Bloom Filter được thảo luận sau
Bloom filter hỗ trợ hai hành động: đầu tiên, thêm đối tượng và theo dõi đối tượng; tiếp theo, kiểm tra xem đối tượng đã từng được thấy trước đó chưa.
Thêm đối tượng vào Bloom filter:
- Tính giá trị băm (hash values) cho đối tượng cần thêm;
- Dùng các giá trị băm này để thiết lập các bit xác định trong trạng thái Bloom filter (giá trị băm là vị trí bit cần thiết lập).
Kiểm tra xem Bloom filter có chứa đối tượng không:
- Tính giá trị băm cho đối tượng cần kiểm tra;
- Tiếp theo kiểm tra xem các bit được chỉ số bởi các giá trị băm này có được thiết lập trong trạng thái Bloom filter không.
Phải nhớ rằng giá trị băm cho đối tượng không được thêm trực tiếp vào trạng thái bloom filter; mỗi hàm băm chỉ xác định bit nào để thiết lập hoặc kiểm tra. Ví dụ: nếu chỉ dùng một hàm băm, chỉ một bit được kiểm tra.