hello云胜

技术与生活

0%

发表于

map类型

声明

1
var myMap map[string]int // 一个map[string]int类型的变量

这个声明的myMap没有进行初始化，所以他的值是nil。对nil的map直接进行操作是报错的。

1
2
var myMap map[string]int
myMap["a"] = 1  // panic: assignment to entry in nil map

类似于java的npe

但是，上一章讲切片时，有这样的代码

1
2
var s []int
s= append(s, 100)

切片定义之后没有初始化，值也是nil。但是可以append。这种在 Go 语言中被称为“零值可用”。算是go对切片类型的一个语法糖。

但是map类型没有这种“零值可用”。

初始化

1
m := map[int]string{}

这样虽然该map没有任何键值对数据，但是m已经不是nil了。可以插值了。

1
2
3
4
m := map[int]string{
	1: "aaa",
	2: "bbb"
}

使用make函数

1
2
3
// 使用make函数可以指定初始化的map容量
	m2 := make(map[string]string, 10)
	t.Log(m2, len(m2))

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

map的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
m := map[int]string{}
// 插入
m[1] = "hello"
//获取
t.Log(m[1])
//长度
t.Log(len(m))
// 不能用cap查容量，和切片不一样
//t.Log(cap(m))
// 删除
delete(m, 1)

判断一个元素是否存在,举个例子

1
2
3
4
5
6
func TestExist(t *testing.T)  {
	m2 := map[string]int{}
	m2["aaa"] = 0
	t.Log(m2["aaa"])
	t.Log(m2["bbb"])
}

打印的结果都是0

也就是说对于不存在的key，返回的value是其类型的零值。所以说通过查询key的value是不是0，是无法判断key是否存在的。

这种情况下go有其标准写法

1
2
3
4
5
6
7
8
9
10
11
func TestExist(t *testing.T)  {
	m2 := map[string]int{}
	m2["aaa"] = 0
	v, ok := m2["bbb"]
	if ok {
		// 存在
		t.Log(v)
	} else {
		t.Log("不存在")
	}
}

遍历的坑

1
2
3
4
5
6
7
8
9
10
func TestMapFor(t *testing.T) {
	m1 := map[int]string{1: "a", 2: "b"}
	m1[3] = "c"
	for i := 0; i < 5; i++ {
		for k, v := range m1 {
			fmt.Printf("【%d, %s】", k, v)
		}
		fmt.Println()
	}
}

打印的结果

1
2
3
4
5
6
=== RUN   TestMapFor
【1, a】【2, b】【3, c】
【3, c】【1, a】【2, b】
【2, b】【3, c】【1, a】
【1, a】【2, b】【3, c】
【2, b】【3, c】【1, a】

也就是对map进行循环，每次的顺序都不一样。

程序逻辑千万不要依赖遍历 map 所得到的的元素顺序。

引用传递

map在函数调用时，传递的是引用。也就是函数内部的改变，会改变原始的数据。

底层实现

map的底层实例对应的是runtime.hmap实例。hmap也称为map类型的头部结构header，是一个map的描述符，保存了一个map类型的所有信息。

  • count，map的长度，len()返回的就是这个值

  • flags，当前map做出的状态标识。

  • B，B的值是bucket数量的以2为底的对数，也就是说2^B=bucket数量

  • noverflow，overflow的bucket的大约数量

  • hash0，哈希函数的种子值

  • buckets，指向bucket数组的指针

  • oldbuckets，在map扩容阶段指向旧的bucket数组的指针

  • nevacuate,扩容进度

map用来存储数据的是bucket数组。每个bucket默认的容量是8。如果8个slot全满了，又没有达到扩容的条件，就暂时创建overflow的bucket存储数据。

可以看到一个bucket分成三部分。tophash，key，value。

当像map中插入一个数据，或者获取数据时，对key进行哈希计算。对得到的hashcode一分为二。地位区用来选bucket。高位去用来确认在bucket中的位置。tophash存的就是这个位置。用来快速定位key，不需要对bucket中的key进行逐个比较。

接着下面就是key和value的存储区域，go将key和value分开存储，不是一个key一个value的方式存储。这样做的好处是减少了因为内存对齐带来的内存浪费。坏处是算法上更复杂。

还有一点要强调一下，如果 key 或 value 的数据长度大于一定数值，那么运 行时不会在 bucket 中直接存储数据，而是会存储 key 或 value 数据的指针。

扩容

map 在什么情况下会进行扩容呢？Go 运行时的 map 实现中引入了一个 LoadFactor（负载因子），

当 count > LoadFactor * bucket的数量 或 overflow bucket 过多 时，运行时会自动对 map 进行扩容。

目前 Go 最新 1.17 版本 LoadFactor 设置为 6.5。

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

如果是因为 overflow bucket 过多导致的“扩容”，实际上运行时会新建一个和现有规模一样的 bucket 数组， 然后在map的插入和删除时时做排空和迁移。

如果是因为当前数据数量超出 LoadFactor 指定水位而进行的扩容，那么运行时会建立一 个两倍于现有规模的 bucket 数组。数据的迁移并不会立即执行，而是等到map进行插入删除操作时，才会执行数据的迁移工作。

原 bucket 数组会挂在 hmap 的 oldbuckets 指针下面，直到原 buckets 数 组中所有数据都迁移到新数组后，原 buckets 数组才会被释放。

另外，因为动态迁移，value的地址会发生变化，所以go不需要获取value的地址

1
&m[key]  //不需要

并发安全

map 实例不是并发写安全的，也不支持并发读写

不过，如果我们仅仅是进行并发读，map 是没有问题的。而且，Go 1.9 版本中引入了支持 并发写安全的 sync.Map 类型，可以用来在并发读写的场景下替换掉 map