Tìm kiếm nhanh — Hashing & Tree

Module 1 — Tìm kiếm nhanh: tổng quan

Hashing, binary search, BST, cây cân bằng, B-tree, trie, bloom filter — bộ cấu trúc dữ liệu cốt lõi của mọi database, cache, search engine.

Hash function — Uniform, avalanche, và hashCode/equals contract

Override equals mà quên hashCode khiến HashSet.contains() trả false — silent bug. Uniform distribution, avalanche effect và hashCode/equals contract.

Open addressing — Probing, Robin Hood và vì sao Java chọn chaining

Python dict, Go map, Rust HashMap dùng open addressing; Java chọn chaining. Giải thích probing, Robin Hood hashing, tombstone và lý do thiết kế.

Binary search — Invariant, lower/upper bound và search-on-answer

90% implementation bị reject vì overflow, off-by-one hoặc infinite loop. Binary search bằng invariant — nắm invariant là viết mọi variant trong 1 phút.

BST — Insert, search, delete và tại sao skewed BST là O(n)

Insert sorted sequence vào BST biến cây thành linked list, operation rớt O(n). Insert/search/delete BST với pseudocode đầy đủ và lý do cần balanced BST.

Self-balancing tree — AVL vs Red-Black và lý do TreeMap chọn RB

Self-balancing tree giữ height O(log n) bằng tái cấu trúc sau insert/delete. Dạy AVL và Red-Black: invariant, rotation, trade-off — đủ để đọc source TreeMap.

B-tree & B+tree — Disk fanout, vì sao DB không dùng AVL/RB

MySQL và Postgres dùng B+tree, không phải Red-Black. Disk seek thay đổi mọi tính toán: fanout cao giảm height, leaf chain cho range scan — giải thích cơ chế.

Trie — Autocomplete, IP routing, và prefix-friendly dictionary

Trie biến prefix query thành O(L) độc lập với số từ — HashMap phải scan O(n×L). Bài dạy trie, Patricia/Radix tree và ứng dụng từ autocomplete đến IP routing.

Bloom filter — Probabilistic membership với 99% RAM tiết kiệm

Cassandra, Chrome, HBase dùng Bloom filter tránh disk read tốn kém. Giải thích bit array, k hash function, false positive rate và trick Kirsch-Mitzenmacher.

Mini-challenge — Autocomplete top-K với Trie + frequency

Implement Autocomplete: insert word với frequency, suggest top-K theo prefix dùng Trie + DFS + min-heap. Pattern cốt lõi của search box.

Case Study: MySQL InnoDB B+tree index + Redis dict incremental rehash

MySQL và Redis cùng giải bài tìm key nhanh nhưng chọn cấu trúc khác nhau. InnoDB B+tree clustered index và Redis incremental rehash — lý do thiết kế.

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

Recap tìm kiếm nhanh: bảng so sánh 7 cấu trúc, glossary, 5 pitfall lớn nhất, self-assessment 4 outcomes và tài liệu mở rộng.