Module 1 — Tổng kết & cheat sheet

TL;DR: Module 1 trang bị 7 cấu trúc tìm kiếm từ hash table đến trie và bloom filter — mỗi cái đúng cho một constraint khác nhau. Đây là trang để bookmark: bảng so sánh thời gian/không gian, glossary 20 thuật ngữ, 5 pitfall lớn nhất và self-assessment 4 outcomes. Nếu bạn implement được hash table với open addressing, giải thích được tại sao MySQL chọn B+tree còn Redis chọn hash table, và thiết kế được bloom filter với false-positive rate cho trước, bạn đã sẵn sàng cho Module 2 — Sắp xếp & thứ tự.

Đã đi qua những gì

Bạn bắt đầu từ bài 00 — Tổng quan module: tìm kiếm nhanh không phải một cấu trúc duy nhất — mỗi constraint (disk vs RAM, point query vs range query, exact vs prefix) dẫn đến cấu trúc tối ưu khác nhau.

Bài 01 mổ xẻ hash function: uniform distribution (output rải đều bucket, tránh hot spot) và avalanche effect (1 bit input đổi thì khoảng 50% bit output đổi, tránh clustering). hashCode/equals contract — vi phạm dẫn đến HashMap lookup silent fail mà không exception.

Bài 03 đi vào open addressing: thay vì linked list, ghi trực tiếp vào array bằng probing. Linear probing — cache friendly nhưng dễ clustering. Quadratic probing và double hashing giảm clustering. Tombstone để xử lý delete mà không phá vỡ probe chain. Python dict và Rust HashMap đều dùng open addressing vì cache locality trên CPU hiện đại.

Bài 04 giải thích binary search và bất biến của nó: target luôn nằm trong đoạn [left, right]. Bài cũng chỉ rõ 3 variant (lower bound, upper bound, exact match) và tại sao mỗi variant cần điều kiện loop và cách tính mid khác nhau để tránh infinite loop và off-by-one.

Bài 05 xây BST từ nền: mỗi node thỏa mãn BST property — left subtree toàn nhỏ hơn, right subtree toàn lớn hơn. Insert O(log n), delete phức tạp hơn khi node có hai con (thay bằng in-order successor). Worst case O(n) khi insert sorted — là động lực trực tiếp của cây cân bằng.

Bài 06 giải thích cây cân bằng: AVL và Red-Black tree dùng rotation để giữ height O(log n). AVL strict balance (height diff tối đa 1) — lookup nhanh hơn, phù hợp read-heavy. Red-Black relaxed balance (nhiều constraint màu) — insert/delete ít rotation hơn, phù hợp write-heavy. Java TreeMap và C++ std::map dùng Red-Black.

Bài 07 mở rộng ra B-tree và B+tree cho disk: node lớn (16KB page), fanout 1000 với integer key, height 3-4 cho 100 triệu row. B+tree thêm leaf linked list cho range scan tuần tự O(k). InnoDB clustered index lưu toàn bộ row tại leaf — 1 walk cho primary key lookup.

Bài 08 giải thích trie: cây chuyên biệt cho string key, mỗi edge là một ký tự, tất cả string cùng prefix chia sẻ cùng path. Insert/lookup/prefix search O(L) với L là độ dài key — độc lập với kích thước tập dữ liệu. Dùng trong autocomplete, IP routing table (Patricia trie), spell checker.

Bài 09 trình bày bloom filter: bit array kích thước m kết hợp k hash function. add(x) set k bit; mightContain(x) check k bit. Không false negative, có false positive kiểm soát được. Trick Kirsch-Mitzenmacher g_i = h1 + i × h2 cho phép dùng chỉ 2 hash function. 1 triệu key với FP rate 1% chỉ cần 1.2MB.

Bài 10 áp dụng trie vào mini-challenge: autocomplete với frequency ranking — prefix search O(L) và top-k result bằng priority queue.

Bài 11 kết nối lý thuyết vào production: MySQL InnoDB chọn B+tree vì disk + range query, leaf chain cho range scan, fanout 1000 giảm IO. Redis chọn hash table vì RAM + point query, incremental rehash tránh blocking trên single-threaded event loop — duy trì 2 table đồng thời, mỗi command migrate vài bucket.

🗺️ Cheat sheet

Bảng so sánh 7 cấu trúc

