Map trong Go

Nói chung, việc thực hiện cấu trúc dữ liệu map thường có hai loại, bảng băm (hash table) và cây tìm kiếm (search tree), điểm khác biệt là cái trước không có thứ tự, cái sau có thứ tự. Trong Go, việc thực hiện map dựa trên thùng băm (cũng là một loại bảng băm), nên cũng không có thứ tự, bài này sẽ không giải thích quá nhiều về nguyên lý thực hiện, điều này vượt quá phạm vi cơ bản, sau này sẽ đi sâu phân tích.

TIP

Muốn tìm hiểu nguyên lý của map có thể đến Thực hiện map

Khởi tạo

Trong Go, kiểu khóa của map phải có thể so sánh được, ví dụ string, int là có thể so sánh được, còn []int là không thể so sánh được, nên không thể làm khóa của map. Có hai phương pháp khởi tạo một map, phương pháp đầu tiên là giá trị chữ, định dạng như sau:

map[keyType]valueType{}

Một vài ví dụ

mp := map[int]string{
   0: "a",
   1: "a",
   2: "a",
   3: "a",
   4: "a",
}

mp := map[string]int{
   "a": 0,
   "b": 22,
   "c": 33,
}

Phương pháp thứ hai là sử dụng hàm tích hợp make, đối với map而言, nhận hai tham số, lần lượt là kiểu và dung lượng ban đầu, ví dụ như sau:

mp := make(map[string]int, 8)

mp := make(map[string][]int, 10)

Map là kiểu tham chiếu, giá trị 0 hoặc map chưa khởi tạo có thể truy cập, nhưng không thể lưu trữ phần tử, nên phải phân bổ bộ nhớ cho nó.

func main() {
   var mp map[string]int
   mp["a"] = 1
   fmt.Println(mp)
}

panic: assignment to entry in nil map

TIP

Khi khởi tạo map nên phân bổ một dung lượng hợp lý, để giảm số lần mở rộng.

Truy cập

Cách truy cập một map giống như truy cập một mảng thông qua chỉ số.

func main() {
  mp := map[string]int{
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
  }
  fmt.Println(mp["a"])
  fmt.Println(mp["b"])
  fmt.Println(mp["d"])
  fmt.Println(mp["f"])
}

0
1
3
0

Thông qua mã có thể quan sát thấy, ngay cả khi trong map không tồn tại cặp khóa-giá trị "f", nhưng vẫn có giá trị trả về. Map đối với khóa không tồn tại, giá trị trả về của nó là giá trị 0 của kiểu tương ứng, và khi truy cập map thực ra có hai giá trị trả về, giá trị trả về đầu tiên là giá trị của kiểu tương ứng, giá trị trả về thứ hai là một giá trị boolean, đại diện cho khóa có tồn tại hay không, ví dụ:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   if val, exist := mp["f"]; exist {
      fmt.Println(val)
   } else {
      fmt.Println("khóa không tồn tại")
   }
}

Tính chiều dài của map

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(len(mp))
}

Lưu giá trị

Cách lưu giá trị của map cũng giống như lưu giá trị của mảng, ví dụ:

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   fmt.Println(mp)
}

Khi lưu giá trị, sử dụng khóa đã tồn tại sẽ ghi đè giá trị ban đầu

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   if _, exist := mp["b"]; exist {
      mp["b"] = 3
   }
   fmt.Println(mp)
}

Nhưng cũng tồn tại một trường hợp đặc biệt, đó là khi khóa là math.NaN()

func main() {
  mp := make(map[float64]string, 10)
  mp[math.NaN()] = "a"
  mp[math.NaN()] = "b"
  mp[math.NaN()] = "c"
  _, exist := mp[math.NaN()]
  fmt.Println(exist)
  fmt.Println(mp)
}

false
map[NaN:c NaN:a NaN:b]

Thông qua kết quả có thể quan sát thấy cùng một khóa không ghi đè, ngược lại còn có thể tồn tại nhiều, cũng không thể phán đoán xem có tồn tại hay không, nên không thể lấy giá trị bình thường. Vì NaN là được định nghĩa trong tiêu chuẩn IEE754, việc thực hiện của nó do lệnh hợp ngữ cấp thấp UCOMISD hoàn thành, đây là một lệnh so sánh kép không có thứ tự, lệnh này sẽ xem xét đến trường hợp NaN, nên kết quả là bất kỳ số nào cũng không bằng NaN, NaN cũng không bằng chính nó, điều này cũng dẫn đến việc mỗi lần giá trị băm đều không giống nhau. Về điểm này cộng đồng cũng từng thảo luận sôi nổi, nhưng chính thức cho rằng không cần thiết phải sửa đổi, nên尽量避免 sử dụng NaN làm khóa của map.

Xóa

func delete(m map[Type]Type1, key Type)

Xóa một cặp khóa-giá trị cần dùng hàm tích hợp delete, ví dụ

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(mp)
   delete(mp, "a")
   fmt.Println(mp)
}

map[a:0 b:1 c:2 d:3]
map[b:1 c:2 d:3]

Cần lưu ý là, nếu giá trị là NaN, thậm chí không thể xóa cặp khóa-giá trị đó.

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   fmt.Println(mp)
   delete(mp, math.NaN())
   fmt.Println(mp)
}

map[NaN:c NaN:a NaN:b]
map[NaN:c NaN:a NaN:b]

Duyệt

Thông qua for range có thể duyệt map, ví dụ

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

c 2
d 3
a 0
b 1

Có thể thấy kết quả không có thứ tự, cũng xác nhận map lưu trữ không có thứ tự. Đáng nói là, NaN tuy không thể lấy bình thường, nhưng có thể truy cập thông qua duyệt, ví dụ

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

NaN a
NaN c
NaN b

Xóa sạch

Trước go1.21, muốn xóa sạch map, chỉ có thể delete từng khóa của map

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  for k, _ := range m {
    delete(m, k)
  }
  fmt.Println(m)
}

Nhưng go1.21 đã cập nhật hàm clear, không cần phải thực hiện thao tác trước đó nữa, chỉ cần một clear là có thể xóa sạch

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  clear(m)
  fmt.Println(m)
}

Xuất ra

map[]

Set

Set là một tập hợp không có thứ tự, không chứa phần tử trùng lặp, Go không cung cấp việc thực hiện cấu trúc dữ liệu tương tự, nhưng khóa của map chính là không có thứ tự và không thể trùng lặp, nên cũng có thể sử dụng map để thay thế set.

func main() {
  set := make(map[int]struct{}, 10)
  for i := 0; i < 10; i++ {
    set[rand.Intn(100)] = struct{}{}
  }
  fmt.Println(set)
}

map[0:{} 18:{} 25:{} 40:{} 47:{} 56:{} 59:{} 81:{} 87:{}]

TIP

Một struct rỗng không chiếm bộ nhớ

Lưu ý

Map không phải là một cấu trúc dữ liệu an toàn đồng thời, nhóm Go cho rằng trong hầu hết các trường hợp việc sử dụng map không liên quan đến kịch bản đồng thời cao, việc giới thiệu khóa tương hỗ sẽ làm giảm đáng kể hiệu năng, bên trong map có cơ chế phát hiện đọc ghi, nếu xung đột sẽ kích hoạt fatal error. Ví dụ các trường hợp sau có khả năng rất lớn sẽ kích hoạt fatal.

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // Thao tác ghi
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // Thao tác đọc
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

Trong trường hợp này, cần sử dụng sync.Map để thay thế.