Cấu trúc dữ liệu xác suất: đo thật

1 Bloom filter: trả lời 'có trong tập không' bằng 1/46 bộ nhớ, đổi lại chút báo nhầm Cần kiểm tra một phần tử có trong tập triệu phần tử không, mà không muốn tốn hàng chục MB? Bloom filter làm được bằng một mảng bit và vài hàm băm. Bài này tự cài Bloom và đo thật: thay 57MB set bằng 1.25MB (nhỏ hơn 46 lần), tỉ lệ báo nhầm thực tế 0.83% khớp gần như hoàn hảo công thức lý thuyết 0.82%, và không bao giờ báo sót. Cơ chế, công thức, và khi nào dùng. 22/09/2026 · 6 phút đọc

2 Chọn m và k tối ưu cho Bloom filter: hai công thức và một cái bẫy chết người Bloom filter chỉ tốt khi bạn cấp đúng số bit và đúng số hàm băm. Bài này đo thật: quét k từ 1 tới 15 cho thấy có một k tối ưu (7) cho tỉ lệ báo nhầm thấp nhất, nhiều hơn lại tệ hơn; công thức m = -n·ln(p)/(ln2)² cho đúng số bit để đạt 1%, 0.1%, 0.01%; và cái bẫy chết người — nhồi gấp đôi số phần tử dự kiến làm báo nhầm nhảy từ 0.8% lên 13.8%. 22/09/2026 · 6 phút đọc

3 Counting Bloom filter: thêm khả năng xóa cho Bloom, và ba cái giá phải trả Bloom filter thường không xóa được — tắt bit sẽ phá phần tử khác. Counting Bloom thay mỗi bit bằng một bộ đếm nhỏ để hỗ trợ xóa. Bài này tự cài và đo thật: xóa 'bob' làm nó biến mất mà 'alice' vẫn còn nguyên; nhưng cái giá là tốn 4 lần bộ nhớ, có rủi ro tràn bộ đếm, và xóa phần tử chưa từng thêm có thể sinh báo sót. Cơ chế và khi nào đáng dùng. 22/09/2026 · 7 phút đọc

4 HyperLogLog: đếm một triệu phần tử khác nhau bằng 16KB, sai số 1% Đếm 'bao nhiêu user duy nhất' hay 'bao nhiêu IP khác nhau' bằng set thì tốn RAM tỉ lệ số phần tử. HyperLogLog đếm số phần tử phân biệt bằng bộ nhớ CỐ ĐỊNH — bất kể 10 nghìn hay 1 triệu, vẫn 16KB. Bài này tự cài HLL và đo thật: đếm 1 triệu phần tử sai chỉ 1.06%, nhỏ hơn set 3479 lần. Trực giác về số 0 dẫn đầu, cơ chế register, và vì sao Redis dùng nó. 22/09/2026 · 7 phút đọc

5 HyperLogLog sâu: vì sao dùng trung bình điều hòa, và ba hiệu chỉnh cứu thuật toán Ý tưởng HyperLogLog đẹp, nhưng công thức thô không chạy được. Bài này đo thật ba hiệu chỉnh biến nó thành thuật toán thật: trung bình điều hòa thay trung bình thường (sai số 1% thay vì 150% vì giảm ảnh hưởng ngoại lai), hằng số alpha bù thiên lệch, và linear counting cho cardinality nhỏ (thiếu nó sai tới 2900% ở tập nhỏ). Đây chính là những gì HyperLogLog++ của Google hoàn thiện. 22/09/2026 · 6 phút đọc

6 Count-Min Sketch: đếm tần suất triệu phần tử trong luồng bằng 78KB Bloom trả lời 'có không', HyperLogLog trả lời 'bao nhiêu khác nhau'. Count-Min Sketch trả lời 'phần tử này xuất hiện bao nhiêu lần?' — bằng một ma trận nhỏ cố định thay vì một dict khổng lồ. Bài này tự cài CMS và đo thật: đếm phần tử phổ biến sai chỉ 0.07%, nhưng phần tử hiếm bị ước lượng vượt tới 2710%. Vì sao lấy MIN, và vì sao CMS hoàn hảo cho heavy hitters mà tệ với đuôi dài. 22/09/2026 · 7 phút đọc

