Go语言Map

hmap_1.png

map 的设计也被称为 “The dictionary problem”，它的任务是设计一种数据结构用来维护一个集合的数据，并且可以同时对集合进行增删查改的操作

Go里的map用于存放key/value对，在其它地方常称为hash、dictionary、关联数组，这几种称呼都是对同一种数据结构的不同称呼，它们都用于将key经过hash函数处理，然后映射到value，实现一一对应的关系

映射是存储一系列无序的 key/value 对，通过 key 来对 value 进行操作（增、删、改、查）。

声明与初始化

1.声明

map 声明需要指定组成元素 key 和 value 的类型，在声明后，会被初始化为 nil，表示
暂不存在的映射

  1. var m map[string]int // *hmap
  2. fmt.Printf("%p\n", m)

2.初始化

可以通过make()创建map，它会先创建好底层数据结构，然后再创建map，并让map指向底层数据结构。

  1. var m map[string]int
  2. m = make(map[string]int)
  3. fmt.Printf("%p\n", m)

3.声明并初始化

也可以直接通过大括号创建并初始化赋值

  1. m := map[string]int{"Tony": 22, "Andy": 55}
  2. fmt.Println(m)

4.限制

Go 语言中只要是可比较的类型都可以作为 key。除开 slice，map，functions 这几种类型，其他类型都是 OK 的。
具体包括：布尔值、数字、字符串、指针、通道、接口类型、结构体、只包含上述类型的数组。
这些类型的共同特征是支持 == 和 != 操作符，k1 == k2 时，可认为 k1 和 k2 是同一个 key。
如果是结构体，则需要它们的字段值都相等，才被认为是相同的 key

  1. var m1 map[string]string
  2. var m2 map[int]int
  3. var m3 map[float64]string
  4. var m4 map[string]AddFunc

nil map和空map

空map是不做任何赋值的map：

  1. a := map[int]string

nil map，它将不会做任何初始化，不会指向任何数据结构：

  1. var a map[int]string

如何map没初始化，直接赋值会报空指针

  1. var a map[int]string
  2. var b []string
  3. fmt.Printf("%p, %p\n", a, b)
  4. // a[0] = "a"
  5. // b[0] = "a"
  7. a = map[int]string{0: "a"}
  8. b = []string{"a"}
  9. fmt.Printf("%p, %p\n", a, b)

所以，map类型实际上就是一个指针, 具体为 *hmap

元素访问

1.访问key的值, 格式 key_value = map_var[key_value]

检索map中key对应的value值。如果key不存在，则value返回值对应数据类型的0。例如int为数值0，布尔为false，字符串为空””

  1. a := map[int]string{}
  2. fmt.Println(a[0])

2.判断key是否存在, 格式: key_value, is_exist = map_var[key_value]

当key存在时，value为对应的值，is_exist为true；当key不存在，value为0(同样是各数据类型所代表的0)，is_exist为false。

  1. a := map[int]string{}
  2. fmt.Println(a[0])
  4. a[100] = "t1"
  5. v1, ok1 := a[100]
  6. fmt.Println(ok1, v1)
  7. v2, ok2 := a[0]
  8. fmt.Println(ok2, v2)

3.测试map中元素是否存在

  1. a[100] = "t1"
  2. if v, ok := a[100]; ok {
  3.     fmt.Println(v)
  4. }

元素删除

通过使用delete内置函数 用删除map中的元素

  1. a := map[int]string{100: "t1"}
  2. delete(a, 100)
  3. fmt.Println(a)

注意: 删除不存在的元素, 是不会有任何保存, 如果需要判断key是否存在，请自己判断

  1. a := map[int]string{100: "t1"}
  2. delete(a, 99)

len

len()函数用于获取map中元素的个数，即有多个少key。delete()用于删除map中的某个key

元素迭代

因为map是key/value类型的数据结构，key就是map的index，所以range关键字对map操作时，将返回key和value

1.迭代key和value

2.只迭代key

map作为函数参数

map是一种指针，所以将map传递给函数，仅仅只是复制这个指针，所以函数内部对map的操作会直接修改外部的map

  1. a := map[int]string{1: "a", 2: "b", 3: "c"}
  3. func(map[int]string) {
  4.     delete(a, 1)
  5. }(a)
  7. fmt.Println(a)

map值为函数

  1. op := map[string]func(x, y int) int{
  2.     "+": func(x, y int) int {
  3.         return x + y
  4.     },
  5.     "-": func(x, y int) int {
  6.         return x - y
  7.     },
  8.     "*": func(x, y int) int {
  9.         return x * y
  10.     },
  11.     "/": func(x, y int) int {
  12.         return x / y
  13.     },
  14. }
  16. fmt.Println(op["+"](1, 2))
  17. fmt.Println(op["-"](1, 2))

扩展

以下为Go Map源码相关解读, 源码位置: src/runtime/map.go,

