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

TL;DR: Module 1 trang bị 7 cấu trúc tìm kiếm mà mọi hệ thống production dùng hàng ngày. Bắt đầu từ hash function — nền tảng của HashMap, cache key, distributed shard — rồi leo qua open addressing, binary search, BST, cây cân bằng AVL/RB, B-tree/B+tree, trie và bloom filter. Mỗi bài giải thích cơ chế bên dưới, phân tích khi nào cấu trúc đó thắng và khi nào nó thua. Kết thúc bằng case study thật: MySQL chọn B+tree vì sao, Redis giải quyết resize không blocking thế nào.

Vì sao module này tồn tại

Mỗi lần bạn gọi map.get(key), trình duyệt kiểm tra URL trong blacklist, autocomplete gợi ý từ khoá, hay MySQL chạy SELECT * FROM orders WHERE id = 42 — một cấu trúc tìm kiếm đang chạy bên dưới. Lựa chọn sai cấu trúc không chỉ làm chậm — nó thay đổi độ phức tạp từ O(1) thành O(n) trên tập dữ liệu hàng triệu phần tử.

Vấn đề là hầu hết tài liệu dừng ở API: "dùng HashMap cho O(1), dùng TreeMap cho sorted". Module này đi xuống tầng cơ chế: hash function cần uniform distribution và avalanche effect để làm gì, tại sao open addressing nhanh hơn chaining trên CPU hiện đại dù cùng O(1) trung bình, bất biến của binary search hoạt động ra sao, và vì sao B+tree cần leaf linked list cho range query còn hash table thì không.

Hiểu cơ chế giúp bạn làm 3 việc mà chỉ biết API không làm được:

• Chẩn đoán performance bottleneck: HashMap chậm không phải vì O(1) sai mà vì load factor 0.95 gây chain dài.
• Chọn đúng cấu trúc khi thiết kế: trie cho prefix search, bloom filter cho membership check tiết kiệm RAM, B+tree cho disk index.
• Đọc hiểu source và documentation của database, cache, search engine — vì chúng đều dùng các cấu trúc này.

Phần HashMap nội tạng JDK — chaining chi tiết, treeify threshold, resize 2x, ConcurrentHashMap lock-striping — nằm ở khoá Java Internals vì nó gắn chặt với Java bytecode và JVM. Module này dạy tư tưởng thuật toán ngôn-ngữ-trung-lập; nếu bạn học Java thì đọc thêm Java Internals — HashMap internals để thấy các khái niệm module này ánh xạ thế nào vào JDK source.

Sau module này bạn sẽ

• Implement hashing với chaining và open addressing, phân tích load factor ảnh hưởng đến probe length và khi nào nên resize.
• Compare các cây tìm kiếm — BST, cây cân bằng (AVL/RB), B-tree, trie — theo trường hợp dùng, workload và constraint bộ nhớ.
• Explain binary search cùng bất biến của nó, và bloom filter cùng đánh đổi false-positive rate vs RAM.
• Design index cho hệ thống thật: B+tree của database, skiplist của Redis, trie của autocomplete engine.

Bản đồ module

flowchart LR
    A["00\nTổng quan"] --> B["01\nHash function\nuniform, avalanche"]
    B --> C["03\nOpen addressing\nprobing, tombstone"]
    C --> D["04\nBinary search\nbất biến"]
    D --> E["05\nBST\ninsert, delete"]
    E --> F["06\nCây cân bằng\nAVL, Red-Black"]
    F --> G["07\nB-tree & B+tree\ndisk index"]
    G --> H["08\nTrie\nprefix search"]
    H --> I["09\nBloom filter\nprobabilistic"]
    I --> J["10\nMini-challenge\nautocomplete"]
    J --> K["11\nCase study\nMySQL & Redis"]
    K --> L["12\nTổng kết"]

(Bài 02 — HashMap internals JDK — nằm ở khoá Java Internals; link mềm ở bài 01 cuối trang.)

Lộ trình module

Thứ tự bài được thiết kế theo nguyên tắc "xây từ nền — mỗi bài mở khoá bài sau":

