极客时间已完结课程限时免费阅读

16｜复合数据类型：原生map类型的实现机制是怎样的？

16｜复合数据类型：原生map类型的实现机制是怎样的？-极客时间

16｜复合数据类型：原生map类型的实现机制是怎样的？

2021-11-17 Tony Bai 来自北京
《Tony Bai · Go语言第一课》
课程介绍

讲述：Tony Bai

时长22:57大小20.97M

你好，我是 Tony Bai。
上一节课，我们学习了 Go 语言中最常用的两个复合类型：数组与切片。它们代表一组连续存储的同构类型元素集合。不同的是，数组的长度是确定的，而切片，我们可以理解为一种“动态数组”，它的长度在运行时是可变的。
这一节课，我们会继续前面的脉络，学习另外一种日常 Go 编码中比较常用的复合类型，这种类型可以让你将一个值（Value）唯一关联到一个特定的键（Key）上，可以用于实现特定键值的快速查找与更新，这个复合数据类型就是 map。很多中文 Go 编程语言类技术书籍都会将它翻译为映射、哈希表或字典，但在我的课程中，为了保持原汁原味，我就直接使用它的英文名，map。
map 是我们继切片之后，学到的第二个由 Go 编译器与运行时联合实现的复合数据类型，它有着复杂的内部实现，但却提供了十分简单友好的开发者使用接口。这一节课，我将从 map 类型的定义，到它的使用，再到 map 内部实现机制，由浅到深地让你吃透 map 类型。

什么是 map 类型？

map 是 Go 语言提供的一种抽象数据类型，它表示一组无序的键值对。在后面的讲解中，我们会直接使用 key 和 value 分别代表 map 的键和值。而且，map 集合中每个 key 都是唯一的：
和切片类似，作为复合类型的 map，它在 Go 中的类型表示也是由 key 类型与 value 类型组成的，就像下面代码：
map[key_type]value_type
key 与 value 的类型可以相同，也可以不同：
map[string]string // key与value元素的类型相同
map[int]string // key与value元素的类型不同
如果两个 map 类型的 key 元素类型相同，value 元素类型也相同，那么我们可以说它们是同一个 map 类型，否则就是不同的 map 类型。
这里，我们要注意，map 类型对 value 的类型没有限制，但是对 key 的类型却有严格要求，因为 map 类型要保证 key 的唯一性。Go 语言中要求，key 的类型必须支持“==”和“!=”两种比较操作符。
但是，在 Go 语言中，函数类型、map 类型自身，以及切片只支持与 nil 的比较，而不支持同类型两个变量的比较。如果像下面代码这样，进行这些类型的比较，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)
因此在这里，你一定要注意：函数类型、map 类型自身，以及切片类型是不能作为 map 的 key 类型的。
知道如何表示一个 map 类型后，接下来，我们来看看如何声明和初始化一个 map 类型的变量。

map 变量的声明和初始化

