映射是一种数据结构，用于存储一系列无序的键值对。

映射是一个集合，可以使用类似处理数组和切片的方式迭代，但映射是无序的集合，每次迭代映射的时候顺序也可能不一样。

1.使用

func testCreate() {
    colors := make(map[string]string) //创建一个空映射
    colors["Red"] = "#da1337"         //赋值
    fmt.Println(colors)

    //var colors2 map[string]string
    //colors2["Red"] = "#da1337" //error

    value, ok := colors["Blue"] //判断键是否存在
    if ok {
        fmt.Println(value)
    }

    value = colors["Blue"] //判断读取到的值是否空值
    if value != "" {
        fmt.Println(value)
    }
}

func removeColor(colors map[string]string, key string) {
    delete(colors, key)
}

func testRemove() {
    colors := map[string]string{
        "AliceBlue": "#f0f8ff",
        "Coral":     "#ff7F50",
    }

    for key, value := range colors {
        fmt.Printf("Key: %s Value: %s\n", key, value)
    }
    fmt.Println("----------------")

    removeColor(colors, "Coral")

    for key, value := range colors {
        fmt.Printf("Key: %s Value: %s\n", key, value)
    }
}

输出结果：

map[Red:#da1337]
----------------
Key: Coral Value: #ff7F50
Key: AliceBlue Value: #f0f8ff
----------------
Key: AliceBlue Value: #f0f8ff

2.内存数据结构源码

src/runtime/map.go

type hmap struct {
 count     int       //元素个数
 flags     uint8     //标记位
 B         uint8     //buckets的对数 log_2
 noverflow uint16    //overflow的bucket的近似数
 hash0     uint32    //hash种子
 buckets    unsafe.Pointer //指向buckets数组的指针，数组个数为2^B
 oldbuckets unsafe.Pointer //扩容时使用，buckets长度是oldbuckets的两倍
 nevacuate  uintptr  //扩容进度，小于此地址的buckets已经迁移完成
 extra *mapextra     //扩展信息
}

//当map的key和value都不是指针，并且size都小于128字节的情况下，
// 会把 bmap 标记为不含指针，这样可以避免gc时扫描整个hmap。
// 但是，我们看bmap其实有一个overflow的字段，是指针类型的，
// 破坏了bmap不含指针的设想，这时会把overflow移动到extra字段来。
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap
 nextOverflow *bmap
}

// bucket
type bmap struct {
 tophash [bucketCnt]uint8 //bucketCnt = 8
 // keys     [8]keytype
 // values   [8]valuetype
 // pad      uintptr
 // overflow uintptr
}

bmap就是桶的数据结构，每个桶最多存储8个key-value对，所有的key都是经过hash后有相同的尾部，在桶内，根据hash值的高8位来决定桶中的位置。

注意到key和value是各自在一起的，不是key/value/key/value/...的方式，这样的好处是某些情况下可以省略padding字段，节省内存空间

如map[int64]int8，按照key/value/key/value/... 这样的模式存储，每一个key/value对之后都要额外 padding7个字节；而将所有的key，value 分别绑定到一起，key/key/.../value/value/...，只需在最后添加padding。

每个bucket设计成最多只能放8个key-value对，如果有第9个 key-value落入当前的bucket，那就需要再构建一个bucket，通过overflow指针连接起来。

编译期间会给它加料，动态地创建一个新的结构

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

3.初始化

底层调用makemap函数，计算得到合适的B，map容量最多可容纳6.5*2^B个元素，6.5为装载因子阈值常量。装载因子的计算公式是：装载因子=填入表中的元素个数/散列表的长度，装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

func makemap(t *maptype, hint int, h *hmap) *hmap {
//边界校验
  if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
    hint = 0
  }

// initialize Hmap
  if h == nil {
    h = new(hmap)
  }
//生成hash种子
  h.hash0 = fastrand()

  // find size parameter which will hold the requested # of elements
  B := uint8(0)
//计算得到合适的B
  for overLoadFactor(hint, B) {
    B++
  }
  h.B = B

  // allocate initial hash table
  // if B == 0, the buckets field is allocated lazily later (in mapassign)
  // If hint is large zeroing this memory could take a while.
//申请桶空间  
if h.B != 0 {
    var nextOverflow *bmap
    h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
    if nextOverflow != nil {
      h.extra = new(mapextra)
      h.extra.nextOverflow = nextOverflow
    }
  }

  return h
}
//常量loadFactorNum=13 ，loadFactorDen=2
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)

makemap函数会通过 fastrand 创建一个随机的哈希种子，然后根据传入的 hint 计算出需要的最小需要的桶的数量，最后再使用 makeBucketArray创建用于保存桶的数组，这个方法其实就是根据传入的 B 计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据，在创建桶的过程中还会额外创建一些用于保存溢出数据的桶，数量是 2^(B-4) 个。初始化完成返回hmap指针。

4.查找

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

value := m["name"]
fmt.Printf("value:%s", value)

value, ok := m["name"]
  if ok {
    fmt.Printf("value:%s", value)
  }

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

查找过程：

• step1.key 经过哈希计算后得到哈希值，共 64 个 bit 位。计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。
• step2.再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。

