共计 12023 个字符，预计需要花费 31 分钟才能阅读完成。
map 又称为 hash 表、字典，存储键值对，其增删改查工夫复杂度能够达到 O(1)。map 和切片是 Go 语言开发最罕用的数据类型。
基本操作
map 存储键值对，反对 key-value 键值对的插入，查找 / 批改 / 删除 key 对应的 value，并且这些操作都能够在 O(1) 工夫复杂度实现。
package main
import "fmt"
func main() {
//map 申明初始化
score := make(map[string]int, 0)
//key-value 键值对存储
score["zhangsan"] = 100
score["lisi"] = 90
//len 返回 map 存储的键值对数目
fmt.Println(len(score), score) //2 map[lisi:90 zhangsan:100]
// 查找 key 对应值，两种形式：1）返回值 value，以及 bool 值示意 key-value 键值对是否存在；2）只返回值 value
zhangsan, ok := score["zhangsan"]
zhangsan1 := score["zhangsan"]
fmt.Println(zhangsan, ok, zhangsan1) //100 true 100
// 批改 key 对应值
score["zhangsan"] = 95
fmt.Println(score["zhangsan"]) //95
// 删除 map 中键值对
delete(score,"zhangsan")
// 这时候查找 key 对应值，返回 value 类型空值，int 类型空值就是 0
zhangsan, ok = score["zhangsan"]
fmt.Println(zhangsan, ok) //0 false
}len 函数能够获取 map 键值对数目，留神 map 在查找 key 对应的 value 时，有两种形式：1）返回一个变量，只返回值 value；2）返回两个变量，第一个示意值 value，第二个为 bool 类型示意 key-value 键值对是否存在。另外，key-value 键值对不存在时，查找时返回的是值 value 类型对应空值，如整数 0，空字符串，空切片，指针 nil 等。特地当值类型为指针时要留神，应用之前最好判断下查找的键值对是否存在，以防呈现空指针异样 panic。
map 也反对 for range 遍历（迭代），相熟 PHP 语言的都晓得，PHP 数组元素的遍历和插入程序是一样的；要特地留神 Go 语言 map 遍历时，键值对的拜访程序和插入是不统一的，并且每次遍历的拜访程序都不同，如上面例子所示：
package main
import "fmt"
func main() {
//map 申明初始化
score := make(map[string]int, 0)
//key-value 键值对存储
for i := 0; i < 10; i ++ {score[fmt.Sprintf("test-%v", i)] = i
}
for k, v := range score {fmt.Printf("%v:%v", k, v)
}
//test-4:4 test-8:8 test-2:2 test-3:3 test-5:5 test-6:6 test-7:7 test-9:9 test-0:0 test-1:1
fmt.Printf("\n")
for k, v := range score {fmt.Printf("%v:%v", k, v)
}
//test-9:9 test-0:0 test-1:1 test-5:5 test-6:6 test-7:7 test-2:2 test-3:3 test-4:4 test-8:8
fmt.Printf("\n")
// 间接批改 v 是没有用的
for _, v := range score {v += 100}
//map[test-0:0 test-1:1 test-2:2 test-3:3 test-4:4 test-5:5 test-6:6 test-7:7 test-8:8 test-9:9]
fmt.Println(score)
// 遍历过程中这样批改 map 键值对
for k, v := range score {score[k] = v + 100
}
//map[test-0:100 test-1:101 test-2:102 test-3:103 test-4:104 test-5:105 test-6:106 test-7:107 test-8:108 test-9:109]
fmt.Println(score)
}看到了吧，两次遍历输入后果都是不一样的，当然你在运行这段代码的时候，后果大概率与下面输入也是不同的。而且，遍历过程中，想批改键 key 对应的值 value 也要留神形式，变量 k，v 只是以后拜访的键值对的拷贝，间接批改变量 v 没有任何意义。
看到上述代码，忽然想到一个问题：如果遍历过程中，往 map 新增键值对，会怎么样？新增的键值对会再次被遍历拜访到吗？遍历过程会有限继续吗？
package main
import "fmt"
func main() {
//map 申明初始化
score := make(map[string]int, 0)
//key-value 键值对存储
for i := 0; i < 3; i ++ {score[fmt.Sprintf("test-%v", i)] = i
}
//map[test-0:0 test-1:1 test-2:2]
fmt.Println(score)
for k, v := range score {score[fmt.Sprintf("%v-%v", k, v)] = v + 1
}
//8 map[test-0:0 test-0-0:1 test-0-0-1:2 test-1:1 test-1-1:2 test-1-1-2:3 test-2:2 test-2-2:3]
fmt.Println(len(score),score)
}貌似遍历过程并没有有限继续。初始 map 键值对数目为 3，遍历过程中新增键值对，如果新增的键值对不会再次被遍历拜访到，实践上完结后 map 键值对数目应该为 6，然而后果却显示 8，键值对数目靠近为原来的 2 倍多，而且察看输入后果，很显著，新增的键值对再次被遍历拜访到了。为什么最终键值对数目为 8 呢？其实这也是一个随机景象，屡次运行，你会发现 map 蕴含的键值对数据以及数目都是随机的。为什么呢？这里先保留一个疑难，前面会具体阐明。
最初还有一个小小的问题，map 作为函数输出参数时，函数中批改了 map（批改 / 删除 / 新增键值对），在函数调用方，map 会同步产生扭转吗？len 会扭转吗？会和切片景象一样吗？
package main
import "fmt"
func main() {score := make(map[string]int, 0)
score["zhangsan"] = 100
fmt.Println(len(score), score) //1 map[zhangsan:100]
testMap(score)
fmt.Println(len(score), score) //2 map[lisi:90 zhangsan:100]
}
func testMap(m map[string]int) {m["lisi"] = 90
fmt.Println(len(m), m) //2 map[lisi:90 zhangsan:100]
}map 数据，len 居然都产生扭转了！说好的 Go 语言函数按值传参呢，map 存储的键值对会产生扭转还能了解，参考切片，底层数组或者是什么构造能够共用，可是 len 为什么也会扭转呢？这里先保留一个疑难，前面会具体阐明。不过在解说之前，能够先思考下，len 应该扭转吗？
实现原理
map 也能够称为 hash 表，字典，其是如何实现 O(1) 的增删改查工夫复杂度呢？学习过数据结构的读者应该都晓得，个别有两种形式：凋谢寻址法和拉链法。最罕用的当属拉链法了，基于数组 + 链表实现，先应用散列函数将键 key 映射到数组索引（如：计算 hash 值，并按数组长度取模），因为不同的键 key 可能映射到同一个数组索引，所以多个键值对造成链表。
Go 语言 map 采取的就是拉链法，只是还做了一些小小的优化。原始计划链表节点存储键值对，每个节点还蕴含 next 指针，这样算下来内存利用率其实是较低的；Go 语言将多个元素压缩到同一个链表节点（8 个），相当于 8 个 key-value 键值对才须要一个 next 指针，内存利用率天然比原始计划高。另外，因为 CPU 高速缓存（L1、L2、L3）存在，间断内存拜访的性能个别要高于扩散内存拜访，即 8 个 key-value 键值对间断存储的拜访性能略好。
Go 语言 map 构造如下图所示，buckets 就是咱们所说的数组，能够看到链表节点存储多个 key-value 键值对，并且多个 key 间断存储，再跟着多个 value 间断存储：
后面介绍的 map 初始化以及增删改查基本操作，底层都对应有函数实现，定义在文件 runtime/map.go：
//make 第二个参数，小于等于 8 对应 makemap_small 函数
func makemap_small() *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap
// 依据 key 查找对应 value，只返回值；对应 v = map[key] 写法
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// 依据 key 查找对应 value，返回两个变量：1）值；2）key 是否存在。对应 v, ok = map[key] 写法
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
// 新增或者批改键值对
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// 删除键值对
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)在介绍这些基本操作之前，先理解下 map 相干构造的定义：
type hmap struct {
count int // 键值对数目，len 返回的就是该值
B uint8 // 数组 buckets 长度为 2^B
buckets unsafe.Pointer // buckets 数组
}
// bucketCnt = 8
type bmap struct {
// tophash generally contains the top byte of the hash value for each key in this bucket
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)buckets 指向数组首地址，bmap 就是链表节点的构造定义，然而其定义只有一个 tophash 字段，看不出什么多个 key 多个 value 间断存储。须要阐明的是，理论怎么拜访 bmap 内容就看你的代码怎么写了，其实与构造定义没有太大关系，毕竟变量拜访无非只须要地址 + 长度就行了。读者能够浏览这里的正文了，具体阐明了 tophash 字段前面还跟着多个 key，多个 value，以及 overflow 指针（就是 next 指针）。而变量 dataOffset 就是第一个键 key 首地址绝对于构造体 bmap 首地址的偏移量。
留神 tophash 字段，uint8 数组，正文解释到，其存储的是键 key 的 hash 值的高字节；hash 值类型为 int64，占 8 字节，而最高字节内容就存储在 tophash 数组。tophash 用于疾速比拟键 key 的 hash 值是否相等，计算形式如下：
func tophash(hash uintptr) uint8 {top := uint8(hash >> (goarch.PtrSize*8 - 8)) //PtrSize 为 8 字节
if top < minTopHash { //minTopHash = 5，强制 tophash 值大于 minTopHash
top += minTopHash
}
return top
}为什么 tophash 值必须大于 minTopHash 呢？因为小于 minTopHash 的值有非凡标识，用于晋升键 key 查找效率。比方：
// 以后地位没有存储键值对，且以后桶后续地位也都没有存储键值对
emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
// 以后地位没有存储键值对
emptyOne = 1 // this cell is empty另外，思考下为什么要间断存储多个 key，再跟着间断存储多个 value 呢？为什么不能按 key-value 键值对对存储呢？这就波及都内存对齐了，不同类型的变量有内存对齐要求，比方 int64 首地址必须按 8 字节对齐（首地址是 8 的倍数），int32 首地址必须依照 4 字节对齐，int8 无要求。所以针对 map[int64]int8，两种存储形式很显著会有如下区别：
好了，咱们理解到 map 底层构造为 hmap，其蕴含底层 buckets 数组，键值对数目等，再察看下面介绍的基本操作函数申明，map 初始化函数 makemap 返回 hmap 指针，map 新增 / 批改键值对函数 mapassign 输出参数为 hmap 指针，删除键值对函数 mapdelete 输出参数为 hmap 指针。那么当 map 作为参数传递呢？其传递的也是 hmap 指针，那么函数外部批改了 map 数据，调用方是否同步扭转呢？len 是否扭转呢？答案很显著了。
最初，基于这两个构造，map 是如何实现增删改查等基本操作呢？咱们已新增 / 批改键值对为例，其实现函数为 mapassign。该函数查找 map，如果找到对应 key，则替换值 value；如果没有找到对应 key，须要找到一个空的 bmap 地位，存储该键值对。留神学习上面代码时，联合 buckets 与 bmap 示意图更容易了解。
// 省略了局部代码
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 计算数组索引
bucket := t.hasher(key, uintptr(h.hash0)) & bucketMask(h.B)
//buckets 桶数组存储的其实就是 bmap 构造，该构造大小为 bucketsize
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
// 计算 tophash 值
top := tophash(hash)
// 记录查找到的可存储键值对地位
var inserti *uint8 // 该地位可存储 tophash 值
var insertk unsafe.Pointer // 该地位可存储键 key
var elem unsafe.Pointer // 该地位可存储值 value
bucketloop:
for {
// 遍历该 bmap 8 个地位；比拟 tophash 值，比拟 key
for i := uintptr(0); i < bucketCnt; i++ {
// 如果 tophash 值不相等，阐明键 key 必定不想等
if b.tophash[i] != top {
// 如果以后地位没有存储键值对，且 inserti 为空，首次记录该地位可存储键值对
if isEmpty(b.tophash[i]) && inserti == nil {inserti = &b.tophash[i]
//bmap 首地址偏移 dataOffset 就是第一个键 key 存储地位，第 i 个键 key，再偏移 i 个键 key 即可。insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 计算第 i 个值 value 地址，bmap 首地址偏移 dataOffset，再偏移 8 个键 key，再偏移 i 个值 value 即可。elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
//emptyRest 阐明以后桶后续地位也都没有存储键值对，即 map 中不存在该键 key；则新插入键值对到 inserti 地位。if b.tophash[i] == emptyRest {break bucketloop}
continue
}
// 获取键 key
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 判断查找到的键和输出 key 是否相等
if !t.key.equal(key, k) {continue}
//key 相等，则更新对应的值 value
if t.needkeyupdate() {typedmemmove(t.key, k, key)
}
goto done
}
// 该 bmap 没有找到对应 key，然而如果 overflow 不为空，则查找链表下一个 bmap
ovf := b.overflow(t)
if ovf == nil {break}
b = ovf
}
// 没有查找到对应 key，须要新增键值对
// 没有找到一个新地位，则须要申请新的 bmap
if inserti == nil {newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 剩下就是保留新增键值数据到 inserti，insertk，elem
}函数 mapassign 的留神逻辑都写分明了正文。当然还有一些细节临时省略了，比方新增键值对的时候还须要判断是否须要扩容，否则链表越来越长，map 的工夫复杂度将进化为 O(N)。map 的其余操作，如拜访 mapaccess1，删除 mapdelete 与新增 / 批改 mapassign 比拟相似，外围都是找到 bmap，遍历匹配键 key，这里就不再介绍了。
迭代 / 遍历
还记得咱们遗留的两个问题吗，1）for range 遍历 map 时，屡次遍历的拜访程序为什么不同呢？2）for range 遍历过程中，新增键值对，最终的键值对数目为什么也是随机的呢？针对问题 1，其实这是 Go 语言专门设计的，自身 map 的遍历程序就与插入程序不统一，Go 语言设计者，为了让开发人员不要依赖 map 的遍历程序，更是将 map 的遍历程序设计为随机的。
如何遍历 map 每一个键值对呢？咱们晓得 hmap 构造保护有一个 buckets 数组，数组元素类型为 bmap，bmap 又通过 overflow 指针造成链表。那么，咱们只须要遍历 buckets 数组，遍历 bmap 链表，也就能实现 map 所有键值对的遍历拜访。map 迭代 / 遍历依赖两个函数，其中 hiter 保护以后拜访到的地位，以及键值对信息：
func mapiterinit(t *maptype, h *hmap, it *hiter)
func mapiternext(it *hiter)
type hiter struct {
// 键值对
key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
// 以后遍历的 bmap
bptr *bmap // current bucket
// 以后 map 已遍历了几个键值对
i uint8
// 开始遍历的 bucket 地位
startBucket uintptr // bucket iteration started at
// 偏移量，每一个 bmap 从该偏移量开始遍历
offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
// 以后遍历的 bucket 地位
bucket uintptr
}函数 mapiterinit 初始化迭代器 hiter，包含开始遍历的 bucket 地位（随机），每一个 bmap 开始遍历的偏移量（随机）。正因为这两个值的随机性，才导致 map 的遍历程序随机。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
// 随机
r := uintptr(fastrand())
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))
it.bucket = it.startBucket
// 获取第一个键值对
mapiternext(it)
}函数 mapiternext 用于拜访下一个键值对，只须要从以后 bmap（hiter.bptr），以后偏移地位（hiter.i + hiter.offset）开始查找下一个键值对即可。如果以后 bmap 遍历结束，通过 overflow 获取下一个 bmap；如果以后 bucket 所有 bmap 都已遍历结束，bucket++；而最终再次遍历到 hiter.startBucket 时，阐明以后 map 已遍历结束。这里就不再详述，有趣味的读者能够本人钻研下函数 mapiternext 实现。
所以 for range 遍历 map 的伪代码应该如下：
iter := &hiter{}
mapiterinit(map, iter)
for {
if iter.key == nil {
// 遍历完结
break
}
k, v := iter.key, iter.elem
// 用户代码
// 拜访下一个键值对
mapiternext(iter)
}map 的遍历过程咱们都很分明了，当初是否能答复下面遗留的问题呢：遍历过程中，新增键值对，遍历过程并没有有限继续，map 最终的键值对数目居然是随机的！其实不难理解，新增的键值对会存储在哪一个 bucket 呢？不晓得，由键 key 的 hash 值决定；每次遍历从哪一个 bucket 开始呢？不晓得，齐全随机。那这就对了，如果新增的键值对，刚好存储在未遍历过的地位；那么就会再次拜访到，如果刚好存储在已遍历过的地位，那么就不会再次拜访到。所以，新增的键值对是否再次被拜访到也是随机的，所以，map 最终的键值对数目也是随机的。
扩容
扩容是什么？map 为什么须要扩容呢？想想如果初始化时，map 的 buckets 数组长度为 8，始终往 map 新增键值对，会呈现什么状况？buckets 数组上挂的 bmap 链表越来越长，这时候 map 的工夫复杂度还是 O(1) 吗？曾经进化为 O(N) 了！所以，map 须要扩容，须要更大的 buckets 数组。
那么 map 什么时候须要扩容呢？这里有一个概念叫负载因子，其示意最大可存储的键值对数目除以 buckets 数组长度。当 map 存储的键值对数目超过 buckets 数组长度乘以负载因子时，触发扩容操作。那么负载因子应该是多少呢？要晓得，当 buckets 数组长度固定时，负载因子越小，可存储的键值对越少，而一个 bmap 就能存储 8 个键值对，键值对过少会节约 bmap 内存空间；负载因子越大，可存储的键值对越多，键值对过多 bmap 链表越长时间复杂度又越高。Go 语言作者通过简略的程序，测试不同负载因子下，map 的一些指标：
// loadFactor %overflow bytes/entry hitprobe missprobe
// 4.00 2.13 20.77 3.00 4.00
// 4.50 4.05 17.30 3.25 4.50
// 5.00 6.85 14.77 3.50 5.00
// 5.50 10.55 12.94 3.75 5.50
// 6.00 15.27 11.67 4.00 6.00
// 6.50 20.90 10.79 4.25 6.50
// 7.00 27.14 10.15 4.50 7.00
// 7.50 34.03 9.73 4.75 7.50
// 8.00 41.10 9.40 5.00 8.00
//
// %overflow = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/elem pair
// hitprobe = # of entries to check when looking up a present key
// missprobe = # of entries to check when looking up an absent key最终，选取的负载因子是 6.5。扩容的时候，个别 buckets 数组长度扩充 2 倍，申请新的 buckets 数组，同时须要将老的 buckets 数组所有键值对迁徙到新的 buckets 数组，这就须要从新计算 hash 值，计算 buckets 数组索引，从新查找 bmap 闲暇地位。要留神，扩容也不是一次性实现的，即键值对的搬迁是逐渐分批次实现的，所以在这期间，同时存在两个 buckets 数组，这时候，map 的增删改查该拜访哪个 buckets 数组呢？
其实也是有迹可循的：1）新增 / 删除 / 批改键值对，如果以后 map 正在扩容，计算键 key 在 oldbuckets 数组索引，迁徙该 bucket 所有键值对到新 buckets 数组，继续执行原有新增 / 删除 / 批改键值对逻辑；2）键值对查找，如果以后 map 正在扩容，计算键 key 在 oldbuckets 数组 b 索引，该 bucket 即为须要查找的 bmap。问题来了，如何计算键 key 在 oldbuckets 数组索引呢？下面说了，扩容时，buckets 数组长度是扩充两倍的，有键 key 的 hash 值，有数组长度，计算数组索引还不容易吗？键值对迁徙逻辑能够参照上面两个函数：
//oldbucket 是须要迁徙的 oldbuckets 数组索引，逻辑省略
func evacuate(t *maptype, h *hmap, oldbucket uintptr)
// 判断该 bucket 键值对是否曾经迁徙
func evacuated(b *bmap) bool {h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
// 判断是否生在扩容
func (h *hmap) growing() bool {return h.oldbuckets != nil}所以，如果须要频繁操作 map 时，并且曾经晓得须要存储的键值对数目，比方转化切片到 map，这时候应用 make 初始化 map，能够指定初始 buckets 数组长度，防止不必要的扩容。
并发问题
咱们都晓得 Go 语言具备人造的并发劣势，go func 能够很不便的创立一个并发协程。那么，如果有一个全局的 map，在多个协程中并发操作 map 呢？能够这么操作吗？咱们写个小程序测试一下：
package main
import (
"fmt"
"time"
)
func main() {var m = make(map[string]int, 0)
// 创立 10 个协程
for i := 0; i <= 10; i ++ {go func() {
// 协程内，循环操作 map
for j := 0; j <= 100; j ++ {m[fmt.Sprintf("test_%v", j)] = j
}
}()}
// 主协程休眠 3 秒，否则主协程完结了，子协程没有机会执行
time.Sleep(time.Second * 3)
fmt.Println(m)
}运行之前能够猜一下执行后果。程序 panic 了，异样信息为：”fatal error: concurrent map writes”。很明确，并发写 map 导致的 panic，也就是说，咱们不能在多个协程并发执行 map 写操作，这一点要特地留神，首次写 Go 语言很容易犯这个错。
其实在函数 mapassign 很容易找到这些逻辑：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果并发写 map，报错
if h.flags&hashWriting != 0 {throw("concurrent map writes")
}
// 记录以后 map 正在执行写操作
h.flags ^= hashWriting
// 执行完结后，再次判断
done:
if h.flags&hashWriting == 0 {throw("concurrent map writes")
}
h.flags &^= hashWriting
}那如果的确想在多个协程并发操作 map 怎么办？这就须要采取其余计划了，比方加锁，比方应用并发平安 map（sync.Map），这些将在前面章节并发编程具体介绍。
总结
map 就介绍到这里了，要好好了解 Go 语言 map 根本构造，包含 buckets 数组，bmap 构造。map 在函数传参时的一些景象也不同于 slice，map 遍历的随机性也须要留神，而 map 并发拜访 panic 记得千万要防止。
