Bộ lọc Bloom đượ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 tập hợp một cách nhanh chóng và hiệu quả về bộ nhớ.
Một cấu trúc dữ liệu cụ thể được đặt tên là cấu trúc dữ liệu xác suất được thực hiện dưới dạng bộ lọc nở. Cấu trúc dữ liệu này giúp chúng tôi xác định rằng một phần tử có hoặc không có trong một tập hợp.
Bit Vector được triển khai dưới dạng cấu trúc dữ liệu cơ sở. Đây là một phần nhỏ mà chúng tôi sẽ sử dụng để 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ố bên dưới chỉ mục hoặc vị trí của nó. Để thêm một phần tử vào bộ lọc Bloom, chúng ta chỉ cần băm nó một vài lần và đặt các bit trong vectơ bit tại vị trí hoặc chỉ mục của các hàm băm đó thành 1.
Việc triển khai công phu Bộ lọc Bloom được thảo luận ở phần sau
Bộ lọc Bloom hỗ trợ hai hành động, lúc đầu là thêm đối tượng và theo dõi một đối tượng và tiếp theo xác minh xem một đối tượng đã được nhìn thấy trước đó hay chưa.
Thêm các đối tượng vào bộ lọc Bloom
- Chúng tôi tính toán các giá trị băm cho đối tượng để thêm vào;
- Chúng tôi triển khai các giá trị băm này để đặt các bit nhất định ở trạng thái bộ lọc Bloom (giá trị băm là vị trí của bit cần đặt).
Xác minh xem bộ lọc Bloom có chứa một đối tượng hay không -
- Chúng tôi tính toán các giá trị băm cho đối tượng để thêm vào;
- Tiếp theo, chúng tôi xác minh xem các bit được lập chỉ mục bởi các giá trị băm này có được đặt ở trạng thái bộ lọc Bloom hay không.
Chúng ta phải lưu ý rằng giá trị băm cho một đối tượng không được nối trực tiếp vào trạng thái bộ lọc nở; mỗi hàm băm chỉ đơn giản xác định bit nào cần đặt hoặc để xác minh. Ví dụ:nếu chỉ một hàm băm được sử dụng, thì chỉ một bit được xác minh hoặc kiểm tra.