前段时间听了大佬们对于 map 的讲解，结合自己之前的积累，专门来由浅入深的总结一下，希望可以与 map 之间做一个了断。

文章的深浅顺序是递进的，当你看完这篇文章，你也基本掌握了 map 的 99% 的知识点了，可以装逼和吹牛逼了。

1.map 的基本使用

1.1 声明 & 默认值

  1. // 声明
  2. var m map[string]string
  3. 复制代码

map 的声明的时候默认值是nil ，此时进行取值，返回的是对应类型的零值（不存在也是返回零值）。

例子：

  1. // bool 的零值是false
  2. var m map[int]bool 
  3. a, ok := m[1]
  4. fmt.Println(a, ok) // false  false
  6. // int 的零值是0
  7. var m map[int]int 
  8. a, ok := m[1]
  9. fmt.Println(a, ok) // 0  false
  10. 复制代码

1.2 初始化

  1. // 声明之后必须初始化，才能使用
  2. m = make(map[string]int)
  3. m = map[string]int{}
  5. // 声明并初始化 <= 注意这里是 := 不是 =
  6. m := make(map[string]int)
  7. m := map[string]int{1:1}
  8. 复制代码

向未初始化的 map 赋值引起 panic: assign to entry in nil map.

1.3key 与 value 的限制

key 一定要是可比较的类型（可以理解为支持 == 的操作）：

可比较类型 不可比较类型
boolean slice
numeric map
string func
pointer
channel
interface
包含前文类型的 array 和 struct

如果是非法的 key 类型，会报错：invalid map key type xxx。

golang 为 uint32、uint64、string 提供了 fast access，使用这些类型作为 key 可以提高 map 访问速度。[runtime/hashmap_fast.go]

value 可以是任意类型。

1.4 新增 & 删除 & 更新 & 查询

  1. // 新增
  2. m["name"] = "咖啡色的羊驼"
  4. // 删除，key不存在则啥也不干
  5. delete(m, "name")
  7. // 更新
  8. m["name"] = "咖啡色的羊驼2"
  10. // 查询，key不存在返回value类型的零值
  11. i := m["name"] // 三种查询方式，
  12. i, ok := m["name"]
  13. _, ok := m["name"]
  14. 复制代码

1.5 遍历

需要强调的是 map 本身是无序的，在遍历的时候并不会按照你传入的顺序，进行传出。

正常遍历：

  1. for k, v := range m { 
  2.     fmt.Println(k, v)
  3. }
  4. 复制代码

有序遍历：

  1. import "sort"
  2. var keys []string
  3. // 把key单独抽取出来，放在数组中
  4. for k, _ := range m {
  5.     keys = append(keys, k)
  6. }
  7. // 进行数组的排序
  8. sort.Strings(keys)
  9. // 遍历数组就是有序的了
  10. for _, k := range keys {
  11.     fmt.Println(k, m[k])
  12. }
  13. 复制代码

1.6 函数传参

Golang 中是没有引用传递的，均为值传递。这意味着传递的是数据的拷贝。 那么 map 本身是引用类型，作为形参或返回参数的时候，传递的是地址的拷贝，扩容时也不会改变这个地址。

  1. var m map[int64]int64
  2. m = make(map[int64]int64, 1)
  3. fmt.Printf("m 原始的地址是：%p\n", m)
  4. changeM(m)
  5. fmt.Printf("m 改变后地址是：%p\n", m)
  6. fmt.Println("m 长度是", len(m))
  7. fmt.Println("m 参数是", m)
  9. // 改变map的函数
  10. func changeM(m map[int64]int64) {
  11.     fmt.Printf("m 函数开始时地址是：%p\n", m)
  12.     var max = 5
  13.     for i := 0; i < max; i++ {
  14.         m[int64(i)] = 2
  15.     }
  16.     fmt.Printf("m 在函数返回前地址是：%p\n", m)
  17. }
  18. 复制代码

输出：

  1. m 原始地址是：0xc42007a180
  2. m 函数开始时地址是：0xc42007a180
  3. m 在函数返回前地址是：0xc42007a180
  4. m 改变后地址是：0xc42007a180
  5. m 长度是 5
  6. m 参数是  map[3:2 4:2 0:2 1:2 2:2]
  7. 复制代码

2.map 的深入了解

