1. 什么是 map（词典）

在Golang中，map是一种内建的数据结构，用于存储无序的键值对集合。每个键在map中都是唯一的，对应的值可以是任意类型，但是key需要支持 == 操作。map 的特点是能够基于键快速检索数据。键就像是数组的索引一样，指向与键关联的值。

2. map 的创建与初始化

2.1使用字面量声明 map

只声明，不赋值：

m := map[int]string{}

这里，我们显式初始化了 map 类型变量 m。不过，此时 map 类型变量 m 中没有任何键值对，但变量 m 也不等同于初值为 nil 的 map 变量。这个时候，我们对 m 进行键值对的插入操作，不会引发运行时异常。

声明+赋值：

// 创建一个映射，键和值的类型都是 string
// 使用两个键值对初始化映射
myMap := map[string]string{
    "Red": "#da1337", 
    "Orange": "#e95a22"
}

创建 map 时，更常用的方法是使用 map 字面量。map 的初始长度会根据初始化时指定的键值对的数量来确定。

2.2 使用 make 函数声明映射

和切片通过 make 进行初始化一样，通过 make 的初始化方式，我们可以为 map 类型变量指定键值对的初始容量，但无法进行具体的键值对赋值

m1 := make(map[int]string) // 未指定初始容量
m2 := make(map[int]string, 8) // 指定初始容量为8

不过，map 类型的容量不会受限于它的初始容量值，当其中的键值对数量超过初始容量后，Go 运行时会自动增加 map 类型的容量，保证后续键值对的正常插入。

2.3 注意点

只声明不初始化会报错。 我们可以这样声明一个 map 变量：

var m map[string]int // 一个map[string]int类型的变量

和切片类型变量一样，如果我们没有显式地赋予 map 变量初值，map 类型变量的默认值为 nil。

不过切片变量和 map 变量在这里也有些不同。初值为零值 nil 的切片类型变量，可以借助内置的 append 的函数进行操作，这种在 Go 语言中被称为“零值可用”。定义“零值可用”的类型，可以提升我们开发者的使用体验，我们不用再担心变量的初始状态是否有效。

但 map 类型，因为它内部实现的复杂性，无法“零值可用”。 所以，如果我们对处于零值状态的 map 变量直接进行操作，就会导致运行时异常（panic），从而导致程序进程异常退出

这里和 slice 对一下对比：切片类型也不是在所有场景下都是零值可用的。

var sl []int
sl[0] = 13 // panic

sl = append(sl, 13) // ok

但 map 没有 append，只有 m[k]=v，这样当 map 变量没有初始化的时候，只能 panic。所谓它内部实现的复杂性，就是 go 没有提供类似 append 的内置函数来支持零值的 map。

3. map 的基本操作

3.1 遍历 map

通过 for range 遍历 map 变量 m，每次迭代都会返回一个键值对，其中键存在于变量 k 中，它对应的值存储在变量 v 中。

// 创建一个映射，存储颜色以及颜色对应的十六进制代码
myColors := map[string]string{
    "AliceBlue":"#f0f8ff",
    "Coral":"#ff7F50",
    "DarkGray":"#a9a9a9",
    "ForestGreen": "#228b22",
}

// 显示映射里的所有颜色
for key, value := range myColors {
    fmt.Printf("Key: %s  Value: %s\n", key, value)
}

如果我们只关心每次迭代的键，我们可以使用下面的方式对 map 进行遍历：

for k, _ := range m { 
  // 使用k
}

// 下面这种也可以
for k := range m { 
    // 使用k
}

不过需要特别注意：程序逻辑千万不要依赖遍历 map 所得到的的元素次序。

对同一 map 做多次遍历的时候，每次遍历元素的次序都不相同。这是 Go 语言 map 类型的一个重要特点，也是很容易让 Go 初学者掉入坑中的一个地方。所以这里你一定要记住：程序逻辑千万不要依赖遍历 map 所得到的的元素次序。

