Map internals trong Go: hmap, bucket 8 slot, và vì sao map không có thứ tự

Map là cấu trúc dữ liệu phức tạp nhất mà Go cung cấp sẵn, và cũng bị hiểu lầm nhiều nhất. Vì sao lặp map cho thứ tự khác nhau mỗi lần? Vì sao make(map, n) nhanh hơn nhiều so với để map tự lớn? Vì sao map tốn nhiều bộ nhớ hơn tưởng tượng? Mọi câu trả lời nằm ở cấu trúc bên trong: hmap và bucket. Bài này mổ xẻ chúng và đo trực tiếp ba hành vi quan trọng.

Cấu trúc: hmap và bucket 8 slot

Map Go là một bảng băm (hash table). Header của nó là struct hmap chứa: count (số entry), B (log2 của số bucket), buckets (con trỏ tới mảng bucket), oldbuckets (dùng khi mở rộng).

Mỗi bucket (bmap) chứa tối đa 8 cặp key-value, bố cục đặc biệt: [8 byte tophash] rồi [8 key liền nhau] rồi [8 value liền nhau] rồi [con trỏ overflow]. tophash là 8 bit cao của hash khóa — dùng để quét nhanh trong bucket mà không cần so key đầy đủ.

Khi tra một khóa k: hash(k) được tính, B bit thấp chọn bucket, 8 bit cao thành tophash. Runtime so tophash trong 8 slot của bucket — chỉ khi tophash khớp mới so key đầy đủ (tối ưu tốc độ). Nếu một bucket đầy 8 slot mà cần thêm, một bucket overflow được cấp và nối vào (tạo chuỗi).

Hình 1: hmap header + bucket chứa 8 cặp key-value với tophash để quét nhanh. Bucket đầy thì nối bucket overflow. Lặp range bắt đầu ở điểm ngẫu nhiên.

Đo thật: ba hành vi cốt lõi

1. Thứ tự lặp ngẫu nhiên. Lặp cùng một map ba lần:

2. Prealloc vs tự lớn. Chèn 1 triệu entry có và không prealloc.

3. Bộ nhớ mỗi entry. Đo bộ nhớ thực của map 1 triệu entry.

Hình 2: (1) Thứ tự lặp khác nhau mỗi lần (điểm bắt đầu ngẫu nhiên). (2) Prealloc nhanh 2 lần, cấp phát 38092 → 19. (3) Mỗi entry int→int tốn 40,2 byte dù data chỉ 16 (dư 24 byte là tophash + slot trống + overflow).

Kết quả:

• Thứ tự lặp ngẫu nhiên: lặp cùng map cho 1 2 3 4 5, rồi 3 4 5 1 2, rồi 1 2 3 4 5 — thứ tự đổi mỗi lần chạy. Go cố ý ngẫu nhiên hoá điểm bắt đầu của vòng range map (chọn bucket và offset khởi đầu ngẫu nhiên).
• Prealloc thắng lớn: make(map[int]int) tự lớn tốn 64,4 ms và 38.092 cấp phát; make(map[int]int, N) prealloc tốn 30,4 ms và chỉ 19 cấp phát — nhanh 2 lần, ít cấp phát 2000 lần. Map tự lớn phải mở rộng (evacuation) nhiều lần, cấp bucket mới liên tục.
• Bộ nhớ mỗi entry: map 1 triệu entry int→int tốn 40,2 byte/entry dù dữ liệu thực chỉ 16 byte (8 key + 8 value). Phần dư 24 byte là tophash, slot trống (bucket chỉ đầy ~65% do load factor), và con trỏ overflow.

Vì sao map không có thứ tự

Đây là quyết định thiết kế có chủ đích, không phải hạn chế kỹ thuật. Về bản chất, bảng băm không có thứ tự tự nhiên (entry nằm ở bucket theo hash). Nhưng Go còn đi xa hơn: nó cố ý ngẫu nhiên hoá điểm bắt đầu mỗi lần lặp. Lý do: ngăn lập trình viên vô tình phụ thuộc vào một thứ tự "tình cờ ổn định" — vì thứ tự thực phụ thuộc hash và sẽ đổi khi map mở rộng hoặc giữa các phiên bản Go. Bằng cách ngẫu nhiên hoá, Go buộc bạn không bao giờ dựa vào thứ tự map, tránh bug lộ ra ở production khi map lớn lên.

Ứng dụng thực tế

Luôn prealloc make(map, n) khi biết cỡ. Như đo được, prealloc cắt cấp phát từ 38.092 xuống 19 và nhanh 2 lần. Đọc n bản ghi từ database rồi cho vào map? make(map[K]V, n). Đây là một trong những tối ưu map dễ nhất và hiệu quả nhất.

Nếu cần thứ tự, sắp riêng. Muốn duyệt map theo thứ tự khóa? Lấy tất cả khóa vào slice, sort slice đó, rồi duyệt slice. Đừng bao giờ giả định range map cho thứ tự nào — code phụ thuộc thứ tự map sẽ hỏng ngẫu nhiên.

Map tốn bộ nhớ hơn slice cho cùng dữ liệu. 40 byte/entry cho int→int (so với 16 byte nếu dùng slice cặp). Nếu bạn có tập khóa nhỏ, cố định, hoặc tuần tự, một slice hoặc mảng có thể tiết kiệm bộ nhớ và nhanh hơn (thân thiện cache). Map đáng dùng khi cần tra cứu theo khóa tùy ý ở quy mô lớn.

Đánh đổi cần cân nhắc

Map nhanh cho tra cứu nhưng có overhead cố định. Băm khóa, chọn bucket, so tophash — tất cả tốn thời gian cho mỗi thao tác. Với tập nhỏ (vài phần tử), tra tuyến tính trong slice có thể nhanh hơn map (không overhead băm). Map thắng khi tập lớn và tra cứu ngẫu nhiên nhiều.

Bucket 8 slot là chi tiết cài đặt. Con số 8, load factor 6.5, cách tophash hoạt động — đều là chi tiết của runtime Go, có thể đổi (Go 1.24 có Swiss Tables cho map, cấu trúc khác hẳn). Đừng viết code phụ thuộc con số cụ thể; dựa vào tính chất "O(1) trung bình" và "không thứ tự".

Map không an toàn cho truy cập đồng thời. Cấu trúc bucket + evacuation không có khoá — đọc/ghi map từ nhiều goroutine đồng thời gây fatal error: concurrent map read and map write. Cần đồng thời thì dùng sync.Map hoặc sync.RWMutex bọc map thường (chủ đề đồng thời).

Ba ý mang về

1. Map Go là bảng băm với bucket 8 slot: hmap header + bucket chứa 8 cặp key-value và tophash (8 bit cao của hash) để quét nhanh; bucket đầy thì nối bucket overflow — đo thật mỗi entry int→int tốn 40 byte (16 data + 24 overhead).
2. Map không có thứ tự là cố ý: đo thật thứ tự lặp đổi mỗi lần vì Go ngẫu nhiên hoá điểm bắt đầu range — để ngăn phụ thuộc vào thứ tự "tình cờ"; cần thứ tự thì sắp khóa riêng.
3. Prealloc make(map, n) là tối ưu lớn: đo thật nhanh 2 lần và cắt cấp phát từ 38.092 xuống 19 vì tránh mở rộng map nhiều lần — luôn prealloc khi biết cỡ.

Phần sau ta đào sâu chính cơ chế mở rộng vừa nhắc: Phần sau mổ xẻ map evacuation — cách Go tăng gấp đôi số bucket và di chuyển entry sang dần (incremental), vì sao nó không gây khựng, và chi phí thật của việc map lớn lên.