Hash Table — từ ngây thơ tới production
Hash function của README §3: h(s) = (Σ ASCII của s) mod 10. Bảng 10 ô (CAP=10). Demo với 5 user của README: alice/bob/carol/dave/eve.
Vì phép cộng giao hoán, mọi anagram có cùng tổng ASCII → cùng hash. Hash table vẫn cho kết quả đúng (chain) nhưng tốc độ tụt xuống mức linear scan trong slot cluster.
Polynomial hash phụ thuộc vị trí: h(s) = s[0]·31^(n-1) + s[1]·31^(n-2) + … + s[n-1]·31^0 (mod m). Đổi thứ tự → đổi hệ số → đổi kết quả.
| Chuỗi | Sum ASCII | mod 10 (sum) | Polynomial 31 | mod 1.000.003 (poly) |
|---|
Hash production-grade FNV-1a (mod 8). Phụ thuộc vị trí qua XOR + nhân prime, không bị anagram clustering. Đây là kiểu hash mà Go/Java/Python dùng nội bộ (tinh vi hơn).
Bài 3 README: tìm 2 số có tổng = k trong O(n). Với mỗi x, kiểm tra (k−x) đã thấy chưa trong map.
Consistent hashing — vòng băm (README §11.2)
Server đặt nhiều điểm trên vòng (0..360°). Key đi theo chiều kim đồng hồ tới server gần nhất.
Thêm/bớt server chỉ remap key lân cận — KHÁC hash%N (đổi N = remap gần hết).