为什么这么设计呢？ go 的 map 是 hashmap 所以其实放进去的东西本来就是无序的（当然可以理解成按照 hash 值排序），像一般（指不做特殊处理）的语言的 map 每次 range 都是固定的顺序，这就导致了一部分人会写出依赖于顺序的代码，这让 go 的作者很不开心，所以他决定遍历前随机找个桶开始，所以每次遍历顺序都不一样。（其实仔细观察你可以看到 key 的是旋转得到的，比如 12345 你只会得到如 34512 这样的 不会得到 54312 这种） Ref : www.zhihu.com/question/46…

3.2 获取某个 key 对应的 value

在 Go 语言中，请使用“comma ok”惯用法对 map 进行键查找和键值读取操作。

读 map 分为下面两种方式：

第一种方式是直接读，倘若 key 存在，则获取到对应的 val，倘若 key 不存在或者 map 未初始化，会返回 val 类型的零值作为兜底。

var m map[string]int
fmt.Println(m["age"]) // 输出0值:0   证明读不会panic
m["age"] = 100        // panic: assignment to entry in nil map 写会panic

第二种方式是读的同时添加一个 bool 类型的 flag 标识是否读取成功。 倘若 ok == false，说明读取失败， key 不存在，或者 map 未初始化。

var m map[string]int
val, ok := m["age"]
if ok {
    fmt.Println(val)
}
fmt.Println("age not exists") // 程序会打印这行

一般更推荐使用方式 2。

3.3插入键值对

写操作的语法如下：

// map 未初始化导致panic
var m map[string]int
m["age"] = 100        // panic: assignment to entry in nil map 写会panic


// 正确的使用方式
m := make(map[string]int, 0)
m["age"] = 100
val, ok := m["age"]
if ok {
    fmt.Println(val) // 输出100
}
fmt.Println("age not exists")

须注意的是：

• 倘若 map 未初始化，直接执行写操作会导致 panic
• 如果我们插入新键值对的时候，某个 key 已经存在于 map 中了，那我们的插入操作就会用新值覆盖旧值

3.4获取键值对数量。

如果我们在编码中，想知道当前 map 类型变量中已经建立了多少个键值对，那我们可以怎么做呢？和切片一样，map 类型也可以通过内置函数 len，获取当前变量已经存储的键值对数量：

m := make(map[string]int, 0)
m["age"] = 100
fmt.Println(len(m)) //1
m["cnt"] = 10
fmt.Println(len(m)) //2 

3.5 删除数据。

在 Go 中，我们需要借助内置函数 delete 来从 map 中删除数据。使用 delete 函数的情况下，传入的第一个参数是我们的 map 类型变量，第二个参数就是我们想要删除的键。

m := make(map[string]int, 0)
m["age"] = 100
m["cnt"] = 10
fmt.Println(len(m)) //2
delete(m, "cnt")
fmt.Println(len(m)) //1

这里要注意的是，delete 函数是从 map 中删除键的唯一方法。即便传给 delete 的键在 map 中并不存在，delete 函数的执行也不会失败，更不会抛出运行时的异常

3.6并发冲突

map 不是并发安全的数据结构，倘若存在并发读写行为，会抛出 fatal error。

具体规则是：

• 并发读没有问题；
• 并发读写中的“写”是广义上的，包含写入、更新、删除等操作；
• 读的时候发现其他 goroutine 在并发写，抛出 fatal error；
• 写的时候发现其他 goroutine 在并发写，抛出 fatal error。

m := make(map[string]int, 0)
m["age"] = 100
m["cnt"] = 10

// concurrent map read and map write
for {
    go func() {
       fmt.Println(m["age"])
       m["cnt"] = 10
    }()
}

需要关注，此处并发读写会引发 fatal error，是一种比 panic 更严重的错误，无法使用 recover 操作捕获。

4. 核心原理

4.1 底层数据结构

golang map 底层由两个核心的结构体实现：hmap 和 bmap

4.1.1 hmap

 // A header for a Go map.
type hmap struct {
  // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
 // Make sure this stays in sync with the compiler's definition.
count     int // # live cells == size of map.  Must be first (used by len() builtin)
flags     uint8
  B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0     uint32 // hash seed

buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

extra *mapextra // optional fields
}

• count： 代表 map 中使用元素的数量。len（m） 返回的就是 count 的值

