Lesson 13 — Map (hash table)
3 module tương tác để hiểu map từ trong ra ngoài: (1) cách hash table dùng hash function + bucket bên trong; (2) counter pattern m[k]++ chạy từng bước; (3) iteration thứ tự random của Go là feature, không phải bug.
1. Hash table internals — key đi vào bucket nào?
Map = mảng các bucket + một hash function. Cho key, hash function tính ra index của bucket. Đi thẳng tới bucket → lookup O(1).
Hash function dưới đây là toy version để minh hoạ:
hash(s) = (Σ ASCII của ký tự) mod N với N = 8 bucket.
Go thật dùng AESHASH — nhanh và phân bố đều hơn nhiều.
alice rồi aleci (cùng chữ cái → cùng hash → cùng bucket). Bucket sẽ chứa cả 2 — đó là chaining, cách phổ biến để xử lý collision.
2. Counter playground — m[w]++ chạy từng bước
Idiom m[k]++ hoạt động được vì zero value của int là 0:
lần đầu gặp key, Go tự thêm {k: 0} rồi ++ thành 1.
| Key | Value |
|---|---|
| (map rỗng — bấm Bắt đầu) | |
Bắt đầu để khởi tạo count := make(map[string]int), sau đó Bước tiếp để xử lý từng từ. Bảng map update real-time.
3. Iteration thứ tự RANDOM — Go cố ý
Map giữ data trong các bucket — không có "thứ tự chèn". Go runtime cố tình randomize thứ tự range để dev không phụ thuộc vào nó.
Chạy for k := range m 5 lần liên tiếp với cùng map dưới đây để xem.
m := map[string]int{"alice": 30, "bob": 25, "carol": 27, "dave": 40, "eve": 22}
sort.Strings → range qua sorted slice.