2.1map 的基础数据结构 & 图

  1. type hmap struct {
  2.     count        int  //元素个数
  3.     flags        uint8   
  4.     B            uint8 //扩容常量
  5.     noverflow    uint16 //溢出 bucket 个数
  6.     hash0        uint32 //hash 种子
  7.     buckets      unsafe.Pointer //bucket 数组指针
  8.     oldbuckets   unsafe.Pointer //扩容时旧的buckets 数组指针
  9.     nevacuate    uintptr  //扩容搬迁进度
  10.     extra        *mapextra //记录溢出相关
  11. }
  13. type bmap struct {
  14.     tophash        [bucketCnt]uint8  
  15.     // Followed by bucketCnt keys 
  16.     //and then bucketan Cnt values  
  17.     // Followed by overflow pointer.
  18. }
  19. 复制代码

说明：每个 map 的地层结构是 hmap，是有若干个机构为 bmap 的 bucket 组成的数组，每个 bucket 可以存放若干个元素 (通常是 8 个)，那么每个 key 会根据 hash 算法归到同一个 bucket 中，当一个 bucket 中的元素超过 8 个的时候，hmap 会使用 extra 中的 overflow 来扩展存储 key。

来一个图，方便记忆：

由浅入深聊聊Golang的map - 图1

2.2map 的 hash 值计算

那么具体 key 是分配到哪个 bucket 呢？也就是 bmap 中的 tophash 是如何计算？

golang 为每个类型定义了类型描述器_type，并实现了 hashable 类型的_type.alg.hash 和_type.alg.equal

  1. type typeAlg struct {
  2.     // function for hashing objects of this type
  3.     // (ptr to object, seed) -> hash
  4.     hash func(unsafe.Pointer, uintptr) uintptr
  5.     // function for comparing objects of this type
  6.     // (ptr to object A, ptr to object B) -> ==?
  7.     equal func(unsafe.Pointer, unsafe.Pointer) bool
  8. 复制代码

具体实现文件：go/1.10.3/libexec/src/runtime/hashmap.go:

  1. // tophash calculates the tophash value for hash.
  2. func tophash(hash uintptr) uint8 {
  3.     top := uint8(hash >> (sys.PtrSize*8 - 8))
  4.     if top < minTopHash {
  5.         top += minTopHash
  6.     }
  7.     return top
  8. }
  9. 复制代码

2.3map 的查找

具体实现文件：go/1.10.3/libexec/src/runtime/hashmap.go:

  1. // mapaccess1 returns a pointer to h[key].  Never returns nil, instead
  2. // it will return a reference to the zero object for the value type if
  3. // the key is not in the map.
  4. // NOTE: The returned pointer may keep the whole map live, so don't
  5. // hold onto it for very long.
  6. func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  7.     ...
  8.     // 并发访问检查
  9.     if h.flags&hashWriting != 0 {
  10.         throw("concurrent map read and map write")
  11.     }
  13.     // 计算key的hash值
  14.     alg := t.key.alg
  15.     hash := alg.hash(key, uintptr(h.hash0)) // alg.hash
  17.     // hash值对m取余数得到对应的bucket
  18.     m := uintptr(1)<<h.B - 1
  19.     b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  21.     // 如果老的bucket还没有迁移，则在老的bucket里面找
  22.     if c := h.oldbuckets; c != nil {
  23.         if !h.sameSizeGrow() {
  24.             m >>= 1
  25.         }
  26.         oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
  27.         if !evacuated(oldb) {
  28.             b = oldb
  29.         }
  30.     }
  32.     // 计算tophash，取高8位
  33.     top := uint8(hash >> (sys.PtrSize*8 - 8))
  35.     for {
  36.         for i := uintptr(0); i < bucketCnt; i++ {
  37.             // 检查top值，如高8位不一样就找下一个
  38.             if b.tophash[i] != top {
  39.                 continue
  40.             }
  42.             // 取key的地址
  43.             k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
  45.             if alg.equal(key, k) { // alg.equal
  46.                 // 取value得地址
  47.                 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
  48.             }
  49.         }
  51.         // 如果当前bucket没有找到，则找bucket链的下一个bucket
  52.         b = b.overflow(t)
  53.         if b == nil {
  54.             // 返回零值
  55.             return unsafe.Pointer(&zeroVal[0])
  56.         }
  57.     }
  58. }
  59. 复制代码