m := make(map[string]int, 10)
m["a"] = 1
fmt.Println(len(m)) // 输出1

• flags：用于标记当前 map 是否处于写状态。如果 map 在执行读写操作时，发现当前 flags 标记为正在写，则抛出 fatal panic，并且这里的 panic 无法 recover。原因是这时候 map 中的数据已经是脏数据了，即使 recover 也无法提供正确的数据了。
• B：标记 map 中桶的数量。如果 B = 1，桶的个数为 2；如果 B = 3， 桶数量为 8。
• noverflow: overflow 的 bucket 近似数。map 在写操作时会判断如果 overflow 的桶过多，也会触发扩容。这里下面在介绍 map 的扩容机制时会详细介绍。
• hash0: hash 散列种子，用于 hash 函数计算 key 应该存储在几号桶。
• buckets：指向 buckets 数组，大小为 2^B；如果元素个数为 0，就为 nil
• oldbuckets: 扩容期间使用，map 在扩容期间需要将数据从 oldbuckets 中移动到 buckers 中。
• nevacutae：扩容阶段使用，指示扩容进度，小于此地址的 buckets 迁移完成。
• extra：额外的信息，供扩展使用。

4.1.2 bmap

hmap 中的 buckets 指向的是 map 的桶数组，其中数组中 bucket 数组实际存储结构为 bmap

 // A bucket for a Go map.
type bmap struct {
  // tophash generally contains the top byte of the hash value
 // for each key in this bucket. If tophash[0] < minTopHash,
 // tophash[0] is a bucket evacuation state instead.
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.
}

Tophash:

tophash 是一个长度为 8 的数组，它不仅仅用来存放 key 的哈希高 8 位，在不同场景下它还可以标记迁移状态，bucket 是否为空等。事实上，TopHash 是 map 中非常重要的一个设计，详情见： blog.csdn.net/fengshenyun…

• 如果 tophash 的值小于 5，则代表当前位置元素的状态：

  • 该 tophash 对应的 K/V 位置以及后面的位置是否是可用的
  • 记录扩容迁移信息：该元素迁移到新桶的 index 与 old buckets 相同，还是迁移后的 index = buckets size + index（为什么需要记录这个信息详见上面的博客）
  • 该 bucket 是否全部迁移完成

• 如果 tophash 的值大于 5，则代表当前元素的 hash 值（这里只是为了方便理解，其实不准确，详见上面的博客）。

但这只是表面（src/runtime/hashmap.go）的结构，编译期间最终会生成如下格式：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 即我们常说的桶。一个桶中可以存储 8 个键值对： 其中 keys 数组存储 8 个 key，values 数组存储 8 个 value。如果该桶元素大于 8 个键值对，则通过 overflow 指针拉出新的 bmap bucket，在附加桶上继续存储。

注意： Golang 的 map 与 java 的 map 在这里存储方式上有个很大的区别： go 语言中，一个 bucket 允许存储 8 个键值对，而 java 中的一个 bucket 最多存储一个键值对。

Golang 这么设计的原因是因为 bucket 中存储 8 个键值对，内存地址完全连续，可以基于局部性原理，充分利用 CPU 高速缓存。

具体可参考博客： blog.csdn.net/qq_39383767…

4.2 Hash 冲突

首先，由于 hash 冲突的存在，不同 key 可能存在相同的 hash 值；再者，hash 值会对桶数组长度取模，因此不同 hash 值可能被打到同一个桶中。综上，不同的 key-value 可能被映射到 map 的同一个桶当中。此时的解决手段分为两种：拉链法和开放寻址法：

方法	原理	优点
拉链法	拉链法中，将命中同一个桶的元素通过链表的形式进行链接，因此很便于动态扩展。	简单常用；无需预先为元素分配内存。
开放寻址法	开放寻址法中，在插入新条目时，会基于一定的探测策略持续寻找，直到找到一个可用于存放数据的空位为止。	无需额外的指针用于链接元素；内存地址完全连续，可以基于局部性原理，充分利用 CPU 高速缓存。