我们可以这样声明一个 map 变量：
var m map[string]int // 一个map[string]int类型的变量
和切片类型变量一样，如果我们没有显式地赋予 map 变量初值，map 类型变量的默认值为 nil。
不过切片变量和 map 变量在这里也有些不同。初值为零值 nil 的切片类型变量，可以借助内置的 append 的函数进行操作，这种在 Go 语言中被称为“零值可用”。定义“零值可用”的类型，可以提升我们开发者的使用体验，我们不用再担心变量的初始状态是否有效。
但 map 类型，因为它内部实现的复杂性，无法“零值可用”。所以，如果我们对处于零值状态的 map 变量直接进行操作，就会导致运行时异常（panic），从而导致程序进程异常退出：
var m map[string]int // m = nil
m["key"] = 1 // 发生运行时异常：panic: assignment to entry in nil map
所以，我们必须对 map 类型变量进行显式初始化后才能使用。那我们怎样对 map 类型变量进行初始化呢？
和切片一样，为 map 类型变量显式赋值有两种方式：一种是使用复合字面值；另外一种是使用 make 这个预声明的内置函数。
方法一：使用复合字面值初始化 map 类型变量。
我们先来看这句代码：
m := map[int]string{}
这里，我们显式初始化了 map 类型变量 m。不过，你要注意，虽然此时 map 类型变量 m 中没有任何键值对，但变量 m 也不等同于初值为 nil 的 map 变量。这个时候，我们对 m 进行键值对的插入操作，不会引发运行时异常。
这里我们再看看怎么通过稍微复杂一些的复合字面值，对 map 类型变量进行初始化：
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",
}
我们看到，上面代码虽然完成了对两个 map 类型变量 m1 和 m2 的显式初始化，但不知道你有没有发现一个问题，作为初值的字面值似乎有些“臃肿”。你看，作为初值的字面值采用了复合类型的元素类型，而且在编写字面值时还带上了各自的元素类型，比如作为 map[int] []string 值类型的[]string，以及作为 map[Position]string 的 key 类型的 Position。
别急！针对这种情况，Go 提供了“语法糖”。这种情况下，Go 允许省略字面值中的元素类型。因为 map 类型表示中包含了 key 和 value 的元素类型，Go 编译器已经有足够的信息，来推导出字面值中各个值的类型了。我们以 m2 为例，这里的显式初始化代码和上面变量 m2 的初始化代码是等价的：
m2 := map[Position]string{
{29.935523, 52.568915}: "school",
{25.352594, 113.304361}: "shopping-mall",
{73.224455, 111.804306}: "hospital",
}
以后在无特殊说明的情况下，我们都将使用这种简化后的字面值初始化方式。
方法二：使用 make 为 map 类型变量进行显式初始化。
和切片通过 make 进行初始化一样，通过 make 的初始化方式，我们可以为 map 类型变量指定键值对的初始容量，但无法进行具体的键值对赋值，就像下面代码这样：
m1 := make(map[int]string) // 未指定初始容量
m2 := make(map[int]string, 8) // 指定初始容量为8
不过，map 类型的容量不会受限于它的初始容量值，当其中的键值对数量超过初始容量后，Go 运行时会自动增加 map 类型的容量，保证后续键值对的正常插入。
了解完 map 类型变量的声明与初始化后，我们就来看看，在日常开发中，map 类型都有哪些基本操作和注意事项。

map 的基本操作

