Tất Tần Tật Về Maps (Hash Map) Trong Golang
Bài viết này sẽ nói về cấu trúc, bảng băm và hiệu suất của Map trong Golang. Cách dữ liệu thực sự được lưu trữ. Không nói về các thao tác cơ bản của Map.
1. Tổng quát cơ bản
Map về cơ bản là nơi lưu trữ key-value với khả năng tra cứu rất nhanh. Ví dụ cơ bản:
m := make(map[int]string)
m[42] = "Hello!"
value, exist := m[42]
// value = 42
// exist = true
Ngoài ra, có thể sử dụng Maps cách khác:
set := make(map[int]struct{})
_, exist := set[42]
if exist {
fmt.Println("42 is in the set")
}
Sử dụng struct{} để không tiêu tốn dung lượng lưu trữ. Xem ví dụ sau để hiểu rõ hơn: https://go.dev/play/p/p33WpvbX97f hoặc bài viết về empty struct sau: https://dave.cheney.net/2014/03/25/the-empty-struct
2. Đi sâu hơn
Map được tạo nên từ một bảng băm (hash table). Thỉnh thoảng, cây tìm kiếm (search tree) cũng được dùng để tạo nên Map trong một vài ngôn ngữ và trường hợp khác.
Ý tưởng chính của bảng băm là để thời gian tra cứu là O(1). Trường hợp tệ nhất là O(n), nếu hàm băm (hash function) gây ra n va chạm (collisions - có nghĩa là băm ra cùng 1 giá trị), điều này không thể sảy ra trong tình huống thực.
3. Băm và Sự va chạm (hash and collisions)
Theo định nghĩa, hàm băm (hash function) là một hàm biến đổi bất kỳ giá trị nào thành giá trị có kích thước cố định. Trong trường hợp của Go, nó lấy số lượng bit bất kỳ và chuyển đổi thành 64 bits
Hàm băm của golang có thể được tìm thấy ở đây: https://github.com/golang/go/blob/dev.boringcrypto.go1.13/src/runtime/hash64.go
Khi hàm băm cho ra cùng một kết quả với các giá trị khác nhau của key. Đó gọi là sự va chạm (collision). Hầu hết hàm băm an toàn đều không có những sự xung đột biết trước
4. Lý thuyết Maps ngắn ngọn
Để lưu trữ cặp key-value (KV), cách tiếp cận đơn giản nhất là tạo một danh sách và duyệt qua tất cả các cặp giá trị, điều này có độ phức tạp O(n)
Các tiếp cận tốt hơn là tạo một cây tìm kiếm cân bằng (balanced search tree) và sẽ đạt được sự hiệu quả tìm kiếm ổn định O(log(n)). Điều này tốt cho một vài trường hợp
Nhưng khi chúng ta muốn thực hiện nó nhanh hơn, khả năng tìm kiếm lên đến O(1), chúng ta sẽ nghĩ đến mảng với việc truy xuất chỉ định (giả sự arr[1] cho giá trị của phần tử thứ 2). Nhưng không thể thực hiện nó với key (string) cho mảng. Giải pháp là băm giá trị key.
Bây giờ chúng ta tạo BN buckets (bucket có giá trị từ 1 đến BN). Mỗi bucket là một danh sách đơn giản. Hàm băm sẽ chuyển đổi các key để phù hợp với một bucket nhất định: hash(key)->{1..BN}
Thêm cặp key-value mới vào Maps là chèn nó vào 1 bucket có giá trị hash(key)
5. Thời gian tra cứu
Giả sử PN là con số chứa cặp key-value trong Map
Nếu ta có PN ≤ BN và 0 sự va chạm (zero collision), đây là trường hợp lý tưởng, thời gian tra cứu là O(1)
Nếu ta có PN > BN thì ít nhất có 1 bucket sẽ chứa ít nhất 2 giá trị, vì vậy tra cứu có thể thực hiện 2 bước - xác định bucket đang chứa nó và duyệt qua danh sách của bucket đó cho đến khi tìm được cặp key-value
Số lượng cặp key-value trung bình trong buckets được gọi là hệ số tải (load factor). Load factor chia cho 2 sẽ là thời gian tra cứu trung bình, và tỷ lệ va chạm sẽ xác định sự phân tán của nó. Về mặt hình thức, độ phức tạp vẫn là O(n), nhưng trong thực tế, va chạm hiếm khi xảy ra và các Key-Value sẽ trải đều đến các bucket gần như đồng đều.
6. Triển khai Map trong Go
Source code của Maps ở đây, ít nhiều có thể hiểu được: https://github.com/golang/go/blob/master/src/runtime/map.go
Map là một con trỏ (pointer) hmap structure. Nếu cần một map mới có giá trị của map cũ, bạn phải tạo một bản sao theo cách thủ công. Bởi vì khi gán trực tiếp, mọi thay đổi của cái này sẽ ảnh hưởng đến cái khác. Xem ví dụ này để hiểu rõ hơn https://go.dev/play/p/GL2cIrGRYG2
Một điều quan trọng nữa là hàm băm dựa trên hạt giống ngẫu nhiên nên mỗi Maps được xây dựng khác nhau.
Ý tưởng đằng sau sự ngẫu nhiên này là để tránh các lỗ hổng tiềm ẩn khi tác nhân độc hại tràn ngập Map với các xung đột và để ngăn chặn mọi nỗ lực dựa vào thứ tự lặp lại Map. Map có thể lặp lại nhưng không được sắp xếp. Ngay cả mọi trình vòng lặp mới của cùng một Map đều được chọn ngẫu nhiên.
m := make(map[int]int)
for j := 0; j < 10; j++ {
m[j] = j * 2
}
for k, v := range m {
fmt.Printf("%d*2=%d ", k, v)
}
fmt.Printf("\n - - -\n")
for k, v := range m {
fmt.Printf("%d*2=%d ", k, v)
}
// Second loop of the same map would produce different order of elements
Code này sẽ in ra kết quả trong thứ tự ngẫu nhiên. Kiểm tra nó ở đây: https://play.golang.org/p/OzEhs4nr_30
Kích thước Map mặc định là 1 bucket, kích thước bucket là 8 phần tử. Hàm băm IRL thường sẽ trả về 32, 64, 256... bits. Vì vậy, ta sẽ chỉ lấy một phần bit này để sử dụng như là số của bucket (bucket number). Vì vậy, với 8 buckets, chúng ta chỉ cần log2(8)=3 bit thứ tự thấp, (8=2³, còn 16 nhóm: log2(16)=4, 16=2⁴, v.v. )
bucket := hash & bucketMask(h.B)
trong đó h.B là log_2 của BN. Tương tự như 2^h.B = BN
buckMask(h.B) là mặt nạ bit h.B đơn giản, như 00…011…1, trong đó số bit 1 là h.B
7. Sự tăng lên của Map
Nếu Map tăng lên bên ngoài giới hạn nhất định, Golang sẽ x2 số lượng buckets. Mỗi lần số lượng bucket tăng lên, nó cần phải băm lại (rehash) tất cả nội dụng Map. Bên dưới, Go sử dụng cơ chế phát triển Map phức tạp để có hiệu suất tối ưu. Trong một thời gian, Go giữ các bucket cũ cùng với các bucket mới để tránh tải đạt đỉnh và đảm bảo rằng các vòng lặp đã bắt đầu sẽ kết thúc một cách an toàn.
Điều kiện của sự tăng lên của Map từ source code:
overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)
Đầu tiên là kiểm tra hệ số tải (load factor). Tải trọng trung bình của một bucket kích thích tăng trưởng là 6,5 trở lên. Giá trị này được mã hóa cứng và dựa trên điểm chuẩn của team Golang.
Kiểm tra thứ 2 là về vượt quá số lượng buckets. Quá nhiều nghĩa là nhiều buckets vượt quá hơn số buckets thông thường. Sức chứa cố định của bucket đơn là 8 phần tử. Khi đạt đến giới hạn này, bucket này sẽ được xem như là bucket đầy
Điều thú vị là trình kích hoạt tăng trưởng đó hơi ngẫu nhiên đối với các Map lớn có ≥2¹⁶ buckets.
func (h *hmap) incrnoverflow() {
// We trigger same-size map growth if there are
// as many overflow buckets as buckets.
// We need to be able to count to 1<<h.B.
if h.B < 16 {
h.noverflow++
return
}
// Increment with probability 1/(1<<(h.B-15)).
// When we reach 1<<15 - 1, we will have approximately
// as many overflow buckets as buckets.
mask := uint32(1)<<(h.B-15) - 1
// Example: if h.B == 18, then mask == 7,
// and fastrand & 7 == 0 with probability 1/8.
if fastrand()&mask == 0 {
h.noverflow++
}
}
8. Hack Map với Unsafe
Để thu thập thêm thông tin, ta cần truy cập các giá trị nội bộ của Map, như h.B và bucket. Điều này sẽ chỉ hoạt động nếu cấu trúc bên trong của hmap không thay đổi, đã được thử nghiệm cho phiên bản 1.13.8
Chúng ta cần chuyển đổi nội dung Map thành cấu trúc hmap để thu thập dữ liệu nội bộ của Map. Bí quyết là sử dụng unsafe.Pointer và empty interface. Đầu tiên, chúng ta chuyển đổi map pointer &m thành unsafe.Pointer, sau đó chuyển đổi sang cấu trúc EmptyInterface, cấu trúc này khớp với cấu trúc bên trong empty interface thực tế. Từ cấu trúc đó, chúng ta có thể thu được map type và cấu trúc hmap.
type emptyInterface struct {
_type unsafe.Pointer
value unsafe.Pointer
}
func mapTypeAndValue(m interface{}) (*maptype, *hmap) {
ei := (*emptyInterface)(unsafe.Pointer(&m))
return (*maptype)(ei._type), (*hmap)(ei.value)
}
Và sử dụng nó như thế này:
m := make(map[int]int)
t, hm := mapTypeAndValue(m)
Chúng ta cần sao chép maptype, một số hằng số hmap, cấu trúc và các hàm từ nguồn Golang src/runtime/map.go, phiên bản nguồn phải khớp với phiên bản trình biên dịch.
Bây giờ chúng ta có thể theo dõi xem số lượng bucket thay đổi như thế nào khi thêm các phần tử mới.
m := make(map[int]int)
_, hm := mapTypeAndValue(m)
fmt.Printf("Elements | h.B | Buckets\n\n")
var prevB uint8
for i := 0; i < 100000000; i++ {
m[i] = i * 3
if hm.B != prevB {
fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)
prevB = hm.B
}
}
Chạy thử code ở đây: https://play.golang.org/p/NaoC8fkmy9x
Elements | h.B | Buckets
9 | 1 | 2
14 | 2 | 4
27 | 3 | 8
53 | 4 | 16
105 | 5 | 32
209 | 6 | 64
417 | 7 | 128
833 | 8 | 256
1665 | 9 | 512
3329 | 10 | 1024
6657 | 11 | 2048
13313 | 12 | 4096
26625 | 13 | 8192
53249 | 14 | 16384
106497 | 15 | 32768
212993 | 16 | 65536
425985 | 17 | 131072
851969 | 18 | 262144
1703937 | 19 | 524288
3407873 | 20 | 1048576
6815745 | 21 | 2097152
13631489 | 22 | 4194304
27262977 | 23 | 8388608
54525953 | 24 | 16777216
9. Kích thước được xác định trước
Đôi khi, bạn cần đưa số lượng key-value nhất định vào map. Đối với các map có kích thước đã biết, tốt hơn là chỉ định kích thước tại thời điểm tạo. Golang sẽ tự động tạo số lượng bucket phù hợp, do đó có thể tránh được chi phí cho quá trình phát triển.
m := make(map[int]int, 1000000)
_, hm := mapTypeAndValue(m)
fmt.Printf("Elements | h.B | Buckets\n\n")
fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)
for i := 0; i < 1000000; i++ {
m[i] = i * 3
}
fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)
Kết quả:
Elements | h.B | Buckets
0 | 18 | 262144
1000000 | 18 | 262144
Chạy thử code ở đây: https://play.golang.org/p/cnijjiKwM8o
10. Xóa và sự phát triển không ngừng của Map
Những điều bạn nên biết về Map dựng sẵn của Golang là chúng chỉ có thể phát triển. Ngay cả khi bạn xóa tất cả các giá trị khỏi Map, số lượng bucket sẽ vẫn giữ nguyên, mức tiêu thụ bộ nhớ cũng vậy.
m := make(map[int]int)
_, hm := mapTypeAndValue(m)
fmt.Printf("Elements | h.B | Buckets\n\n")
for i := 0; i < 100000; i++ {
m[i] = i * 3
}
for i := 0; i < 100000; i++ {
delete(m, i)
}
fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)
Kết quả:
Elements | h.B | Buckets
0 | 14 | 16384
Chạy thử code tại đây: https://play.golang.org/p/SPWixru8sdM
Được dịch lại tại:
https://hackernoon.com/some-insights-on-maps-in-golang-rm5v3ywh
All rights reserved
