Bloom Filter — Bộ lọc xác suất

Bảng 64 bit cố định, 3 hàm hash. Add một key bật 3 bit. Check một key nhìn vào đúng 3 bit đó — nếu cả 3 đều bật → "có thể có"; có bit nào tắt → "chắc chắn không có". Đây là demo nhỏ để thấy cơ chế trước khi vào vấn đề kích thước ở phần 2.

Bảng 64 bit ở phần 1 saturate rất nhanh (n=20 đã có FP ~23%). Phần này cho biết n dự kiến và FP target → tự động tính m, k theo công thức: m = -n·ln(p) / (ln 2)², k = (m/n)·ln 2. Sau đó add key và đo FP đo thực để xác nhận giữ trong tầm kiểm soát.

Linked list nhiều tầng: L0 chứa tất cả phần tử đã sắp xếp; tầng trên chỉ giữ một số node, mỗi tầng bỏ qua một nửa (xác suất). Search đi từ tầng cao xuống, mỗi tầng nhảy phải tối đa khi còn ≤ target, rồi xuống tầng dưới. Trung bình O(log n) — chính là cách Redis ZSET tìm trong sorted set.