针对一个 map 类型变量，我们可以进行诸如插入新键值对、获取当前键值对数量、查找特定键和读取对应值、删除键值对，以及遍历键值等操作。我们一个个来学习。
操作一：插入新键值对。
面对一个非 nil 的 map 类型变量，我们可以在其中插入符合 map 类型定义的任意新键值对。插入新键值对的方式很简单，我们只需要把 value 赋值给 map 中对应的 key 就可以了：
m := make(map[int]string)
m[1] = "value1"
m[2] = "value2"
m[3] = "value3"
而且，我们不需要自己判断数据有没有插入成功，因为 Go 会保证插入总是成功的。这里，Go 运行时会负责 map 变量内部的内存管理，因此除非是系统内存耗尽，我们可以不用担心向 map 中插入新数据的数量和执行结果。
不过，如果我们插入新键值对的时候，某个 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]
从这段代码中你可以看到，map 类型变量 m 在声明的同时就做了初始化，它的内部建立了两个键值对，其中就包含键 key1。所以后面我们再给键 key1 进行赋值时，Go 不会重新创建 key1 键，而是会用新值 (11) 把 key1 键对应的旧值 (1) 替换掉。
操作二：获取键值对数量。
如果我们在编码中，想知道当前 map 类型变量中已经建立了多少个键值对，那我们可以怎么做呢？和切片一样，map 类型也可以通过内置函数 len，获取当前变量已经存储的键值对数量：
m := map[string]int {
"key1" : 1,
"key2" : 2,
}
fmt.Println(len(m)) // 2
m["key3"] = 3
fmt.Println(len(m)) // 3
不过，这里要注意的是我们不能对 map 类型变量调用 cap，来获取当前容量，这是 map 类型与切片类型的一个不同点。
操作三：查找和数据读取
和写入相比，map 类型更多用在查找和数据读取场合。所谓查找，就是判断某个 key 是否存在于某个 map 中。有了前面向 map 插入键值对的基础，我们可能自然而然地想到，可以用下面代码去查找一个键并获得该键对应的值：
m := make(map[string]int)
v := m["key1"]
乍一看，第二行代码在语法上好像并没有什么不当之处，但其实通过这行语句，我们还是无法确定键 key1 是否真实存在于 map 中。这是因为，当我们尝试去获取一个键对应的值的时候，如果这个键在 map 中并不存在，我们也会得到一个值，这个值是 value 元素类型的零值。
我们以上面这个代码为例，如果键 key1 在 map 中并不存在，那么 v 的值就会被赋予 value 元素类型 int 的零值，也就是 0。所以我们无法通过 v 值判断出，究竟是因为 key1 不存在返回的零值，还是因为 key1 本身对应的 value 就是 0。
那么在 map 中查找 key 的正确姿势是什么呢？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
我们看到，这里我们通过了一个布尔类型变量 ok，来判断键“key1”是否存在于 map 中。如果存在，变量 v 就会被正确地赋值为键“key1”对应的 value。
不过，如果我们并不关心某个键对应的 value，而只关心某个键是否在于 map 中，我们可以使用空标识符替代变量 v，忽略可能返回的 value：
m := make(map[string]int)
_, ok := m["key1"]
... ...
因此，你一定要记住：在 Go 语言中，请使用“comma ok”惯用法对 map 进行键查找和键值读取操作。
操作四：删除数据。
接下来，我们再看看看如何从 map 中删除某个键值对。在 Go 中，我们需要借助内置函数 delete 来从 map 中删除数据。使用 delete 函数的情况下，传入的第一个参数是我们的 map 类型变量，第二个参数就是我们想要删除的键。我们可以看看这个代码示例：
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]
这里要注意的是，delete 函数是从 map 中删除键的唯一方法。即便传给 delete 的键在 map 中并不存在，delete 函数的执行也不会失败，更不会抛出运行时的异常。
操作五：遍历 map 中的键值数据
最后，我们来说一下如何遍历 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")
}
你看，通过 for range 遍历 map 变量 m，每次迭代都会返回一个键值对，其中键存在于变量 k 中，它对应的值存储在变量 v 中。我们可以运行一下这段代码，可以得到符合我们预期的结果：
{ [1, 11] [2, 12] [3, 13] }
如果我们只关心每次迭代的键，我们可以使用下面的方式对 map 进行遍历：
for k, _ := range m {
// 使用k
}
当然更地道的方式是这样的：
for k := range m {
// 使用k
}
如果我们只关心每次迭代返回的键所对应的 value，我们同样可以通过空标识符替代变量 k，就像下面这样：
for _, v := range m {
// 使用v
}
不过，前面 map 遍历的输出结果都非常理想，给我们的表象好像是迭代器按照 map 中元素的插入次序逐一遍历。那事实是不是这样呢？我们再来试试，多遍历几次这个 map 看看。
我们先来改造一下代码：
package main
import "fmt"
func doIteration(m map[int]int) {
fmt.Printf("{ ")
for k, v := range m {
fmt.Printf("[%d, %d] ", k, v)
}
fmt.Printf("}\n")
}
func main() {
m := map[int]int{
1: 11,
2: 12,
3: 13,
}
for i := 0; i < 3; i++ {
doIteration(m)
}
}
运行一下上述代码，我们可以得到这样结果：
{ [3, 13] [1, 11] [2, 12] }
{ [1, 11] [2, 12] [3, 13] }
{ [3, 13] [1, 11] [2, 12] }
我们可以看到，对同一 map 做多次遍历的时候，每次遍历元素的次序都不相同。这是 Go 语言 map 类型的一个重要特点，也是很容易让 Go 初学者掉入坑中的一个地方。所以这里你一定要记住：程序逻辑千万不要依赖遍历 map 所得到的的元素次序。
从我们前面的讲解，你应该也感受到了，map 类型非常好用，那么，我们在各个函数方法间传递 map 变量会不会有很大开销呢？

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]
}

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”)
这是 map 类型在 Go 运行时层实现的示意图：
我们可以看到，和切片的运行时表示图相比，map 的实现示意图显然要复杂得多。接下来，我们结合这张图来简要描述一下 map 在运行时层的实现原理。我们重点讲解一下一个 map 变量在初始状态、进行键值对操作后，以及在并发场景下的 Go 运行时层的实现原理。