2.4map 的更新 / 插入过程

  1. // Like mapaccess, but allocates a slot for the key if it is not present in the map.
  2. func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  4.     // 如果已经达到了load factor的最大值，那我们就继续开始扩容
  5.     if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  6.         hashGrow(t, h)
  7.         goto again 
  8.     }
  10.     if inserti == nil {
  11.         // burrent满了的话，需要申请一个新的
  12.         newb := h.newoverflow(t, b)
  13.         inserti = &newb.tophash[0]
  14.         insertk = add(unsafe.Pointer(newb), dataOffset)
  15.         val = add(insertk, bucketCnt*uintptr(t.keysize))
  16.     }
  18.     // 在插入的位置，存储键值
  19.     if t.indirectkey {
  20.         kmem := newobject(t.key)
  21.         *(*unsafe.Pointer)(insertk) = kmem
  22.         insertk = kmem
  23.     }
  24.     if t.indirectvalue {
  25.         vmem := newobject(t.elem)
  26.         *(*unsafe.Pointer)(val) = vmem
  27.     }
  28.     typedmemmove(t.key, insertk, key)
  29.     *inserti = top
  30.     h.count++
  31. }
  32. 复制代码

2.5map 的删除过程

  1. func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
  2.     // 找key
  3.    。。。
  4.     // 若找到把对应的tophash里面的打上空的标记
  5.     b.tophash[i] = empty
  6.     h.count--
  7. }
  8. 复制代码

2.6map 的扩容机制

map 判断扩容的函数：

  1. // overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
  2. func overLoadFactor(count int, B uint8) bool {
  3.     // 注意这里有一个loadFactorNum/loadFactorDen
  4.     return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
  5. }
  7. func bucketShift(b uint8) uintptr {
  8.     if sys.GoarchAmd64|sys.GoarchAmd64p32|sys.Goarch386 != 0 {
  9.         b &= sys.PtrSize*8 - 1 // help x86 archs remove shift overflow checks
  10.     }
  11.     return uintptr(1) << b
  12. }
  13. 复制代码

每次 map 进行更新或者新增的时候，会先通过以上函数判断一下 load factor。来决定是否扩容。

扩容白话文：如果之前为 2^n ，那么下一次扩容是 2^(n+1), 每次扩容都是之前的两倍。扩容后需要重新计算每一项在 hash 中的位置，新表为老的两倍，此时前文的 oldbacket 用上了，用来存同时存在的两个心就 map，等数据迁移完毕就可以释放 oldbacket 了

好处：均摊扩容时间，一定程度上缩短了扩容时间（是不是和 gc 的引用计数法有点像，都是均摊～）

那么 overLoadFactor 函数中有一个常量 6.5（loadFactorNum/loadFactorDen）来进行影响扩容时机。这个值的来源是测试取中的结果。

  1.   loadFactor    %overflow  bytes/entry     hitprobe    missprobe
  2.         4.00         2.13        20.77         3.00         4.00
  3.         4.50         4.05        17.30         3.25         4.50
  4.         5.00         6.85        14.77         3.50         5.00
  5.         5.50        10.55        12.94         3.75         5.50
  6.         6.00        15.27        11.67         4.00         6.00
  7.         6.50        20.90        10.79         4.25         6.50
  8.         7.00        27.14        10.15         4.50         7.00
  9.         7.50        34.03         9.73         4.75         7.50
  10.         8.00        41.10         9.40         5.00         8.00
  11. 复制代码
字段 说明
%overflow 溢出率，平均一个 bucket 有多少个 kv 的时候会溢出
bytes/entry 平均存一个 kv 需要额外存储多少字节的数据
hitprobe 找到一个存在的 key 平均需要找几下
missprobe 找到一个不存在的 key 平均需要找几下

3. 并发中的 map

3.1 安全性

这里呢，实现一个小功能来证明下并发不是安全的。 并发起两个 goroutine，分别对 map 进行数据的增加

  1. func main() {
  2.     test := map[int]int {1:1}
  3.     go func() {
  4.         i := 0
  5.         for i < 10000 {
  6.             test[1]=1
  7.             i++
  8.         }
  9.     }()
  11.     go func() {
  12.         i := 0
  13.         for i < 10000 {
  14.             test[1]=1
  15.             i++
  16.         }
  17.     }()
  19.     time.Sleep(2*time.Second)
  20.     fmt.Println(test)
  21. }
  23. 复制代码

会发现有这样的报错：

  1. fatal error: concurrent map read and map write
  2. 复制代码

根本原因就是：并发的去读写 map 结构的数据了。

3.2 处理方案 & 优缺点

那解决方案就是加锁。上代码

  1. func main() {
  2.     test := map[int]int {1:1}
  3.     var s sync.RWMutex
  4.     go func() {
  5.         i := 0
  6.         for i < 10000 {
  7.             s.Lock()
  8.             test[1]=1
  9.             s.Unlock()
  10.             i++
  11.         }
  12.     }()
  14.     go func() {
  15.         i := 0
  16.         for i < 10000 {
  17.             s.Lock()
  18.             test[1]=1
  19.             s.Unlock()
  20.             i++
  21.         }
  22.     }()
  24.     time.Sleep(2*time.Second)
  25.     fmt.Println(test)
  26. }
  27. 复制代码