更详细的内容可以参考 曹大的笔记: map

内存模型

源码中，表示 map 的结构体是 hmap，它是 hashmap 的“缩写”

  1. // A header for a Go map.
  2. type hmap struct {
  3.     // 元素个数，调用 len(map) 时，直接返回此值
  4.     count     int
  5.     flags     uint8
  6.     // buckets 的对数 log_2
  7.     B         uint8
  8.     // overflow 的 bucket 近似数
  9.     noverflow uint16
  10.     // 计算 key 的哈希的时候会传入哈希函数
  11.     hash0     uint32
  12.     // 指向 buckets 数组，大小为 2^B
  13.     // 如果元素个数为0，就为 nil
  14.     buckets    unsafe.Pointer
  15.     // 扩容的时候，buckets 长度会是 oldbuckets 的两倍
  16.     oldbuckets unsafe.Pointer
  17.     // 指示扩容进度，小于此地址的 buckets 迁移完成
  18.     nevacuate  uintptr
  19.     extra *mapextra // optional fields
  20. }

该结构中用于存储key value的数据结构是 buckets([]bmap), 其中bmap就是我们常说的“桶”，桶里面最多装 8 个元素(key-value)

如果有第 9 个 元素 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来

下面是一张全局图

hmap.png

创建过程

  1. m1 := make(map[string]int)
  2. // 指定 map 长度
  3. m2 := make(map[string]int, 8)

我们可以看到创建的核心是 根据用户提供的map大小，计算出需要初始化的bucket, 计算bucket数量的核心指标是 装载因子

装载因子：用于衡量bucket的装载情况, 计算公式: loadFactor := count / (2^B)

  • count: map 的元素个数
  • 2^B ：bucket 数量

装载因子超过阈值，源码里定义的阈值是 6.5, 就需要分配一个扩展了(B++), 一次计算逻辑: count / 2^B < 6.5

  1. // loadFactorNum 13
  2. // overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
  3. func overLoadFactor(count int, B uint8) bool {
  4.     return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
  5. }

下面是makemap的具体过程:

  1. func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
  2.     // 省略各种条件检查...
  4.     // 找到一个 B，使得 map 的装载因子在正常范围内
  5.     B := uint8(0)
  6.     for ; overLoadFactor(hint, B); B++ {
  7.     }
  9.     // 初始化 hash table
  10.     // 如果 B 等于 0，那么 buckets 就会在赋值的时候再分配
  11.     // 如果长度比较大，分配内存会花费长一点
  12.     buckets := bucket
  13.     var extra *mapextra
  14.     if B != 0 {
  15.         var nextOverflow *bmap
  16.         buckets, nextOverflow = makeBucketArray(t, B)
  17.         if nextOverflow != nil {
  18.             extra = new(mapextra)
  19.             extra.nextOverflow = nextOverflow
  20.         }
  21.     }
  23.     // 初始化 hamp
  24.     if h == nil {
  25.         h = (*hmap)(newobject(t.hmap))
  26.     }
  27.     h.count = 0
  28.     h.B = B
  29.     h.extra = extra
  30.     h.flags = 0
  31.     h.hash0 = fastrand()
  32.     h.buckets = buckets
  33.     h.oldbuckets = nil
  34.     h.nevacuate = 0
  35.     h.noverflow = 0
  37.     return h
  38. }

元素存取过程

key 经过哈希计算后得到哈希值，共 64 个 bit 位, 然后通过这个hash来决定我们元素放那个桶的那个槽

  • bucket编号: 用最后的5个bit位作为bucket的编号
  • key放置槽: 用哈希值的高 8 位(top hash)标识存放的槽的位置, 最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入

map_op.png

如何进行扩容

1.触发条件

在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容

  • 装载因子超过阈值，源码里定义的阈值是 6.5，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的
  • overflow 的 bucket 数量过多，即 map 里元素总数少，但是 bucket 数量多，导致 key 会很分散，查找插入效率都变低了, 这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难
    • 当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B
    • 当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15

2.扩容策略:

  • 装载因子超过阈值的扩容策略:将 B 加 1，bucket 最大数量（2^B）直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。而且，新 bucket 只是最大数量变为原来最大数量（2^B）的 2 倍（2^B * 2）
  • overflow 的 bucket 数量过多扩展策略: 开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密, 这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升

3.元素搬迁

经过上面的扩容， 但是元素并没有迁移

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”地方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket

因此搬迁时(插入或修改、删除 key 的时候), 都会尝试进行搬迁 buckets 的工作, 根据bucketmask, 进行重新hash, 然后再次均衡
所谓的 bucketmask，作用就是将 key 计算出来的哈希值与 bucketmask 相与，得到的结果就是 key 应该落入的桶。比如 B = 5，那么 bucketmask 的低 5 位是 11111，其余位是 0，hash 值与其相与的意思是，只有 hash 值的低 5 位决策 key 到底落入哪个 bucket