运维八一
lyndon
2022-06-07
目录

字典 map

# 8. 字典 map

# 8.1 map介绍

map 是一种无序的基于 key-value 的数据结构，map 中每个 key 都是唯一的。

img

# 8.2 定义map

Go 语言中 map 的定义语法如下：

==map[KeyType]ValueType==

  • KeyType：表示键的类型，key 的类型必须支持“==”和“!=”两种比较操作符。
  • ValueType：表示键对应的值的类型，map 类型对 value 的类型没有限制。

Go 语言中的 map 是引用类型，必须初始化才能使用。map 类型的变量默认初始值为 nil，需要使用 make()函数来分配内存。

切片变量和 map 变量在这里也有些不同。初值为零值 nil 的切片类型变量，可以借助内置的 append 的函数进行操作，这种在 Go 语言中被称为**“零值可用”**。

但 map 类型，因为它内部实现的复杂性，无法“零值可用”。所以，如果我们对处于零值状态的 map 变量直接进行操作，就会导致运行时异常（panic），从而导致程序进程异常退出：

var m map[string]int // m = nil
m["key"] = 1    // 发生运行时异常：panic: assignment to entry in nil map
1
2

和切片一样，为 map 类型变量显式赋值有两种方式：

  • 一种是使用复合字面值；
  • 另外一种是使用 make 这个预声明的内置函数。

# 8.2.1 方法一：使用复合字面值初始化 map 类型变量

// 作为初值的字面值采用了复合类型的元素类型，而且在编写字面值时还带上了各自的元素类型，比如作为 map[int] []string 值类型的[]string，以及作为 map[Position]string 的 key 类型的 Position。

m1 := map[int][]string{
    1: []string{"val1_1", "val1_2"},
    3: []string{"val3_1", "val3_2", "val3_3"},
    7: []string{"val7_1"},
}

type Position struct { 
    x float64 
    y float64
}

m2 := map[Position]string{
    Position{29.935523, 52.568915}: "school",
    Position{25.352594, 113.304361}: "shopping-mall",
    Position{73.224455, 111.804306}: "hospital",
}

