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来替代。