初始状态

从图中我们可以看到，与语法层面 map 类型变量（m）一一对应的是 *runtime.hmap 的实例，即 runtime.hmap 类型的指针，也就是我们前面在讲解 map 类型变量传递开销时提到的 map 类型的描述符。hmap 类型是 map 类型的头部结构（header），它存储了后续 map 类型操作所需的所有信息，包括：
真正用来存储键值对数据的是桶，也就是 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 的位置。我把这一过程整理成了下面这张示意图，你理解起来可以更直观：
因此，每个 bucket 的 tophash 区域其实是用来快速定位 key 位置的，这样就避免了逐个 key 进行比较这种代价较大的操作。尤其是当 key 是 size 较大的字符串类型时，好处就更突出了。这是一种以空间换时间的思路。
key 存储区域
接着，我们看 tophash 区域下面是一块连续的内存区域，存储的是这个 bucket 承载的所有 key 数据。运行时在分配 bucket 的时候需要知道 key 的 Size。那么运行时是如何知道 key 的 size 的呢？
当我们声明一个 map 类型变量，比如 var m map[string]int 时，Go 运行时就会为这个变量对应的特定 map 类型，生成一个 runtime.maptype 实例。如果这个实例已经存在，就会直接复用。maptype 实例的结构是这样的：
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
}
我们可以看到，这个实例包含了我们需要的 map 类型中的所有"元信息"。我们前面提到过，编译器会把语法层面的 map 操作重写成运行时对应的函数调用，这些运行时函数都有一个共同的特点，那就是第一个参数都是 maptype 指针类型的参数。
Go 运行时就是利用 maptype 参数中的信息确定 key 的类型和大小的。map 所用的 hash 函数也存放在 maptype.key.alg.hash(key, hmap.hash0) 中。同时 maptype 的存在也让 Go 中所有 map 类型都共享一套运行时 map 操作函数，而不是像 C++ 那样为每种 map 类型创建一套 map 操作函数，这样就节省了对最终二进制文件空间的占用。
value 存储区域
我们再接着看 key 存储区域下方的另外一块连续的内存区域，这个区域存储的是 key 对应的 value。和 key 一样，这个区域的创建也是得到了 maptype 中信息的帮助。Go 运行时采用了把 key 和 value 分开存储的方式，而不是采用一个 kv 接着一个 kv 的 kv 紧邻方式存储，这带来的其实是算法上的复杂性，但却减少了因内存对齐带来的内存浪费。
我们以 map[int8]int64 为例，看看下面的存储空间利用率对比图：
你会看到，当前 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
)

map 扩容

我们前面提到过，map 会对底层使用的内存进行自动管理。因此，在使用过程中，当插入元素个数超出一定数值后，map 一定会存在自动扩容的问题，也就是怎么扩充 bucket 的数量，并重新在 bucket 间均衡分配数据的问题。
那么 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
}
... ...
}
这两方面原因导致的扩容，在运行时的操作其实是不一样的。如果是因为 overflow bucket 过多导致的“扩容”，实际上运行时会新建一个和现有规模一样的 bucket 数组，然后在 assign 和 delete 时做排空和迁移。
如果是因为当前数据数量超出 LoadFactor 指定水位而进行的扩容，那么运行时会建立一个两倍于现有规模的 bucket 数组，但真正的排空和迁移工作也是在 assign 和 delete 时逐步进行的。原 bucket 数组会挂在 hmap 的 oldbuckets 指针下面，直到原 buckets 数组中所有数据都迁移到新数组后，原 buckets 数组才会被释放。你可以结合下面的 map 扩容示意图来理解这个过程，这会让你理解得更深刻一些：

map 与并发

接着我们来看一下 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
不过，如果我们仅仅是进行并发读，map 是没有问题的。而且，Go 1.9 版本中引入了支持并发写安全的 sync.Map 类型，可以在并发读写的场景下替换掉 map。如果你有这方面的需求，可以查看一下sync.Map 的手册。
另外，你要注意，考虑到 map 可以自动扩容，map 中数据元素的 value 位置可能在这一过程中发生变化，所以 Go 不允许获取 map 中 value 的地址，这个约束是在编译期间就生效的。下面这段代码就展示了 Go 编译器识别出获取 map 中 value 地址的语句后，给出的编译错误：
p := &m[key] // cannot take the address of m[key]
fmt.Println(p)