• step3.如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

  
  

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  //...
  // 如果 h 什么都没有，返回零值
  if h == nil || h.count == 0 {
    return unsafe.Pointer(&zeroVal[0])
  }
  // 写和读冲突
  if h.flags&hashWriting != 0 {
    throw("concurrent map read and map write")
  }
  // 不同类型 key 使用的 hash 算法在编译期确定
  alg := t.key.alg
  // 计算哈希值，并且加入 hash0 引入随机性
  hash := alg.hash(key, uintptr(h.hash0))
  // 比如 B=5，那 m 就是31，二进制是全 1
  // 求 bucket num 时，将 hash 与 m 相与，
  // 达到 bucket num 由 hash 的低 8 位决定的效果
  m := bucketMask(h.B)
  // b 就是 bucket 的地址
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // oldbuckets 不为 nil，说明发生了扩容
  if c := h.oldbuckets; c != nil {
    // 如果不是同 size 扩容（看后面扩容的内容）
    // 对应条件 1 的解决方案
    if !h.sameSizeGrow() {
      // 新 bucket 数量是老的 2 倍
      m >>= 1
    }
    // 求出 key 在老的 map 中的 bucket 位置
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    // 如果 oldb 没有搬迁到新的 bucket
    // 那就在老的 bucket 中寻找
    if !evacuated(oldb) {
      b = oldb
    }
  }
  // 计算出高 8 位的 hash
  // 相当于右移 56 位，只取高8位
  top := tophash(hash)
  //开始寻找key
  for ; b != nil; b = b.overflow(t) {
    // 遍历 8 个 bucket
    for i := uintptr(0); i < bucketCnt; i++ {
      // tophash 不匹配，继续
      if b.tophash[i] != top {
        continue
      }
      // tophash 匹配，定位到 key 的位置
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      // key 是指针
      if t.indirectkey {
        // 解引用
        k = *((*unsafe.Pointer)(k))
      }
      // 如果 key 相等
      if alg.equal(key, k) {
        // 定位到 value 的位置
        v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
        // value 解引用
        if t.indirectvalue {
          v = *((*unsafe.Pointer)(v))
        }
        return v
      }
    }
  }
  return unsafe.Pointer(&zeroVal[0])
}

5.赋值操作（插入操作）

m := make(map[int32]int32)
m[0] = 6666666

源码是：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

具体流程：

• step1.校验和初始化。判断 buckets 是否为 nil，若是则调用 newobject 根据当前 bucket 大小进行分配
• step2.寻找可插入位和更新既有值。若满足三个条件：触发最大 LoadFactor 、存在过多溢出桶 overflow buckets、当前不在扩容。就会进行扩容动作（以确保后续的动作）
• step3.申请新的插入位和插入新值。经过前面迭代寻找动作，若没有找到可插入的位置，意味着当前的所有桶都满了，将重新分配一个新溢出桶用于插入动作。最后再在上一步申请的新插入位置，存储键值对，返回该值的内存地址
• step4.最后返回的是内存地址。是怎么进行写入的呢？这是因为隐藏的最后一步写入动作（将值拷贝到指定内存区域）是通过底层汇编配合来完成的，在 runtime 中只完成了绝大部分的动作。

6.扩容

6.1 bucket状态

// 空的 cell，也是初始时 bucket 的状态
empty  = 0

// 空的 cell，表示 cell 已经被迁移到新的 bucket
evacuatedEmpty = 1

// key,value 已经搬迁完毕，但是 key 都在新 bucket 前半部分，
evacuatedX  = 2

// 同上，key 在后半部分
evacuatedY  = 3

// tophash 的最小正常值
minTopHash  = 4

为了避免计算出的topHash与minTopHash 冲突，底层做了相关操作：

func tophash(hash uintptr) uint8 {
  top := uint8(hash >> (sys.PtrSize*8 - 8))
  if top < minTopHash {
    top += minTopHash
  }
  return top
}

当一个 cell 的 tophash 值小于 minTopHash 时，标志这个 cell 的迁移状态。

6.2 触发 map 扩容的时机

装载因子。loadFactor := count/(2^B)

count 就是 map 的元素个数，2^B 表示 bucket 数量。

扩容的时机：

• 1、装载因子超过阈值，源码里定义的阈值是 6.5。每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。
• 2、overflow 的 bucket 数量过多。overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人。overflow 的 bucket 数量过多：当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。

源码在mapassign，对应扩容条件的源码如下

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

// 装载因子超过 6.5
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
  if B > 15 {
    B = 15
  }
  return noverflow >= uint16(1)<<(B&15)
}

对应的扩容方法：

• 1）元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量(2^B)直接变成原来 bucket 数量的 2 倍。
• 2）其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。

优化：渐进式搬迁

• 由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。
• hashGrow() 函数实际上并没有真正地“搬迁”，它只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕，具体来说就是检查 oldbuckets 是否为 nil。

调整前：

调整后：扩容完成后，overflow bucket 消失了，key 都集中到了一个 bucket，更为紧凑了，提高了查找的效率。

7.遍历操作

为什么遍历 map 是无序的？

• 在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。
• 正常从前往后遍历，如果碰到扩容，也会不同。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。

8.删除操作

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {

删除过程：

• 它首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。
• 计算 key 的哈希，找到落入的 bucket。
• 检查此 map 如果正在扩容的过程中，直接触发一次搬迁操作。
• 删除操作同样是两层循环，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。找到对应位置后，对 key 或者 value 进行“清零”操作，将 count 值减 1，将对应位置的 tophash 值置成 Empty。

9.并发操作

map 并不是一个线程安全的数据结构。同时读写一个 map 是不安全的，如果被检测到，会直接 panic。

解决方法1：读写锁 sync.RWMutex。
解决方法2：使用golang提供的 sync.Map

参考文档

• https://www.kevinwu0904.top/blogs/golang-map/
• https://mp.weixin.qq.com/s?__biz=MzkyMzI0NjkzMw==&mid=2247491696&idx=1&sn=7c901815a7c64a012cb84570b8481341&source=41#wechat_redirect
• https://mp.weixin.qq.com/s?__biz=MzkyMzI0NjkzMw==&mid=2247491745&idx=1&sn=ab48946c69eca5aee429d112261c7d0f&source=41#wechat_redirect
• https://segmentfault.com/a/1190000022118894