聊一聊 map

map 是 go 中一个重要的数据结构, 可以通过 map 存储键值对「key-value」, 可以在常数时间内实现对 key 的查找。

使用

可以使用以下方式声明一个 map。

m, m1 := make(map[string]int), make(map[string]int, 8) // 分配默认空间 & 指定空间
var m2 map[string]int                                  // 并未创建空间
fmt.Println(m == nil, m1 == nil, m2 == nil)            // false false true

对于未分配空间 map 可以进行查找、删除操作, 但不能进行添加操作

var m map[int]int
fmt.Println(m[1]) // 0
delete(m, 1)
m[0] = 0
// panic: assignment to entry in nil map

对于 map 的查找, 如果不存在也会返回零值, 可以通过下面的方式判断 map 中是否包含了指定的 key

m := map[int]int{
   1: 1,
}
fmt.Println(m[0]) // 0
if _, ok := m[0]; !ok {
   fmt.Println("not contain key: 0")
}

map 传参, 可以将 map 看作指向一块空间的指针。因此, 当参数传递时, 会修改指向的内容

func main() {
    m := map[int]int{}
    paramMap(m)
    fmt.Println(m) // 输出更新之后的值
}

func paramMap(m map[int]int) {
   for i := 0; i < 100; i++ {
      m[i] = i
   }
}

map 的遍历并不保证有序, 官方说法是：为了 runtime 能够不断对 map 进行优化, 不能保证 map 遍历的结果是有序的。

func rMap(m map[string]int) {
   for k, v := range m {
      fmt.Println(k, ":", v)
   }
}

map 并不是并发安全, 多个 goroutine 并发写 map 会导致 panic。主要还是出于性能的考虑, 如果将 map 设计为并发安全的, 将大大损失程序的性能。如果是并发场景可以使用 sync.Map

func wMap(m map[string]int) {
   for _, v := range []string{"4", "5", "6"} {
      m[v] = 9
   }
}

// BenchmarkWMap-12     fatal error: concurrent map writes
func BenchmarkWMap(b *testing.B) {
   m := make(map[string]int)
   wg := sync.WaitGroup{}
   for i := 0; i < b.N; i++ {
      wg.Add(1)
      go func() {
         defer func() {
            wg.Done()
         }()
         wMap(m)
      }()
   }
   wg.Wait()
}

实现

map 本质上就是一个 hash table。将 key 使用一个 hash 函数映射到指定的位置, 如果发生 hash 冲突, 通常使用开放寻址法、拉链法解决。在 go 中使用拉链法解决 hash 冲突。能力有限, 不做源码解读了, 这里抛一些点。

• 插入的时候会先通过 hash(key) 确定 key 所属于的 bucket, 一个 bucket 默认存储 8 个键值对, 当插入溢出时会使用链表追加
• 当负载因子过高「数据元素过多, 防止查找复杂度劣化到 o(n)」或过低「频繁的插入删除导致 bucket 溢出链表过长」时都会触发 map 的扩容操作「翻倍扩容、等容量扩容」. 为了防止一次性扩容导致大量的数据搬迁, go 使用渐进式扩容, 只有在发生插入和删除操作的时候搬迁两个 bucket.

总结

• 在使用 map 的时候, 如果明确知道所需要存储的数据量, 可以指定容量创建 map, 减少扩容操作。
• map 在底层实现的时候, 本质上还是通过数组+链表存储数据, 极端情况下性能会劣化到 o(n). 在 go 中, 使用分桶、渐进扩容的方式来保证 map 有尽可能好的性能。