// Go 提供了“语法糖”。这种情况下，Go 允许省略字面值中的元素类型。（推荐）
// m2 的初始化代码
m2 := map[Position]string{
    {29.935523, 52.568915}: "school",
    {25.352594, 113.304361}: "shopping-mall",
    {73.224455, 111.804306}: "hospital",
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 8.2.2 方法二：使用 make 为 map 类型变量进行显式初始化

和切片通过 make 进行初始化一样，通过 make 的初始化方式，我们可以为 map 类型变量指定键值对的初始容量，但无法进行具体的键值对赋值，

不过，map 类型的容量不会受限于它的初始容量值，当其中的键值对数量超过初始容量后，Go 运行时会自动增加 map 类型的容量，保证后续键值对的正常插入。

如下：

m1 := make(map[int]string) // 未指定初始容量
m2 := make(map[int]string, 8) // 指定初始容量为8
1
2

注意：获取 map 的容量不能使用 cap, cap 返回的是数组切片分配的空间大小, 不能用于map。要获取 map 的容量，可以用 len 函数。

package main

import "fmt"

func main() {
   userInfo := map[string]string{
      "username": "root",
      "password": "123456",
   }
   fmt.Println(userInfo) // map[password:123456 username:root]
}
1
2
3
4
5
6
7
8
9
10
11

在 Go 语言中，函数类型、map 类型自身，以及切片只支持与 nil 的比较，而不支持同类型两个变量的比较。

函数类型、map 类型自身，以及切片类型是不能作为 map 的 key 类型的。

如果像下面代码这样，进行这些类型的比较，Go 编译器将会报错：

s1 := make([]int, 1)
s2 := make([]int, 2)
f1 := func() {}
f2 := func() {}
m1 := make(map[int]string)
m2 := make(map[int]string)
println(s1 == s2) // 错误：invalid operation: s1 == s2 (slice can only be compared to nil)
println(f1 == f2) // 错误：invalid operation: f1 == f2 (func can only be compared to nil)
println(m1 == m2) // 错误：invalid operation: m1 == m2 (map can only be compared to nil)
1
2
3
4
5
6
7
8
9

# 8.3 map基本使用

# 8.3.1 查找和数据读取

和写入相比，map 类型更多用在查找和数据读取场合。所谓查找，就是判断某个 key 是否存在于某个 map 中。

m := make(map[string]int)
v := m["key1"]

// 通过以上还是无法确定键 key1 是否真实存在于 map 中。这是因为，当尝试去获取一个键对应的值的时候，如果这个键在 map 中并不存在，我们也会得到一个值，这个值是 value 元素类型的零值。
1
2
3
4

Go 语言的 map 类型支持通过用一种名为==“comma ok”==的惯用法，进行对某个 key 的查询。用“comma ok”惯用法改造一下上面的代码：

m := make(map[string]int)
v, ok := m["key1"]
if !ok {
    // "key1"不在map中
}

// "key1"在map中，v将被赋予"key1"键对应的value
1
2
3
4
5
6
7

如果我们并不关心某个键对应的 value，而只关心某个键是否在于 map 中，我们可以使用空标识符替代变量 v，忽略可能返回的 value：

m := make(map[string]int)
_, ok := m["key1"]
... ...
1
2
3

在 Go 语言中，请使用“comma ok”惯用法对 map 进行键查找和键值读取操作。

package main

import "fmt"

func main() {
   userInfo := map[string]string{
      "username": "zhangsan",
      "password": "123456",
   }
   v, ok := userInfo["username"]
   if ok {
      fmt.Println(v) 	// zhangsan
   } else {
      fmt.Println("map中没有此元素")
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 8.3.2 delete()函数

使用 delete()内建函数从 map 中删除一组键值对，delete()函数的格式如下：

==delete(map对象, key)==

  • map对象：表示要删除键值对的 map 对象
  • key：表示要删除的键值对的键
package main

import "fmt"

func main() {
   userInfo := map[string]string{
      "username": "zhangsan",
      "password": "123456",
   }
   delete(userInfo, "password") //将 password从 map 中删除
   fmt.Println(userInfo)        // map[username:zhangsan]
}
1
2
3
4
5
6
7
8
9
10
11
12

**delete 函数是从 map 中删除键的唯一方法。**即便传给 delete 的键在 map 中并不存在，delete 函数的执行也不会失败，更不会抛出运行时的异常。

m := map[string]int {
  "key1" : 1,
  "key2" : 2,
}

fmt.Println(m) // map[key1:1 key2:2]
delete(m, "key2") // 删除"key2"
fmt.Println(m) // map[key1:1]
1
2
3
4
5
6
7
8

# 8.3.3 插入新键值对

插入新键值对的方式很简单，只需要把 value 赋值给 map 中对应的 key 就可以了，如下：

m := make(map[int]string)
m[1] = "value1"
m[2] = "value2"
m[3] = "value3"
1
2
3
4

如果我们插入新键值对的时候，某个 key 已经存在于 map 中了，那我们的插入操作就会用新值覆盖旧值：

m := map[string]int {
  "key1" : 1,
  "key2" : 2,
}

m["key1"] = 11 // 11会覆盖掉"key1"对应的旧值1
m["key3"] = 3  // 此时m为map[key1:11 key2:2 key3:3]
1
2
3
4
5
6
7

# 8.3.4 获取键值对数量

map 类型可以通过内置函数 len，获取当前变量已经存储的键值对数量：

m := map[string]int {
  "key1" : 1,
  "key2" : 2,
}

fmt.Println(len(m)) // 2
m["key3"] = 3  
fmt.Println(len(m)) // 3
1
2
3
4
5
6
7
8

不能对 map 类型变量调用 cap，来获取当前容量。

# 8.4 map遍历

在 Go 中，遍历 map 的键值对只有一种方法，那就是像对待切片那样通过 for range 语句对 map 数据进行遍历。

package main

import "fmt"

func main() {
    m := map[int]int{
        1: 11,
        2: 12,
        3: 13,
    }

    fmt.Printf("{ ")
    for k, v := range m {
        fmt.Printf("[%d, %d] ", k, v)
    }
    fmt.Printf("}\n")

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

**对同一 map 做多次遍历的时候，每次遍历元素的次序都不相同。**这是 Go 语言 map 类型的一个重要特点，也是很容易让 Go 初学者掉入坑中的一个地方。

所以这里一定要记住：程序逻辑千万不要依赖遍历 map 所得到的的元素次序。

# 8.4.1 遍历key和value

package main

import "fmt"

func main() {
   scoreMap := map[string]int{
      "zhangsan": 24,
      "lisi":     26,
      "wangwu":   24,
   }
   for k, v := range scoreMap {
      fmt.Println(k, v)
   }
}

/*
zhangsan 24
lisi 26
wangwu 24
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 8.4.2 只遍历key

注意： 遍历 map 时的元素顺序与添加键值对的顺序无关

package main

import "fmt"

func main() {
   scoreMap := map[string]int{
      "zhangsan": 24,
      "lisi":     26,
      "wangwu":   24,
   }
   for k := range scoreMap {
      fmt.Println(k)
   }
}

/*
zhangsan
lisi
wangwu
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 8.4.3 只遍历value

package main

import "fmt"

func main() {
   scoreMap := map[string]int{
      "zhangsan": 24,
      "lisi":     26,
      "wangwu":   24,
   }
   for _, v := range scoreMap {
      fmt.Println(v)
   }
}

/*
24
26
24
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 8.5 map变量的传递开销

和切片类型一样，map 也是引用类型。这就意味着 map 类型变量作为参数被传递给函数或方法的时候，实质上传递的只是一个**“描述符”**，而不是整个 map 的数据拷贝，所以这个传递的开销是固定的，而且也很小。

并且，当 map 变量被传递到函数或方法内部后，在函数内部对 map 类型参数的修改在函数外部也是可见的。

// 函数 foo 中对 map 类型变量 m 进行了修改，而这些修改在 foo 函数外也可见。

package main

import "fmt"

func foo(m map[string]int) {
    m["key1"] = 11
    m["key2"] = 12
}

func main() {
    m := map[string]int{
        "key1": 1,
        "key2": 2,
    }

    fmt.Println(m) // map[key1:1 key2:2]  
    foo(m)
    fmt.Println(m) // map[key1:11 key2:12] 

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 8.6 map的内部实现

和切片相比，map 类型的内部实现要更加复杂。

Go 运行时使用一张哈希表来实现抽象的 map 类型。运行时实现了 map 类型操作的所有功能，包括查找、插入、删除等。在编译阶段，Go 编译器会将 Go 语法层面的 map 操作，重写成运行时对应的函数调用。

大致的对应关系是这样的：

// 创建map类型变量实例
m := make(map[keyType]valType, capacityhint) → m := runtime.makemap(maptype, capacityhint, m)

// 插入新键值对或给键重新赋值
m["key"] = "value" → v := runtime.mapassign(maptype, m, "key") v是用于后续存储value的空间的地址

// 获取某键的值 
v := m["key"]      → v := runtime.mapaccess1(maptype, m, "key")
v, ok := m["key"]  → v, ok := runtime.mapaccess2(maptype, m, "key")

// 删除某键
delete(m, "key")   → runtime.mapdelete(maptype, m, “key”)
1
2
3
4
5
6
7
8
9
10
11
12

map 类型在 Go 运行时层实现的示意图：

img

初始状态

与语法层面 map 类型变量（m）一一对应的是 *runtime.hmap 的实例，即 runtime.hmap 类型的指针，也就是我们前面在讲解 map 类型变量传递开销时提到的 map 类型的描述符。hmap 类型是 map 类型的头部结构（header），它存储了后续 map 类型操作所需的所有信息，包括：

img

真正用来存储键值对数据的是桶，也就是 bucket，每个 bucket 中存储的是 Hash 值低 bit 位数值相同的元素，默认的元素个数为 BUCKETSIZE（值为 8，Go 1.17 版本中在 $GOROOT/src/cmd/compile/internal/reflectdata/reflect.go 中定义，与 runtime/map.go 中常量 bucketCnt 保持一致）。

当某个 bucket（比如 buckets[0]) 的 8 个空槽 slot）都填满了，且 map 尚未达到扩容的条件的情况下，运行时会建立 overflow bucket，并将这个 overflow bucket 挂在上面 bucket（如 buckets[0]）末尾的 overflow 指针上，这样两个 buckets 形成了一个链表结构，直到下一次 map 扩容之前，这个结构都会一直存在。

从图中我们可以看到，每个 bucket 由三部分组成，从上到下分别是 tophash 区域、key 存储区域和 value 存储区域。

tophash 区域

当我们向 map 插入一条数据，或者是从 map 按 key 查询数据的时候，运行时都会使用哈希函数对 key 做哈希运算，并获得一个哈希值（hashcode）。

这个 hashcode 非常关键，运行时会把 hashcode“一分为二”来看待，其中低位区的值用于选定 bucket，高位区的值用于在某个 bucket 中确定 key 的位置。

img

因此，每个 bucket 的 tophash 区域其实是用来快速定位 key 位置的，这样就避免了逐个 key 进行比较这种代价较大的操作。尤其是当 key 是 size 较大的字符串类型时，好处就更突出了。这是一种以空间换时间的思路。

key 存储区域

存储的是这个 bucket 承载的所有 key 数据。运行时在分配 bucket 的时候需要知道 key 的 Size。

当我们声明一个 map 类型变量，比如 var m map[string]int 时，Go 运行时就会为这个变量对应的特定 map 类型，生成一个 runtime.maptype 实例。如果这个实例已经存在，就会直接复用。maptype 实例的结构是这样的：

// 这个maptype 实例包含了我们需要的 map 类型中的所有"元信息"。
type maptype struct {
    typ        _type
    key        *_type
    elem       *_type
    bucket     *_type // internal type representing a hash bucket
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}
1
2
3
4
5
6
7
8
9
10
11

编译器会把语法层面的 map 操作重写成运行时对应的函数调用，这些运行时函数都有一个共同的特点，那就是第一个参数都是 maptype 指针类型的参数。

**Go 运行时就是利用 maptype 参数中的信息确定 key 的类型和大小的。**map 所用的 hash 函数也存放在 maptype.key.alg.hash(key, hmap.hash0) 中。同时 maptype 的存在也让 Go 中所有 map 类型都共享一套运行时 map 操作函数，而不是像 C++ 那样为每种 map 类型创建一套 map 操作函数，这样就节省了对最终二进制文件空间的占用。

value 存储区域

存储的是 key 对应的 value。Go 运行时采用了把 key 和 value 分开存储的方式，而不是采用一个 kv 接着一个 kv 的 kv 紧邻方式存储，这带来的其实是算法上的复杂性，但却减少了因内存对齐带来的内存浪费。

以 map[int8]int64 为例，看看下面的存储空间利用率对比图：

img

Go 运行时使用的方案内存利用效率很高，而 kv 紧邻存储的方案在 map[int8]int64 这样的例子中内存浪费十分严重，它的内存利用率是 72/128=56.25%，有近一半的空间都浪费掉了。

注意：

如果 key 或 value 的数据长度大于一定数值，那么运行时不会在 bucket 中直接存储数据，而是会存储 key 或 value 数据的指针。目前 Go 运行时定义的最大 key 和 value 的长度是这样的：

// $GOROOT/src/runtime/map.go
const (
    maxKeySize  = 128
    maxElemSize = 128
)
1
2
3
4
5

# 8.7 map扩容

map 会对底层使用的内存进行自动管理。因此，在使用过程中，当插入元素个数超出一定数值后，map 会自动扩容。

map 在什么情况下会进行扩容呢？

Go 运行时的 map 实现中引入了一个 LoadFactor（负载因子），当 ==count > LoadFactor * 2^B== 或 ==overflow bucket 过多==时，运行时会自动对 map 进行扩容。

目前 Go 最新 1.17 版本 LoadFactor 设置为 6.5（loadFactorNum/loadFactorDen）。这里是 Go 中与 map 扩容相关的部分源码：

// $GOROOT/src/runtime/map.go
const (
  ... ...

  loadFactorNum = 13
  loadFactorDen = 2
  ... ...
)

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  ... ...
  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again // Growing the table invalidates everything, so try again
  }
  ... ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这两方面原因导致的扩容，在运行时的操作其实是不一样的。

  • **overflow bucket 过多：**实际上运行时会新建一个和现有规模一样的 bucket 数组，然后在 assign 和 delete 时做排空和迁移。
  • **超出 LoadFactor 指定水位：**运行时会建立一个两倍于现有规模的 bucket 数组，但真正的排空和迁移工作也是在 assign 和 delete 时逐步进行的。原 bucket 数组会挂在 hmap 的 oldbuckets 指针下面，直到原 buckets 数组中所有数据都迁移到新数组后，原 buckets 数组才会被释放。

img

# 8.8 map 与并发

从实现原理来看，充当 map 描述符角色的 hmap 实例自身是有状态的（hmap.flags），而且对状态的读写是没有并发保护的。所以说 map 实例不是并发写安全的，也不支持并发读写。

如果我们对 map 实例进行并发读写，程序运行时就会抛出异常。并发读写 map 的例子：

package main

import (
    "fmt"
    "time"
)

func doIteration(m map[int]int) {
    for k, v := range m {
        _ = fmt.Sprintf("[%d, %d] ", k, v)
    }
}

func doWrite(m map[int]int) {
    for k, v := range m {
        m[k] = v + 1
    }
}

func main() {
    m := map[int]int{
        1: 11,
        2: 12,
        3: 13,
    }

    go func() {
        for i := 0; i < 1000; i++ {
            doIteration(m)
        }
    }()
    
    go func() {
        for i := 0; i < 1000; i++ {
            doWrite(m)
        }
    }()
    
    time.Sleep(5 * time.Second)

}


// 得到执行错误结果：fatal error: concurrent map iteration and map write
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

不过，如果仅仅是进行并发读，map 是没有问题的。而且，Go 1.9 版本中引入了支持并发写安全的 ==sync.Map== 类型，可以用来在并发读写的场景下替换掉 map，如果你有这方面的需求，可以查看一下sync.Map 的手册 (opens new window)。

上次更新: 2022/06/12, 15:48:09
切片 sice
指针

← 指针→

最近更新
01
ctr和crictl显示镜像不一致
03-13
02
alpine镜像集成常用数据库客户端
03-13
03
create-cluster
02-26
更多文章>
Theme by Vdoing | Copyright © 2015-2024 op81.com
苏ICP备18041258号-2