在 map 解决 hash /分桶 冲突问题时，实际上结合了拉链法和开放寻址法两种思路。 以 map 的插入写流程为例，进行思路阐述：

1. 桶数组中的每个桶，严格意义上是一个单向桶链表，以桶为节点进行串联；
2. 每个桶固定可以存放 8 个 key-value 对；
3. 当 key 命中一个桶时，首先根据开放寻址法，在桶的 8 个位置中寻找空位进行插入；
4. 倘若桶的 8 个位置都已被占满，则基于桶的溢出桶指针，找到下一个桶，重复第（3）步；
5. 倘若遍历到链表尾部，仍未找到空位，则基于拉链法，在桶链表尾部续接新桶，并插入 key-value 对。

4.3 扩容

ref: blog.csdn.net/weixin_5269…

4.3.1为什么要扩容

1. 如果 map 的溢出桶数量过多，则 map 查找复杂度将退化为链表查询。而链表查询的时间复杂度为 O（n）。因此我们需要扩容让元素尽可能的平均分配到每个 bucket 中，同时溢出桶的数量尽可能少。
2. 虽然 map 的溢出桶数量不多，但是当装载因子超过 6.5 时，表明很多 bucket 都快要装满了。我们在往 bucket 中存放元素时需要开放寻址的时间将会增加，而且大概率可能需要拉出溢出桶了。所以这个时候也需要扩容。

4.3.2 扩容策略

等量扩容：对应 overflow 的 bucket 数量过多

1. 当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；

2. 当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。

对于这种情况， 其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间（size 与 原桶数组相等），将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率。

增量扩容：

• 负载因子（ 元素个数 / 桶数量）大于 6.5

• 扩容方式：将桶数量 2 倍扩容。bucket 最大数量（2^B）直接变成原来 bucket 数量的 2 倍。然后将元素逐步从 old buckets 迁移到 new buckets 中

注意点：需要渐进式扩容

4.3.3 渐进式扩容

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为 “渐进式” 地方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

下面重点讲解下增量扩容流程。

4.3.3.1 何时扩容

执行mapassign （对应map的更新、写入）操作时会判断是否需要开启扩容。如果需要扩容，则会执行如下操作：

1. 将map的buckets指针赋值给oldBuckets
2. 创建新的buckets数组，并且buckets指针指向新建的数组
3. 给nevacuate复制为0
4. 更新flags标识为增量扩容，更新B的值

4.3.3.2 渐进式扩容

所谓的渐进式扩容即元素不会一次性全部搬迁完成。

map的数组搬迁时机为：每次触发写、删操作时，会为处于扩容流程中的 map 完成两组桶的数据迁移。

• 一组桶是当前写、删操作所命中的桶。
• 另一组桶是，当前未迁移的桶中，索引最小的那个桶。

注：如果当前写操作命中的桶即为索引最小的桶，则本次只会迁移1个桶，因此map的渐进式迁移一次最多迁移2个桶。

func growWork(t *maptype, h *hmap, bucket uintptr) {
  // make sure we evacuate the oldbucket corresponding
 // to the bucket we're about to use
evacuate(t, h, bucket&h.oldbucketmask())

  // evacuate one more oldbucket to make progress on growing
if h.growing() {
   evacuate(t, h, h.nevacuate)
  }
}

每次迁移时，会先判断当前bucket迁移状态：

• 如果已经全部迁移完成，则跳过该桶。
• 如果未迁移，则将该桶的所有元素全部完成迁移。如果本次迁移的桶数组 = nevacuate（待迁移索引最小的桶），则nevacuate++

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
  newbit := h.noldbuckets()
  if !evacuated(b) {
      // 执行迁移
  }

  // 如果本次迁移的桶数组 = nevacuate（待迁移索引最小的桶），则nevacuate++
  if oldbucket == h.nevacuate {
  // h.nevacuate++
   advanceEvacuationMark(h, t, newbit)
  }
}

5.线程安全的 sync.map

golang的map 并不是现成安全的，如果需要并发读写，请使用sync.map

sync.map

1. Golang map 与 java map，redis map 的对比

参考资料

mp.weixin.qq.com/s/PT1zpv3bv…