Go映射表

一般來說，映射表數據結構實現通常有兩種，哈希表(hash table)和搜索樹(search tree)，區別在於前者無序，後者有序。在 Go 中，map的實現是基於哈希桶(也是一種哈希表)，所以也是無序的，本篇不會對實現原理做過多的講解，這超出了基礎的范圍，後續會進行深入分析。

TIP

想要了解 map 的原理可以前往map 實現

初始化

在 Go 中，map 的鍵類型必須是可比較的，比如string ，int是可比較的，而[]int是不可比較的，也就無法作為 map 的鍵。初始化一個 map 有兩種方法，第一種是字面量，格式如下：

map[keyType]valueType{}

舉幾個例子

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

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

第二種方法是使用內置函數make，對於 map 而言，接收兩個參數，分別是類型與初始容量，例子如下：

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

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

map 是引用類型，零值或未初始化的 map 可以訪問，但是無法存放元素，所以必須要為其分配內存。

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

panic: assignment to entry in nil map

TIP

在初始化 map 時應當盡量分配一個合理的容量，以減少擴容次數。

訪問

訪問一個 map 的方式就像通過索引訪問一個數組一樣。

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

通過代碼可以觀察到，即使 map 中不存在"f"這一鍵值對，但依舊有返回值。map 對於不存的鍵其返回值是對應類型的零值，並且在訪問 map 的時候其實有兩個返回值，第一個返回值對應類型的值，第二個返回值一個布爾值，代表鍵是否存在，例如：

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("key不存在")
   }
}

對 map 求長度

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

存值

map 存值的方式也類似數組存值一樣，例如：

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

存值時使用已存在的鍵會覆蓋原有的值

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

但是也存在一個特殊情況，那就是鍵為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]

通過結果可以觀察到相同的鍵值並沒有覆蓋，反而還可以存在多個，也無法判斷其是否存在，也就無法正常取值。因為 NaN 是 IEE754 標准所定義的，其實現是由底層的匯編指令UCOMISD完成，這是一個無序比較雙精度浮點數的指令，該指令會考慮到 NaN 的情況，因此結果就是任何數字都不等於 NaN，NaN 也不等於自身，這也造成了每次哈希值都不相同。關於這一點社區也曾激烈討論過，但是官方認為沒有必要去修改，所以應當盡量避免使用 NaN 作為 map 的鍵。

刪除

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

刪除一個鍵值對需要用到內置函數delete，例如

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]

需要注意的是，如果值為 NaN，甚至沒法刪除該鍵值對。

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]

遍歷

通過for range可以遍歷 map，例如

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

可以看到結果並不是有序的，也印證了 map 是無序存儲。值得一提的是，NaN 雖然沒法正常獲取，但是可以通過遍歷訪問到，例如

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

清空

在 go1.21 之前，想要清空 map，就只能對每一個 map 的 key 進行 delete

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

但是 go1.21 更新了 clear 函數，就不用再進行之前的操作了，只需要一個 clear 就可以清空

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

輸出

map[]

Set

Set 是一種無序的，不包含重復元素的集合，Go 中並沒有提供類似的數據結構實現，但是 map 的鍵正是無序且不能重復的，所以也可以使用 map 來替代 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

一個空的結構體不會佔用內存

注意

map 並不是一個並發安全的數據結構，Go 團隊認為大多數情況下 map 的使用並不涉及高並發的場景，引入互斥鎖會極大的降低性能，map 內部有讀寫檢測機制，如果沖突會觸發fatal error。例如下列情況有非常大的可能性會觸發fatal。

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // 寫操作
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // 讀操作
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

在這種情況下，需要使用sync.Map來替代。