优点：实现简单粗暴，好理解 缺点：锁的粒度为整个 map，存在优化空间 适用场景：all

3.3 官方处理方案 & 优缺点

想一想，在程序设计中，想增加运行的速度，那么必然要有另外的牺牲，很容易想到 “空间换时间” 的方案，现在来实战体验一把。

  1. func main() {
  2.     test := sync.Map{}
  3.     test.Store(1, 1)
  4.     go func() {
  5.         i := 0
  6.         for i < 10000 {
  7.             test.Store(1, 1)
  8.             i++
  9.         }
  10.     }()
  12.     go func() {
  13.         i := 0
  14.         for i < 10000 {
  15.             test.Store(1, 1)
  16.             i++
  17.         }
  18.     }()
  20.     time.Sleep(time.Second)
  21.     fmt.Println(test.Load(1))
  22. }
  23. 复制代码

运行完呢，会发现，其实是不会报错的。因为 sync.Map 里头已经实现了一套加锁的机制，让你更方便地使用 map。

sync.Map 的原理介绍：sync.Map 里头有两个 map 一个是专门用于读的 read map，另一个是才是提供读写的 dirty map；优先读 read map，若不存在则加锁穿透读 dirty map，同时记录一个未从 read map 读到的计数，当计数到达一定值，就将 read map 用 dirty map 进行覆盖。

优点：是官方出的，是亲儿子；通过空间换时间的方式；读写分离； 缺点：不适用于大量写的场景，这样会导致 read map 读不到数据而进一步加锁读取，同时 dirty map 也会一直晋升为 read map，整体性能较差。 适用场景：大量读，少量写

3.4 额外的处理机制

想一想，mysql 加锁，是不是有表级锁、行级锁，前文的 sync.RWMutex 加锁方式相当于表级锁。

而 sync.Map 其实也是相当于表级锁，只不过多读写分了两个 map，本质还是一样的。

既然这样，那就自然知道优化方向了：就是把锁的粒度尽可能降低来提高运行速度。

思路：对一个大 map 进行 hash，其内部是 n 个小 map，根据 key 来来 hash 确定在具体的那个小 map 中，这样加锁的粒度就变成 1/n 了。 网上找了下，真有大佬实现了：点这里

4.map 的 gc 回收机制

4.1 实战代码 && 处理机制

我们知道呢，map 在 golang 里头是只增不减的一种数组结构，他只会在删除的时候进行打标记说明该内存空间已经 empty 了，不会回收的。

show my code，no bb:

  1. var intMap map[int]int
  3. func main() {
  4.     printMemStats("初始化")
  6.     // 添加1w个map值
  7.     intMap = make(map[int]int, 10000)
  8.     for i := 0; i < 10000; i++ {
  9.         intMap[i] = i
  10.     }
  12.     // 手动进行gc操作
  13.     runtime.GC()
  14.     // 再次查看数据
  15.     printMemStats("增加map数据后")
  17.     log.Println("删除前数组长度：", len(intMap))
  18.     for i := 0; i < 10000; i++ {
  19.         delete(intMap, i)
  20.     }
  21.     log.Println("删除后数组长度：", len(intMap))
  23.     // 再次进行手动GC回收
  24.     runtime.GC()
  25.     printMemStats("删除map数据后")
  27.     // 设置为nil进行回收
  28.     intMap = nil
  29.     runtime.GC()
  30.     printMemStats("设置为nil后")
  31. }
  33. func printMemStats(mag string) {
  34.     var m runtime.MemStats
  35.     runtime.ReadMemStats(&m)
  36.     log.Printf("%v：分配的内存 = %vKB, GC的次数 = %v\n", mag, m.Alloc/1024, m.NumGC)
  37. }
  38. 复制代码

会输出：

  1. 初始化：分配的内存 = 65KB, GC的次数 = 0
  2. 增加map数据后：分配的内存 = 381KB, GC的次数 = 1
  3. 删除前数组长度： 10000
  4. 删除后数组长度： 0
  5. 删除map数据后：分配的内存 = 381KB, GC的次数 = 2
  6. 设置为nil后：分配的内存 = 68KB, GC的次数 = 3
  7. 复制代码

很明显可以看到 delete 是不会真正的把 map 释放的，所以要回收 map 还是需要设为 nil

由浅入深聊聊Golang的map - 图2
https://juejin.cn/post/6844904078636482574