Bài 01 — Hash function là điểm khởi đầu: uniform distribution và avalanche effect là hai thuộc tính cốt lõi mà mọi cấu trúc hash-based đều phụ thuộc. Không hiểu hash function, bạn không thể phân tích tại sao HashMap thoái hoá hay open addressing hoạt động.

Bài 03 — Open addressing tiếp ngay sau chaining: thay vì linked list, ghi entry trực tiếp vào array bằng probing. Nhanh hơn trên CPU hiện đại vì cache locality, nhưng cần hiểu tombstone và clustering để tránh pitfall.

Bài 04 — Binary search là bước chuyển sang cấu trúc dạng cây: sorted array + bất biến loop invariant. Tư tưởng "phân đôi không gian tìm kiếm" sẽ xuất hiện lại trong BST, B-tree, và thậm chí trie.

Bài 05 — BST xây cây tìm kiếm từ nền: mỗi node là một binary search. Bài này cũng giải thích vì sao BST không đủ — worst case O(n) khi cây mất cân bằng là động lực trực tiếp của bài tiếp theo.

Bài 06 — Cây cân bằng (AVL, Red-Black tree) giải quyết vấn đề của BST: rotation để duy trì height O(log n) dù insert/delete pattern ra sao. Bài giải thích khi nào dùng AVL (read-heavy) vs Red-Black (write-heavy).

Bài 07 — B-tree & B+tree mở rộng cây ra disk: fanout lớn (1000+) giảm height xuống 3-4 cho 100 triệu row, leaf linked list cho range scan. Đây là cấu trúc sau MySQL InnoDB index.

Bài 08 — Trie là cây chuyên biệt cho string key: mỗi edge là một ký tự, tất cả string có cùng prefix chia sẻ cùng path. Dùng trong autocomplete, IP routing table, dictionary.

Bài 09 — Bloom filter là cấu trúc probabilistic: bit array + k hash function, không có false negative, có false positive kiểm soát được. 1 triệu key chỉ cần 1.2MB. Dùng trong Cassandra, Chrome safe-browsing, HBase.

Bài 10 — Mini-challenge áp dụng trie vào autocomplete thật: implement prefix search với frequency ranking.

Bài 11 — Case study kết nối lý thuyết vào production: MySQL InnoDB chọn B+tree vì sao, Redis giải quyết resize không blocking thế nào. Đọc source thật, hiểu quyết định thiết kế.

Bài 12 — Tổng kết gom cheat sheet, glossary và self-assessment.

Yêu cầu trước khi bắt đầu

• Đã học Thuật toán Căn bản — Module 1 (phức tạp thuật toán — O-notation, Big-O analysis) và Thuật toán Căn bản — Module 2 (cấu trúc dữ liệu tuyến tính — array, linked list, stack, queue, heap).
• Hiểu khái niệm pointer/reference và cách linked list hoạt động — BST và trie dùng node chứa con trỏ tới con.
• Không yêu cầu ngôn ngữ cụ thể — pseudocode trong module này ngôn-ngữ-trung-lập.

Time budget

Cách học module này hiệu quả

• Vẽ sơ đồ tay. BST, AVL rotation, B-tree split — tất cả đều cần visualize. Vẽ tay trên giấy từng bước insert và delete trước khi đọc pseudocode. Não xử lý thao tác cây tốt hơn nhiều khi có hình ảnh.
• Hỏi "khi nào cái này thua?". Mỗi cấu trúc có worst case. BST thoái hoá về O(n). Bloom filter không delete được. Trie tốn RAM khi alphabet lớn. Biết giới hạn quan trọng hơn biết ưu điểm.
• Liên hệ ngay vào công cụ bạn đang dùng. HashMap trong Java/Python/Go, index trong MySQL/PostgreSQL, KEYS trong Redis, autocomplete trong IDE — tất cả đều dùng cấu trúc trong module này. Mỗi khi gặp một tool mới, hỏi "cấu trúc nào đằng sau đó?".
• Module 2 (Sắp xếp) xây trực tiếp trên module này. Heap sort dùng heap từ Thuật toán Căn bản — Module 2. Counting sort dùng array hash. Radix sort dùng tư tưởng trie. Biết Module 1 vững, Module 2 sẽ nhanh hơn nhiều.

Bài tiếp theo: Hàm băm