Tìm kiếm nhanh — Hashing & Tree

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

Java junior override equals nhưng quên hashCode — HashSet.contains() trả false dù phần tử đã add. Bài này giải thích tại sao: uniform distribution, avalanche effect, hashCode/equals contract, và vì sao bug hashCode lại silent.

HashMap internals — Separate chaining + treeify từ Java 8

Amortized O(1) của HashMap nghe có vẻ chắc chắn — cho đến khi attacker dùng key cố tình collide và API endpoint của bạn spike CPU 100%. Bài này đi sâu vào bucket array, chaining, treeify Java 8, resize, và khi nào O(1) claim thực sự đứng vững.

Open addressing — Linear / quadratic probing, Robin Hood, và vì sao Java chọn chaining

Python dict, Go map, Rust HashMap đều dùng open addressing — nhưng Java HashMap lại chọn separate chaining. Bài này giải thích 3 strategy probing, Robin Hood hashing, tombstone khi delete, và lý do kỹ thuật + lịch sử đằng sau quyết định thiết kế của mỗi ngôn ngữ.

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

90% implementation đầu tay bị reviewer reject vì overflow, off-by-one, hoặc infinite loop. Bài này dạy binary search bằng invariant — biết invariant thì mọi variant viết được trong 1 phút mà không bug.

Binary Search Tree — Insert, search, delete, và lý do skewed BST trở thành linked list

Tutorial BST dạy search O(log n) — đẹp lý thuyết. Nhưng insert sorted sequence vào BST sẽ degenerate thành linked list, mọi operation O(n). Bài này dạy BST từ insert/search/delete với code đầy đủ, delete với in-order successor, và lý do cần balanced BST.

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

BST skewed là O(n) — lesson 05 đã chứng minh điều đó. Self-balancing tree giải quyết bằng cách tự tái cấu trúc sau mỗi insert/delete. Bài này dạy intuition AVL và Red-Black tree: invariant, rotation cơ bản, trade-off — đủ để đọc source TreeMap mà không cần full-code AVL/RB từ đầu.

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

Red-Black tree tuyệt vời cho RAM — height O(log n), 20–40 bước cho 1 tỷ phần tử. Nhưng MySQL và Postgres dùng B+tree, không phải RB. Bài này giải thích tại sao disk seek thay đổi mọi tính toán: fanout, leaf chain, và cơ chế search/insert của B+tree.

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

HashMap không thể tìm prefix hiệu quả. Trie giải quyết bằng cách biến mỗi ký tự thành một node, biến prefix query thành đường đi O(L) độc lập với số từ đã lưu. Bài này dạy trie cơ bản, Patricia/Radix tree, và ứng dụng thực tế từ autocomplete đến IP routing.

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

Cassandra, Chrome, HBase đều dùng Bloom filter để tránh disk read tốn kém. Bài này giải thích cấu trúc bit array + k hash function, công thức false positive rate, trick 2-hash Kirsch-Mitzenmacher, và các variant counting/scalable — nền tảng để hiểu probabilistic data structure trong hệ thống phân tán.

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

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

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

MySQL và Redis đều giải bài toán 'tìm key nhanh' — nhưng chọn hai cấu trúc dữ liệu hoàn toàn khác nhau. Bài này dive source thật của InnoDB B+tree clustered index và Redis dict incremental rehash để hiểu vì sao mỗi quyết định đúng cho context của nó.