Giới Thiệu

Bài viết này sẽ khám phá cấu trúc, bảng băm và hiệu suất của Map trong Golang. Chúng ta sẽ tìm hiểu cách dữ liệu được lưu trữ và cơ chế hoạt động của các Map mà không đi sâu vào các thao tác cơ bản.

1. Tổng Quan Về Map

Map trong Golang là một kiểu dữ liệu cho phép lưu trữ các cặp key-value với tốc độ truy xuất cực nhanh. Để minh họa, hãy xem ví dụ dưới đây:

m := make(map[int]string)
m[42] = "Hello!" 
value, exist := m[42]
// value = 42
// exist = true

Map cũng có thể được sử dụng như một tập hợp (set) để kiểm tra sự tồn tại của các giá trị:

set := make(map[int]struct{})
_, exist := set[42]
if exist {
  fmt.Println("42 có trong tập hợp")
}

Việc sử dụng struct{} giúp tiết kiệm dung lượng lưu trữ. Để tìm hiểu thêm, bạn có thể tham khảo tại đây hoặc đọc bài viết về empty struct của Dave Cheney.

2. Đi Sâu Vào Cấu Trúc Map

Map được xây dựng từ bảng băm (hash table), là một cấu trúc dữ liệu rất hiệu quả cho việc tìm kiếm. Mục tiêu chính của bảng băm là đảm bảo thời gian tra cứu là O(1). Tuy nhiên, trong trường hợp xấu nhất, khi xảy ra xung đột (collision), thời gian có thể là O(n).

3. Băm và Các Sự Va Chạm

Hàm băm (hash function) chuyển đổi giá trị thành một giá trị có kích thước cố định. Đối với Go, nó biến đổi số bit bất kỳ thành 64 bit. Bạn có thể tham khảo hàm băm trong Golang tại đây. Sự va chạm xảy ra khi hai giá trị khác nhau cho cùng một giá trị băm.

4. Lý Thuyết Về Maps

Một cách đơn giản để lưu trữ cặp key-value là sử dụng danh sách, nhưng sẽ có độ phức tạp O(n). Phương pháp hiệu quả hơn là sử dụng cây tìm kiếm cân bằng, giúp tìm kiếm có độ phức tạp O(log(n)). Tuy nhiên, để đạt tốc độ O(1), ta chấp nhận sử dụng bảng băm với các bucket.

5. Thời Gian Tra Cứu

Giả sử PN là số lượng cặp key-value trong Map:

• Nếu PN ≤ BN và không có va chạm, thời gian tra cứu là O(1).
• Nếu PN > BN, ít nhất sẽ có một bucket chứa nhiều hơn một giá trị, thời gian tra cứu sẽ yêu cầu hai bước: xác định bucket và tìm kiếm trong bucket đó.

6. Triển Khai Map Trong Go

Source code của Maps có thể được tìm thấy tại đây. Map là một con trỏ tới cấu trúc hmap. Để tạo một bản sao của map, bạn cần phải làm thủ công để tránh tình trạng khi thay đổi một map thì map còn lại cũng bị ảnh hưởng.

Một điều thú vị là hàm băm được xây dựng với hạt giống ngẫu nhiên, gây ra sự ngẫu nhiên trong các phần tử được lặp lại từ map. Ví dụ:

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)
}

Kết quả sẽ xuất hiện theo thứ tự ngẫu nhiên.

7. Tăng Trưởng Của Map

Khi số lượng các phần tử trong Map vượt quá giới hạn nhất định, Golang sẽ tự động tăng gấp đôi số bucket. Điều này giúp duy trì hiệu suất tối ưu khi lượng dữ liệu gia tăng.

if h.B < 16 {
   h.noverflow++
}

8. Hack Map Bằng Unsafe

Để truy cập các giá trị nội bộ của Map, ta có thể sử dụng unsafe.Pointer. Điều này cho phép theo dõi số lượng bucket khi thêm các phần tử mới vào map:

m := make(map[int]int)
t, hm := mapTypeAndValue(m)

9. Kích Thước Được Xác Định Trước

Khi biết trước số lượng key-value cần lưu trữ, bạn nên khởi tạo map với kích thước cụ thể để tránh chi phí cho việc phát triển:

m := make(map[int]int, 1000000)

10. Xóa Và Sự Phát Triển Của Map

Thực tế, khi xóa tất cả các giá trị trong Map, số lượng bucket vẫn giữ nguyên, dẫn đến mức tiêu thụ bộ nhớ vẫn không thay đổi. Điều này có thể được chứng minh với đoạn mã:

m := make(map[int]int)

Kết Luận

Map trong Golang là một công cụ mạnh mẽ cho việc lưu trữ dữ liệu. Bài viết này đã cung cấp cái nhìn sâu sắc về cách thức hoạt động, cấu trúc và hiệu suất của Map, giúp bạn nắm bắt hiệu quả hơn khi làm việc với Golang.
source: viblo