Go Map

本文将介绍 Go 中 Map，即键值对集合。

一、Map 创建

1
2
3
4
5
6
7
8
9
10
11
// 声明类型，不赋值
var myMap map[键类型]值类型

// 声明类型，赋值
var myMap map[键类型]值类型{
  键1: 值1
  ...
}

// 通过 make 函数
var myMap = make(map[键类型]值类型[, 容量])

需要注意的是：

  • 通过 make 函数：
    • 容量可以省略

二、Map 访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 获取值
var value = myMap[键]

// 设置值
myMap[键] = value

// 删除键值对
delete(myMap, 键)

// 获取键值对个数
var len = len(myMap)

// 遍历键值对
for k, v := range myMap{
	...
}

三、map 的底层结构

hmap 描述并维护 map，其中：

  • count：map 中元素个数

  • flags：定义了四个状态值，包括 iterator、oldIterator、hashWriting、sameSizeGrow

  • B：bucket 数量的以 2 为底的对数，即 2^B = bucket 数量

  • noverflow：overflow bucket 的大致数量

  • hash0：哈希函数的种子值

  • buckets：指向桶数组的指针

  • oldbuckets：扩容阶段中，指向旧桶数组的指针

  • nevacuate：扩容阶段中，充当扩容进度指示器，所有下标小于它的桶均已完成迁移

  • extra：可选子段

桶数组负责存储元素，它由若干个 bucket 组成。当往 map 中存取数据时，会使用哈希函数计算得到哈希值，哈希值的低位区用于选取 bucket，高位区用于在 bucket 中确定 key 的位置。

每个 bucket 由四个部分组成：

  • tophashs：通过哈希值的高位区和 tophashs，可以快速确定 key 的位置
  • keys：存储 key
  • values：存储 value
  • overflow：如果 bucket 已满，并且 map 未达到扩容条件，会建立 overflow bucket 并让 overflow 指向它

四、自动扩容机制

当 count > LoadFactor * bucket 数量 或 noverflow 较大时，会进行自动扩容。

参考