运维八一
lyndon
2022-06-07
4.2k
17.7m
29
目录
8. 字典 map
8.1 map介绍
8.2 定义map
8.2.1 方法一：使用复合字面值初始化 map 类型变量
8.2.2 方法二：使用 make 为 map 类型变量进行显式初始化
8.3 map基本使用
8.3.1 查找和数据读取
8.3.2 delete()函数
8.3.3 插入新键值对
8.3.4 获取键值对数量
8.4 map遍历
8.4.1 遍历key和value
8.4.2 只遍历key
8.4.3 只遍历value
8.5 map变量的传递开销
8.6 map的内部实现
8.7 map扩容
8.8 map 与并发

字典 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-2025 op81.com
苏ICP备18041258号-2

下午好呀~~，现在是 16:03:00，繁忙的下午也要适当休息哦🥤🏀~~