*O(1) amortized với tombstone; thực tế cần resize khi load factor cao.

L = độ dài key, N = số key, m = kích thước bit array, k = số hash function.

Quy tắc chọn cấu trúc

flowchart TD
    Q1{"Cần\nrange query?"}
    Q2{"Key là\nstring/prefix?"}
    Q3{"Sống\ntrên disk?"}
    Q4{"Cho phép\nfalse positive?"}
    Q5{"Cần\nexact match\nO(1)?"}
    BTREE["B+tree\n(database index)"]
    TRIE["Trie\n(autocomplete,\nIP routing)"]
    BLOOM["Bloom filter\n(membership,\ntiết kiệm RAM)"]
    HASH["Hash table\n(HashMap, cache)"]
    BALANCED["Cây cân bằng\n(TreeMap/Set)"]

    Q1 -- "có" --> Q3
    Q1 -- "không" --> Q2
    Q2 -- "có (prefix)" --> TRIE
    Q2 -- "không" --> Q4
    Q4 -- "có" --> BLOOM
    Q4 -- "không" --> Q5
    Q5 -- "có" --> HASH
    Q5 -- "không" --> BALANCED
    Q3 -- "có" --> BTREE
    Q3 -- "không" --> BALANCED

Hash table — công thức load factor

load factor α = n / m        -- n: số entry, m: số bucket

Chaining:
  Probe length trung bình = 1 + α/2
  α = 0.75: probe ≈ 1.375 (HashMap Java default resize tại đây)
  α = 0.95: probe ≈ 1.475 (chain dài, lookup chậm hơn 2-3x)

Open addressing (linear probing):
  Probe length trung bình = 1/2 × (1 + 1/(1 - α))
  α = 0.5: probe ≈ 1.5
  α = 0.75: probe ≈ 2.5
  α = 0.9: probe ≈ 5.5   -- thoái hoá nhanh, resize trước 0.8

Bloom filter — công thức tham số

Cho n key cần insert, FP rate p mong muốn:

m (số bit) = -n × ln(p) / (ln 2)^2     -- ≈ -1.44 × n × log2(p)
k (số hash) = (m/n) × ln 2             -- ≈ 0.693 × m/n

Ví dụ: n = 1.000.000, p = 0.01 (1%)
  m = -1.000.000 × ln(0.01) / (ln 2)^2 ≈ 9.585.059 bit ≈ 1.2 MB
  k = (9.585.059 / 1.000.000) × ln 2 ≈ 6.64 → dùng k = 7

B+tree — fanout và height

Fanout f = page_size / (key_size + pointer_size)
InnoDB: page 16KB, int key 8B → f ≈ 1000

Height h cho N record: h = ceil(log_f(N))

N = 1 triệu:   h = ceil(log_1000(10^6)) = 2  →  2 disk seek
N = 1 tỷ:      h = ceil(log_1000(10^9)) = 3  →  3 disk seek
N = 100 triệu: h = 3 (buffer pool cache internal node → 1 disk seek thực tế)

📖 Glossary module

⚠️ Pitfall tổng hợp

Pitfall 1 — Load factor quá cao trong open addressing. Chaining chịu được load factor 0.9+ tương đối tốt (chain dài nhưng vẫn hoạt động). Open addressing với load factor vượt 0.8 thì probe length tăng phi tuyến — linear probing ở α = 0.9 trung bình thử 5.5 lần. Resize trước khi vượt 0.75 (chaining) hoặc 0.7 (open addressing).

Pitfall 2 — Xoá trong open addressing bằng cách xoá trực tiếp. Xoá entry mà không để tombstone làm gián đoạn probe chain — các entry phía sau vẫn còn nhưng lookup sẽ dừng sớm và báo "không tìm thấy" sai. Luôn thay entry đã xoá bằng tombstone, hoặc dùng Robin Hood hashing với backward shift deletion.

Pitfall 3 — Off-by-one trong binary search. while left < right hay while left <= right? mid = (left + right) / 2 hay mid = left + (right - left) / 2? Cách viết sai gây infinite loop hoặc miss phần tử cuối. Mỗi variant (lower bound, upper bound, exact) cần điều kiện loop và cách update left/right nhất quán với bất biến đã chọn. Viết ra bất biến trước khi code.