7 Heavy hitters: tìm top-k phần tử nóng nhất trong luồng, không lưu hết Count-Min Sketch đếm được tần suất nhưng không tự biết phần tử nào nóng. Ghép nó với một min-heap nhỏ là ra bộ tìm top-k. Bài này tự cài và đo thật: trên luồng 300.000 sự kiện với 15.000 phần tử, CMS + min-heap tìm đúng 9/10 heavy hitter (recall 90%), chỉ lệch ở phần tử ranh giới có tần suất sát nhau. Cơ chế, vì sao top-k thường đúng, và ứng dụng DDoS/trending. 22/09/2026 · 7 phút đọc

8 MinHash: đo hai tập giống nhau bao nhiêu bằng 1KB thay vì cả tập Đo độ tương đồng hai tập lớn (Jaccard) cần giao chúng — tốn khi có triệu tập. MinHash rút mỗi tập thành một chữ ký vài trăm số, và một sự thật đẹp: xác suất min-hash của hai tập trùng nhau đúng bằng Jaccard similarity. Bài này tự cài và đo thật: MinHash ước lượng Jaccard bám sát giá trị thật, sai số giảm theo 1/√k, và mỗi tập chỉ tốn 1KB thay vì 250KB. Nền của phát hiện trùng lặp và gợi ý. 22/09/2026 · 7 phút đọc

9 Reservoir sampling: lấy mẫu ngẫu nhiên đều từ luồng mà không biết độ dài Làm sao lấy ngẫu nhiên 1000 dòng từ một log đang chảy, khi bạn không biết nó sẽ dài bao nhiêu và không thể giữ hết trong RAM? Algorithm R làm được với một lượt duyệt và bộ nhớ O(k). Bài này tự cài và đo thật: chạy 200.000 lần, mọi phần tử — đầu hay cuối luồng — đều được chọn với xác suất k/N (lệch tối đa 0.18 điểm phần trăm). Cơ chế, vì sao đều, và ứng dụng. 22/09/2026 · 7 phút đọc

10 t-digest: đo p99/p999 của luồng khổng lồ mà không cần lưu và sắp xếp cả mảng Bài Debug phần 11 tính percentile bằng cách sort cả mảng — tốn RAM tuyến tính và không mergeable. t-digest gom dữ liệu thành centroid, nén dày ở hai đuôi để p99/p999 sắc nét. Bài này cài t-digest rút gọn bằng Python, chạy thật 2 triệu latency: 171 centroid (~2,7 KB) thay 16 MB mảng, p99 sai chỉ 0,1%, và giải thích vì sao nó bền hơn histogram ô đều khi có outlier. 22/09/2026 · 8 phút đọc

11 Cuckoo filter: bộ lọc vừa tiết kiệm bộ nhớ vừa xóa được — thứ Bloom không làm Bloom filter (phần 1 loạt này) kiểm tra tồn tại rất gọn nhưng không xóa được phần tử và tỉ lệ dương tính giả cố định. Cuckoo filter lưu fingerprint vào một trong hai bucket, đá (kick) khi đầy, nên xóa được và thường chính xác hơn Bloom ở cùng bộ nhớ. Bài này tự cài Cuckoo filter bằng Python, chạy thật: 249.036 phần tử ở load 95%, FPP 0,18%, xóa hoạt động — và đo điểm giao FPP Cuckoo vs Bloom. 22/09/2026 · 8 phút đọc

12 Chọn cấu trúc dữ liệu xác suất nào? Tổng kết 12 phần bằng một bảng đo thật Khép lại loạt Cấu trúc dữ liệu xác suất: điểm lại 11 cấu trúc đã học, mỗi cái trả lời một câu hỏi khác nhau, rồi chạy thật cả năm trên CÙNG một luồng 2 triệu sự kiện để so bộ nhớ và sai số với cách 'giữ hết + tính chính xác'. Kết quả đo được: 5 sketch cộng lại chỉ 527 KB thay cho 52 MB — nhỏ hơn ~96 lần, đổi lấy sai số 0,08%–4,57%. Kèm cây quyết định và khi nào KHÔNG nên dùng ước lượng. 22/09/2026 · 8 phút đọc