小结

好了，今天的课讲到这里就结束了。这一节课，我们讲解了 Go 语言的另一类十分常用的复合数据类型：map。
在 Go 语言中，map 类型是一个无序的键值对的集合。它有两种类型元素，一类是键（key），另一类是值（value）。在一个 map 中，键是唯一的，在集合中不能有两个相同的键。Go 也是通过这两种元素类型来表示一个 map 类型，你要记得这个通用的 map 类型表示：“map[key_type]value_type”。
map 类型对 key 元素的类型是有约束的，它要求 key 元素的类型必须支持"==“和”!="两个比较操作符。value 元素的类型可以是任意的。
不过，map 类型变量声明后必须对它进行初始化后才能操作。map 类型支持插入新键值对、查找和数据读取、删除键值对、遍历 map 中的键值数据等操作，Go 为开发者提供了十分简单的操作接口。这里要你重点记住的是，我们在查找和数据读取时一定要使用“comma ok”惯用法。此外，map 变量在函数与方法间传递的开销很小，并且在函数内部通过 map 描述符对 map 的修改会对函数外部可见。
另外，map 的内部实现要比切片复杂得多，它是由 Go 编译器与运行时联合实现的。Go 编译器在编译阶段会将语法层面的 map 操作，重写为运行时对应的函数调用。Go 运行时则采用了高效的算法实现了 map 类型的各类操作，这里我建议你要结合 Go 项目源码来理解 map 的具体实现。
和切片一样，map 是 Go 语言提供的重要数据类型，也是 Gopher 日常 Go 编码是最常使用的类型之一。我们在日常使用 map 的场合要把握住下面几个要点，不要走弯路：
不要依赖 map 的元素遍历顺序；
map 不是线程安全的，不支持并发读写；
不要尝试获取 map 中元素（value）的地址。

思考题

通过上面的学习，我们知道对 map 类型进行遍历所得到的键的次序是随机的，那么我想请你思考并实现一个方法，让我们能对 map 的进行稳定次序遍历？期待在留言区看到你的想法。
欢迎你把这节课分享给更多对 Go 语言 map 类型感兴趣的朋友。我是 Tony Bai，我们下节课见。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 45

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
15｜同构复合类型：从定长数组到变长切片
下一篇
17｜复合数据类型：用结构体建立对真实世界的抽象
unpreview
 写留言

