Hashing & Hash Table — Ứng dụng thực tế
Hash function, xử lý va chạm (collision), và Consistent Hashing — kỹ thuật đứng sau sharding, load balancing, và CDN.
Hash Table là cấu trúc dữ liệu được dùng nhiều nhất trong lập trình thực tế (dict/map/object trong hầu hết ngôn ngữ) — nhưng phần lớn kỹ sư dùng nó như hộp đen O(1) mà không hiểu vì sao, và không biết Consistent Hashing (biến thể quan trọng) đang chạy bên dưới hầu hết hệ thống phân tán bạn đã học ở khoá Architecture.
🎯 Mục tiêu học tập
- Giải thích được hash function hoạt động ra sao và tính chất của 1 hash function tốt
- Hiểu 2 kỹ thuật xử lý va chạm chính: Separate Chaining và Open Addressing
- Giải thích vì sao thao tác Hash Table là O(1) trung bình nhưng O(n) trường hợp xấu nhất
- Áp dụng Consistent Hashing cho bài toán sharding/load balancing trong hệ phân tán
Hash Function & Tính chất của Hash Function tốt
Hash function biến đổi 1 khoá (key) bất kỳ (chuỗi, số, object) thành 1 số nguyên (hash code) trong 1 khoảng cố định — dùng số này làm chỉ số (index) để lưu/tra cứu trong 1 mảng bên dưới, biến thao tác tìm kiếm từ "so sánh với từng phần tử" (O(n)) thành "tính toán vị trí trực tiếp" (O(1)).
Tính chất quan trọng của hash function tốt: phân bố đều (tránh nhiều khoá cùng hash về 1 vị trí, gây collision — bên dưới), tính toán nhanh (O(1) hoặc gần O(1)), và deterministic (cùng input luôn cho cùng output — bắt buộc để tra cứu lại được).
Xử lý Va chạm (Collision) — 2 kỹ thuật chính
| Kỹ thuật | Cách hoạt động |
|---|---|
| Separate Chaining | Mỗi vị trí trong mảng chứa 1 danh sách liên kết (hoặc cấu trúc khác) — khi va chạm, thêm vào danh sách tại vị trí đó |
| Open Addressing | Khi vị trí đã có phần tử, tìm vị trí trống tiếp theo theo 1 quy tắc cố định (linear probing, quadratic probing, double hashing) |
Đây chính là lý do thao tác Hash Table "O(1) trung bình" nhưng "O(n) trường hợp xấu nhất": nếu hash function tệ hoặc bảng quá đầy (load factor cao), nhiều khoá dồn vào cùng 1 vị trí, biến tra cứu thành duyệt tuần tự cả danh sách/chuỗi collision. Các triển khai thực tế tự động resize (tăng kích thước mảng và hash lại toàn bộ) khi load factor vượt ngưỡng (thường ~0.7) để giữ hiệu năng gần O(1).
Consistent Hashing — giải quyết bài toán Resize ở hệ phân tán
Hash Table thường (Module trên) khi resize phải hash lại toàn bộ dữ liệu — chấp nhận
được trong 1 process đơn lẻ, nhưng thảm hoạ ở hệ phân tán: nếu dùng hash thường để quyết
định "key này thuộc server nào" (server = hash(key) % số_server), thêm/bớt 1 server làm
gần như toàn bộ key phải di chuyển sang server khác — với hệ thống cache/database phân
tán có hàng triệu key, đây là chi phí không thể chấp nhận được.
Consistent Hashing giải quyết bằng cách sắp xếp cả server và key lên 1 "vòng tròn hash" (hash ring) — mỗi key thuộc về server gần nhất theo chiều kim đồng hồ trên vòng tròn đó. Khi thêm/bớt 1 server, chỉ những key nằm giữa server đó và server liền kề cần di chuyển — trung bình chỉ khoảng 1/N tổng số key (N = số server), thay vì gần như toàn bộ.
Consistent Hashing là nền tảng của: Sharding database (đã học ở khoá Architecture Module 7), phân phối request trong CDN (route đến đúng edge server gần key/user), và cơ chế phân phối dữ liệu của các hệ thống NoSQL phân tán (Cassandra, DynamoDB). Dùng virtual node (mỗi server thật ánh xạ thành nhiều điểm ảo trên vòng tròn) để cân bằng tải đều hơn khi số server ít hoặc năng lực không đồng đều.
🏋️ Bài tập thực hành
Triển khai 1 hash ring đơn giản (dùng thư viện hash có sẵn của ngôn ngữ) với 3 "server" ảo. Thêm 1.000 key ngẫu nhiên, quan sát phân bố key giữa các server. Thêm 1 server thứ 4, đo % key phải di chuyển — so sánh với việc dùng hash % N thông thường (phải di chuyển gần như toàn bộ). Thử thêm virtual node (mỗi server ánh xạ 100 điểm ảo) và quan sát phân bố có đều hơn không.
📚 Tài nguyên học tập
-
Toptal — Consistent Hashing ExplainedGiải thích trực quan, dễ hiểu Consistent HashingBài viết
-
VisuAlgo — Hash TableTrực quan hoá tương tác Hash Table và collision resolutionTool
✅ Tự đánh giá hoàn thành
- Giải thích được hash function và tính chất của hash function tốt
- Phân biệt được Separate Chaining và Open Addressing
- Giải thích được vì sao Hash Table là O(1) trung bình nhưng O(n) trường hợp xấu nhất
- Triển khai được Consistent Hashing đơn giản và đo được lợi ích khi thêm/bớt server