书籍来源：《Go语言精进之路：从新手到高手的编程思想、方法和技巧》
一边学习一边整理读书笔记，并与大家分享，侵权即删，谢谢支持！
附上汇总贴：《Go语言精进之路》读书笔记 | 汇总_COCOgsta的博客-CSDN博客
map类型也是Go语言中最常用的数据类型之一。
14.1 什么是map
map是Go语言提供的一种抽象数据类型，它表示一组无序的键值对（key-value）。
必须对map类型变量进行显式初始化后才能使用它。和切片一样，创建map类型变量有两种方式：一种是使用复合字面值，另一种是使用make这个预声明的内置函数。
（1）使用复合字面值创建map类型变量
// $GOROOT/src/net/status.go
var statusText = map[int]string{
StatusOK: "OK",
StatusCreated: "Created",
StatusAccepted: "Accepted",
...
}
复制代码 （2）使用make创建map类型变量
// $GOROOT/src/net/client.go
icookies = make(map[string][]*Cookie)
// $GOROOT/src/net/h2_bundle.go
http2commonLowerHeader = make(map[string]string, len(common))
复制代码 和切片一样，map也是引用类型，将map类型变量作为函数参数传入不会有很大的性能损耗，并且在函数内部对map变量的修改在函数外部也是可见的，比如下面的例子：
// chapter3/sources/map_var_as_param.go
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]
}
复制代码 可以看到，函数foo中对m进行了修改，这些修改在foo函数外可见。
14.2 map的基本操作
- 插入数据
m := make(map[K]V)
m[k1] = v1
m[k2] = v2
m[k3] = v3
复制代码 如果key已经存在于map中，则该插入操作会用新值覆盖旧值：
m := map[string]int {
"key1" : 1,
"key2" : 2,
}
m["key1"] = 11 // 11会覆盖掉旧值1
m["key3"] = 3 // map[key1:11 key2:2 key3:3]
复制代码 - 获取数据个数
map可以通过内置函数len获取当前已经存储的数据个数：
m := map[string]int {
"key1" : 1,
"key2" : 2,
}
fmt.Println(len(m)) // 2
m["key3"] = 3
fmt.Println(len(m)) // 3
复制代码 - 查找和数据读取
可以使用“comma ok”惯用法来进行查找：
_, ok := m["key"]
if !ok {
// "key"不在map中
}
复制代码 如果要读取key对应的value的值，我们可能会写出下面这样的代码：
m := map[string]int
m["key1"] = 1
m["key2"] = 2
v := m["key1"]
fmt.Println(v) // 1
v = m["key3"]
fmt.Println(v) // 0
复制代码 因为无法判定这个0是“key3”对应的值还是因“key3”不存在而返回的零值，还需要借助“comma ok”惯用法：
m := map[string]int
v, ok := m["key"]
if !ok {
// "key"不在map中
}
fmt.Println(v)
复制代码 综上，Go语言的一个最佳实践是总是使用“comma ok”惯用法读取map中的值。
- 删除数据
m := map[string]int {
"key1" : 1,
"key2" : 2,
}
fmt.Println(m) // map[key1:1 key2:2]
delete(m, "key2")
fmt.Println(m) // map[key1:1]
复制代码 - 遍历数据
通过for range语句对map中的数据进行遍历：
// chapter3/sources/map_iterate.go
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")
}
$ go run map_iterate.go
{ [1, 11] [2, 12] [3, 13] }
复制代码 但是不能依赖遍历map所得到的元素次序。如果需要一个稳定的遍历次序，可使用另一种数据结构来按需要的次序保存key，比如切片：
// chapter3/sources/map_stable_iterate.go
import "fmt"
func doIteration(sl []int, m map[int]int) {
fmt.Printf("{ ")
for _, k := range sl { // 按切片中的元素次序迭代
v, ok := m[k]
if !ok {
continue
}
fmt.Printf("[%d, %d] ", k, v)
}
fmt.Printf("}\n")
}
func main() {
var sl []int
m := map[int]int{
1: 11,
2: 12,
3: 13,
}
for k, _ := range m {
sl = append(sl, k) // 将元素按初始次序保存在切片中
}
for i := 0; i < 3; i++ {
doIteration(sl, m)
}
}
$go run map_stable_iterate.go
{ [1, 11] [2, 12] [3, 13] }
{ [1, 11] [2, 12] [3, 13] }
{ [1, 11] [2, 12] [3, 13] }
复制代码 14.3 map的内部实现
Go运行时使用一张哈希表来实现抽象的map类型。
- 初始状态
hmap是map类型的header，可以理解为map类型的描述符，它存储了后续map类型操作所需的所有信息。
图14-1 运行时的map类型实现
用来存储键值对数据的是bucket（桶），每个bucket由三部分组成：tophash区域、key存储区域和value存储区域。
（1）tophash区域
每个bucket的tophash区域是用于快速定位key位置的，避免了逐个key进行比较这种代价较大的操作，尤其是当key是size较大的字符串类型时，这是一种以空间换时间的思路。
（2）key存储区域
tophash区域下面是一块连续的内存区域，存储的是该bucket承载的所有key数据。在分配bucket时可以通过maptype参数中的信息确定key的类型和大小。
（3）value存储区域
Go运行时采用了将key和value分开存储而不是采用一个kv接着一个kv的kv紧邻方式存储，这带来的是算法上的复杂性，但却减少了因内存对齐带来的内存浪费。
- map扩容
map在什么情况下会进行扩容呢？Go运行时的map实现中引入了一个LoadFactor（负载因子），当count > LoadFactor * 2^B或overflow bucket过多时，运行时会对map进行扩容。
- map与并发
map实例不支持并发读写。如果仅仅是并发读，则map是没有问题的。
Go 1.9版本中引入了支持并发写安全的sync.Map类型，可以用来在并发读写的场景下替换掉map。
14.4 尽量使用cap参数创建map
如果可能的话，我们最好对map使用规模做出粗略的估算，并使用cap参数对map实例进行初始化。
![算法图解读书笔记 第8章 贪婪算法[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)