精选留言(59)

  • 罗杰
    2021-11-17
    还想深入研究 map 的小伙伴，可以去研究这些博客： https://www.qcrao.com/2019/05/22/dive-into-go-map/ https://qcrao.com/2020/05/06/dive-into-go-sync-map/ https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
    共 9 条评论
    33
  • 用0和1改变自己
    2021-11-17
    可以用一个有序结构存储key,如slice,然后for这个slice,用key获取值。资料来源至：https://go.dev/blog/maps

    作者回复: ✅

    共 2 条评论
    26
  • ddh
    2022-04-25
    请问一下老师， map 元素不能寻址， 是因为动态扩容， 那么切片不也有动态扩容吗。 为什么切片元素可以寻址呢？ 难道切片动态扩容之后， 它的元素地址不会变吗

    作者回复: 好问题！ 关于这个问题，官方没有明确说明。 我觉得之所以map element是不可寻址的，还是复杂性和安全性的考虑。 Go slice和map都是复合数据类型，但两者的内部实现复杂度却远远不同。map要远复杂于slice。 slice的元素的地址要么在要么在原底层数组中，要么在扩容后的新数组中。并且slice扩容是一次完成的。 但map扩容是“蚂蚁搬家”，element位置复杂一些，可能在原bucket中、可能在overflow bucket中，也可能在新扩容的bucket中。 此外，一旦暴露map element的地址，比如我们用一个栈上的指针变量引用了该地址，当发生element移动时，go就要考虑连带变更这些栈上指针变量的指向，这些变更操作在每个map操作中都会导致运行时消耗的增加。 至于安全性，map有着一个复杂内部结构，这个结构环环相扣。一旦map element地址被暴露，通过该地址不仅可以修改value值，还可能会对map内部结构造成破坏，这种破坏将导致整个map工作不正常。而slice的element即便被hack，改掉的也只是元素值。

    共 3 条评论
    11
  • thomas
    2022-04-12
    go团队为什么要故意把map的遍历设置为随机？

    作者回复: 这一话题要追溯到Go 1.0版本发布的时候，从Go 1.0版本的发布文档- https://go.dev/doc/go1中，我们能找到如下内容： The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another. In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order. This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map. 翻译过来，大致意思就是：1.0版本之前的语言规范中没有规定map的迭代次序，从而导致在实践中的一些糟糕的开发运行体验。于是Go团队选 择故意在map中加入随机迭代功能，这样一旦出现开发人员依赖key迭代顺序的错误行为，这一行为导致的问题在开发和测试早期就能被及时发现，而不会出现在生产运行环境中导致更大的危害。

    8
  • Darren
    2021-11-17
    可以参考java的LinkedHashMap,能实现插入有序或者访问有序，就是使用额外的链表来保存顺序。 go 中可以基于container/list来实现。github上现成的功能。 https://github.com/elliotchance/orderedmap
    6
  • ddh
    2021-11-17
    把key存到有序切片中，用切片遍历

    作者回复: 是一个可行方法。

    共 2 条评论
    4
  • Geek_244c46
    2022-05-26
    map的key和value的值，是否可以为null

    作者回复: 用代码回答你的问题：） // testnilasmapkey.go package main func main() { var m = make(map[*int]*int) m[nil] = nil println(m) println(len(m)) var b = 5 m[nil] = &b p := m[nil] println(*p) } 0xc0000466b0 1 5 nil作为value不新鲜。但nil可作为key可是很多人都不知道的。

    3
  • flexiver
    2022-04-21
    老师，想请问一下，hmap这个结构中的extra字段， 在key和value都不是指针的情况下，会存储所有的overflow bucket的指针，里面有提到一个内联，这个内联是什么意思？以及为什么当key和value都不是指针的情况下，会将bucket中的overflow指针全部放到extra字段存储

    作者回复: 在Go项目源码(Go 1.17版本)的 src/cmd/compile/internal/reflectdata/reflect.go中，func MapBucketType(t *types.Type) *types.Type>这个函数实现中，我们可以勾勒出一个bucket桶的结构： tophash keys values overflow pointer 不过这个overflow pointer有两种情况： // If keys and elems have no pointers, the map implementation // can keep a list of overflow pointers on the side so that // buckets can be marked as having no pointers. // Arrange for the bucket to have no pointers by changing // the type of the overflow field to uintptr in this case. // See comment on hmap.overflow in runtime/map.go. otyp := types.Types[types.TUNSAFEPTR] if !elemtype.HasPointers() && !keytype.HasPointers() { otyp = types.Types[types.TUINTPTR] } 当key和value中都没有指针时，比如map[int]int。此时考虑到gc优化，编译器将overflow的类型设置为uintptr。 uintptr是一个整型，无法被GC识别，这样一来uintptr指向的overflow bucket就没有指向它的指针，这样gc就会将overflow bucket视为unrea chable的mem块而将其释放掉。为了避免这种情况，hmap中的extra此时就会指向上面这类bucket的overflow bucket，保证key和value中都不含指针时，overflow bucket依旧可以不被gc。

    3
  • 文经
    2022-01-05
    我看了《Go语言实践》，《Go专家编程》，《Go语言底层原理剖析》这几本书对map的描述，对比才发现白老师讲得最清晰，在封装和细节方面拿捏得最好，大大地赞👍 剩下不清楚的地方就只能自己看源码了。

    作者回复: 过奖。其实原理这东西最终还是要落到代码上。而且不同版本实现也有差异。要想真正把原理吃透，还得自己多过几遍代码

    3
  • 多选参数
    2021-11-22
    突然想到之前碰到的一个问题，就是golang 结构体作为map的元素时，不能够直接赋值给结构体的某个字段。这个也有“Go 不允许获取 map 中 value 的地址”的原因在嘛？假如这样的话，那么为什么读结构体中的某个字段是可以的？

    作者回复: 读操作得到的是值的一个copy

    共 2 条评论
    3
  • 不负青春不负己🤘
    2021-11-19
    可以把key 赋值到变量，使用sort 排序，在遍历

    作者回复: ✅

    3
  • 高雪斌
    2021-11-17
    func doIteration(m map[int]int) { mu.RLock() defer mu.RUnlock() keys := []int{} for k := range m { keys = append(keys, k) } sort.SliceStable(keys, func(x, y int) bool { return x < y }) for _, k := range keys { fmt.Printf("[%d, %d] ", k, m[k]) } fmt.Println() } func doWrite(m map[int]int) { mu.Lock() defer mu.Unlock() for k, v := range m { m[k] = v + 1 } } ==> 对并发示例代码的稳定排序输出 (原例1000次输出太多，输出前10个作为说明)： [1, 11] [2, 12] [3, 13] [1, 12] [2, 13] [3, 14] [1, 13] [2, 14] [3, 15] [1, 14] [2, 15] [3, 16] [1, 15] [2, 16] [3, 17] [1, 16] [2, 17] [3, 18] [1, 17] [2, 18] [3, 19] [1, 18] [2, 19] [3, 20] [1, 19] [2, 20] [3, 21] [1, 20] [2, 21] [3, 22] 。。。
    展开

    作者回复: 不错的思路。

    共 2 条评论
    2
  • Geek_f654de
    2022-02-25
    思考题： 1.把map的key拿出来，放到切片里 2.对切片进行排序 3.取出切片中元素对应的value

    作者回复: ✅

    1
  • Casper
    2021-12-02
    老师，请问一下如果是因为overflow bucket过多导致的"扩容", 是否可以理解为这个hash函数的算法不太合理，导致大部分的key都分配到了一个bucket中，是否可以通过修改hash算法来重新hash一遍呢？

    作者回复: go map底层的hash函数要考虑通用性。谁也不能预测用户会使用什么样的key数据。

    1
  • lesserror
    2021-11-19
    Tony Bai 老师，麻烦有时间回复一下以下几个问题： 1. 文中说： “map 所用的 hash 函数也存放在 maptype.key.alg.hash(key, hmap.hash0) 中。” 后面的这一串：“maptype.key.alg.hash(key, hmap.hash0) ” 是什么？ 看的有点懵。 2. 不管是使用字面值 还是用 make函数初始化 map类型变量，打印变量名，都是输出的 map[] 而不是 nil ，这个输出是正常的吗？
    展开

    作者回复: 1. 引用层次太深，所以用了伪代码形式的简写。就是说hash函数存放在maptype类型中的key字段的alg字段中的hash字段中，key是hash函数的第一个参数，是待hash的字段。第二个参数是种子(hmap.hash0就是种子)。go 1.17中这块的组成发生了一些变化。这个hash函数直接放在maptype的hasher字段中了。但原理应该没有变。 2. var m map[string]int // m = nil 你说的是这里么？这里后面注释中不是打印输出，而是指 m为nil。

    共 4 条评论
    1
  • AlexWillBeGood
    2021-11-18
    老师，有一点我不明白，为什么kv 紧邻存储的时候一定需要Padding？

    作者回复: 看完第17讲，你就有思路了。

    共 4 条评论
    1
  • Geek_0b92d9
    2021-11-17
    老师好。我是 go1.16.2 版本 var m map[string]int 定义后， 打印 m , 是 map[]，不是 nil

    作者回复: var m map[string]int // m = nil 注释中的m = nil 是提示m的值为nil，不是打印输出。

    共 2 条评论
    1
  • return
    2021-11-17
    老师讲的太好了，
    1
  • aoe
    2021-11-17
    使用链表存储可以得到有序的Map。有了描述符，再也不用担心传递性能问题了！原来多个bucket是为了降低Hash冲突，虽然一个bucket和多个bucket在查找Key时时间复杂度都是O(1)，但一个Bucket遇到Hash冲突的可能性要比多个高出很多。
    1
  • 邹志鹏.Joey ⁷⁷...
    2023-01-18 来自广东
    既切片之后, 应该是 "继切片之后"?

    作者回复: 👍。稍后让编辑老师修改一下这个typo。