Pitfall 4 — Dùng bloom filter khi cần delete. Standard bloom filter không hỗ trợ delete — xoá bit có thể xoá bit của entry khác cùng chia sẻ vị trí đó. Nếu cần delete, dùng counting bloom filter (thay mỗi bit bằng counter) hoặc cuckoo filter. Nếu dùng standard bloom filter mà insert vượt n dự kiến ban đầu, FP rate tăng vọt ngoài dự tính.

Pitfall 5 — Dùng UUID v4 làm primary key trong B+tree. UUID v4 random hoàn toàn — mỗi insert rơi vào vị trí ngẫu nhiên trong B+tree, gây page split liên tục. Sau 1 triệu insert: tree fragmented, nhiều half-full page, write amplification cao. Dùng UUID v7 (timestamp prefix monotonic, RFC 9562) hoặc AUTO_INCREMENT BIGINT để insert gần-sequential, tối thiểu page split.

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Implement được hash table với chaining và open addressing, giải thích tại sao load factor ảnh hưởng đến probe length và khi nào nên resize.
  • Nếu chưa: đọc lại bài 01 — Hash function (mục uniform distribution, avalanche) và bài 03 — Open addressing (mục linear probing, tombstone).
• So sánh được BST, cây cân bằng (AVL/RB), B-tree và trie theo trường hợp dùng — giải thích tại sao mỗi cái thắng trong context của nó.
  • Nếu chưa: đọc lại bài 05 — BST, bài 06 — Cây cân bằng, bài 07 — B-tree, bài 08 — Trie.
• Giải thích được binary search cùng bất biến của nó, và bloom filter cùng đánh đổi false-positive — tính được m và k cho FP rate cho trước.
  • Nếu chưa: đọc lại bài 04 — Binary search (mục loop invariant) và bài 09 — Bloom filter (mục công thức tham số).
• Thiết kế được index cho hệ thống thật — giải thích tại sao MySQL InnoDB dùng B+tree và Redis dùng hash table với incremental rehash.
  • Nếu chưa: đọc lại bài 11 — Case study MySQL & Redis (mục clustered index, incremental rehash).

🚀 What's next

Module 1 cho bạn bộ cấu trúc tìm kiếm cốt lõi — biết cấu trúc nào đúng cho bài toán nào. Module 2 — Sắp xếp & thứ tự phóng to vào bài toán thứ hai: sắp xếp dữ liệu hiệu quả. Merge sort, quick sort, heap sort, counting sort, radix sort — mỗi thuật toán đúng cho một constraint khác nhau (in-place vs stable, comparison vs non-comparison, disk vs RAM). Hiểu Module 1 vững (đặc biệt heap từ Thuật toán Căn bản — Module 2 và BST/balanced tree từ Module 1) giúp bạn tiếp thu Module 2 nhanh hơn nhiều.

Bài tiếp theo: Module 2 — Sắp xếp & thứ tự: tổng quan

📚 Tài liệu mở rộng

• Sách: Introduction to Algorithms, 4th Edition (CLRS) — Cormen, Leiserson, Rivest, Stein. Chapters 11 (Hash Tables), 12-13 (BST & Red-Black Tree), 18 (B-Trees). Phân tích toán học chặt chẽ nhất, có proof cho mọi claim về độ phức tạp.
• Sách: Algorithms, 4th Edition — Robert Sedgewick & Kevin Wayne (Princeton). Phần 3 (Searching): BST, Red-Black BST, hash table với animation minh hoạ. Đọc miễn phí tại algs4.cs.princeton.edu.
• Paper: Less Hashing, Same Performance: Building a Better Bloom Filter — Kirsch & Mitzenmacher (2008). Chứng minh trick g_i = h1 + i × h2 cho cùng FP rate với chỉ 2 hash function — nền tảng của mọi bloom filter hiện đại.
• Source: Redis src/dict.c — dictRehash(), dictFind() trong rehash phase, dictRehashMilliseconds(). Code thực tế ngắn và dễ đọc, minh hoạ trực tiếp incremental rehash.
• Source: MySQL InnoDB btr0btr.cc — B+tree insert, page split, merge logic. Hàm btr_page_split_and_insert cho thấy chi tiết khi nào và thế nào page split xảy ra.
• Blog: Bill Mill — "Bloom Filters by Example" — interactive demo, thay đổi m và k để thấy FP rate thay đổi theo thời gian thực.