关于go:go源码分析map全网最详细

map

一、简略构造

map 类型的变量实质上是一个 hmap 类型的指针，键值对通过哈希表来贮存。如下图：

二、哈希表的设计

1、构造

hash 表首先有一段贮存贮存数据的间断空间，咱们将数据存到这段间断的空间（能够把它当组成一个数组）外面，如下图所示，把 key、value 以及 key 的 hash 值存到间断的空间外面

2、寻址

而后就是以后的 key-value 具体要存到哪一个地位呢？当初支流的通常有两种办法：

1、取模运算：hash % m

2、位运算：hash&(m-1)

咱们都晓得位运算必定是更加的高效，然而必须得限度 m 为 2 的整数幂。golang 外面采纳了幂运算的办法来寻址

3、hash 抵触

当咱们两个 key 产生 hash 抵触了怎么解决呢？咱们也介绍两种的办法

1、拉链法：这种办法会把产生 hash 抵触的 key-value 数据用链表的形式把数据组织起来。如下图所示，当产生 hash 抵触的时候，前面插入的数据会链接到发生冲突的数据前面

2、凋谢地址法：比方下图，咱们编号 0 的地位曾经被占了，那么咱们就把数据放在编号 1 的地位，如果编号 1 的地位也被占了，由此类推，咱们持续寻址，直到找到闲暇的中央。

当咱们去查找数据的时候，咱们先会查找 0 地位，如果不是咱们查找的 key，会持续向下查找，晓得查找到最初的地位，很显然，这种办法不适宜负载因子（前面会介绍）过大的状况

下面两种办法比照：拉链法 绝对于查找数据比拟敌对，查找的次数不会太多。凋谢地址法 则不会产生不间断的内存空间，每次申请的都是一块间断的内存空间。在 golang 中，采纳了相似于拉链法，为什么说相似呢？前面会详细分析一下 map 的数据结构。

4、扩容

当咱们的数据曾经远远超过 8 个，采纳拉链法，那么 hash 表就会进化成链表。开发地址法就更不行了。这时候咱们就会波及到扩容的问题。扩容咱们次要搞清楚两个问题就行了：何时扩容、怎么扩容

何时扩容

还记得咱们上文提到的负载因子吗？负载因子就是来标识何时扩容的一个参数。它是哈希表中存储的键值对数量和桶数量的比值，通常须要设定一个触发扩容的最大负载因子

loadFactor = keyCount / bucketCount

咱们假如咱们的负载因子是 50%, 当咱们来了一个新的 key12 的时候，就会触发扩容

怎么扩容

咱们间接的想法是，当达到负载因子的时候，间接把 buckets 的容量翻倍。而后把数据都 copy 到新的地址空间去。如下所示

这么迁徙会有个问题。当旧桶的数据十分多的时候呢？这时候迁徙数据就会占用大量工夫，影响咱们主程序。所以简直在所有的语言中，都会采纳 渐进式扩容。

这种形式下，旧桶里的键值对是分屡次挪到新桶里的，能够在触发扩容后，先调配新桶，而后标记以后哈希表正在扩容，并在哈希表的读写操作中判断若在扩容中，则迁徙一部分键值对到新桶里，这样能够把扩容耗费的工夫扩散到屡次操作中。

好了，下面咱们大略介绍了 hash 表的一些个性和问题，接下来咱们再介绍一下 golang 中的 map 长什么样子。

三、map 的数据结构

图解构造

map 底层的哈希表通过 与运算 的形式抉择桶，所以 hmap 中并不间接记录桶的个数，而是记录这个数目是 2 的多少次幂。上面咱们先看看 map 应用的桶长什么样子。咱们先看看之前的 map 根本结构图，晓得 golang 中一个桶其实就是一个 bmap。

下图是一个 bmap 的数据结构。咱们能够看到 bmap 其实是一段间断内存空间。

为了内存应用更加紧凑，8 个键放一起，8 个值放一起。对应每个 key 只保留其哈希值的高 8 位（tophash）。而每个键值对的 tophash、key 和 value 的索引程序一一对应。

能够看到这个其实和咱们下面说的拉链法比拟类似，如果产生 hash 抵触的时候，会在 bmap 中向后写入，这样既保证了查找次数较少，又能保障内存比拟间断。

8 个存满了怎么办？为了缩小扩容次数，这里引入了溢出桶 (overflow)。溢出桶的内存布局与惯例桶雷同。如果哈希表要调配的桶的数目大于 2^4，就会预调配 2^(B-4) 个溢出桶备用。这些惯例桶和溢出桶在内存中是间断的，只是前 2^B 个用作惯例桶，前面的用作溢出桶。

源码剖析

上面咱们具体来看看源码：

type hmap struct {
  count     int //map 中值的数量
  flags     uint8 // 动作标识（比方正在写数据）B         uint8  // 惯例桶个数等于 2^B
  noverflow uint16 // 溢出桶数量
  hash0     uint32 // hash 种子
  
  buckets    unsafe.Pointer // 桶的指针，指向的是 2^B 个 bmap
  oldbuckets unsafe.Pointer // 旧桶的指针（扩容时应用）nevacuate  uintptr // 扩容时迁徙的地位       

  extra *mapextra // 所有溢出桶指针
}


type mapextra struct {overflow    *[]*bmap // 曾经用到的溢出桶
    oldoverflow *[]*bmap // 渐进式扩容时，保留旧桶用到的溢出桶
    nextOverflow *bmap   // 下一个尚未应用的溢出桶
}
type bmap struct {tophash [bucketCnt]uint8 // 存储 tophash 的值
}

能够看到如果以后桶存满了当前，查看 hmap.extra.nextoverflow 还有可用的溢出桶，就在这个桶前面链上这个溢出桶，而后持续往这个溢出桶里

四、创立 map

咱们晓得创立 map 个别用 make(map) 的形式，上面咱们看看创立 map 具体是怎么操作的，下图是创立 map 时的主流程:

1. 依据须要初始化的大小来确定B 的值
2. 如果B 的值≥4，确定溢出桶的数量
3. 调配桶和溢出桶的内存

源码剖析：

// make map 返回的是指针
func makemap(t *maptype, hint int, h *hmap) *hmap {
  if h == nil {h = new(hmap)
  }
  h.hash0 = fastrand()
  // 依据 hint 初始化桶的大小
  B := uint8(0)
  for overLoadFactor(hint, B) {B++}
  h.B = B

  // 如果桶的数量大于 0，初始化桶的内存
  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
}

// 给 map bucket 分配内存
//  @param t map 的类型
//  @param b 桶的个数 2^b
//  @param dirtyalloc 是否要把返回的 buckets 指向 dirtyalloc 地址
//  @return buckets buckets 地址
//  @return nextOverflow 溢出桶地址
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {base := bucketShift(b)
  nbuckets := base //bucket 的数量
  
  // 当 b 大于 4 是，增加溢出桶，溢出桶的大小为 2^(b-4)个
  if b >= 4 {nbuckets += bucketShift(b - 4)
  }

   // 申请桶的空间
  if dirtyalloc == nil {buckets = newarray(t.bucket, int(nbuckets))
  } else {
    buckets = dirtyalloc
    size := t.bucket.size * nbuckets
    if t.bucket.ptrdata != 0 {memclrHasPointers(buckets, size)
    } else {memclrNoHeapPointers(buckets, size)
    }
  }

 // 有溢出桶，nextOverflow 指向溢出桶的地址
  if base != nbuckets {nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
    last.setoverflow(t, (*bmap)(buckets))
  }
  return buckets, nextOverflow
}

五、通过 key 获取 val

当咱们应用 val,ok := map[key] 会产生什么呢？同样，咱们先通过一个流程图理解一下主流程：

1. 判断 map 是否为空
2. 判断是否有协程在并发的写、
3. 定位到 key 对应的桶地位，如果 map 正在扩（等量）容且该桶还未被迁徙，定位到旧桶的地位
4. 遍历该桶的每个 tophash、key，直到找到和指定 key 相等的数据

上面咱们看看源码：

//  @param t map 的类型
//  @param h map 数据
// 通过 key 获取 val
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   //map 为 nil 或者没有数据，返回零值
  if h == nil || h.count == 0 {if t.hashMightPanic() {t.hasher(key, 0) 
    }
    return unsafe.Pointer(&zeroVal[0])
  }

  //@Step1 有并发的协程正在写，抛出异样（panic）if h.flags&hashWriting != 0 {throw("concurrent map read and map write")
  }

  //@Step2 计算 key 的 hash，定位到以后 key 的 hash 桶地位
  hash := t.hasher(key, uintptr(h.hash0))
  m := bucketMask(h.B)
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

  //@Step3 判断有没有旧桶（正在迁徙）//  如果旧桶数据没有被迁徙，定位到以后 key 在旧桶的地位
  //  如果以后旧桶没有被迁徙，则迁徙桶
  if c := h.oldbuckets; c != nil {if !h.sameSizeGrow() { // 不是进行同长度的扩容（当 map 被删除过多时，须要从新整合数据，避免浪费过多空间）m >>= 1
    }
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    if !evacuated(oldb) {b = oldb}
  }

  // 取 top hash
  top := tophash(hash)

  //@Step4 从 bucket 中找出 key 对应的 val，循环遍历 top hash
bucketloop:
  for ; b != nil; b = b.overflow(t) { // 是否有溢出桶
    for i := uintptr(0); i < bucketCnt; i++ {
      //top hash 是否相等
      if b.tophash[i] != top {if b.tophash[i] == emptyRest { // 如果 top hash 为 emptyRest，则示意前面没数据了
          break bucketloop
        }
        continue
      }
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      if t.indirectkey() {k = *((*unsafe.Pointer)(k))
      }
      // key 是否相等，相等则返回对应的 val
      if t.key.equal(key, k) {e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
        if t.indirectelem() {e = *((*unsafe.Pointer)(e))
        }
        return e
      }
    }
  }
  return unsafe.Pointer(&zeroVal[0])// 返回零值
}

六、增加 key value

增加 key-val 的时候产生了什么呢？同样，咱们先来看一下流程图：

1. 判断 map 是否为空、判断有没有协程并发写
2. 如果 buckets 为空，申请一个长度为 1 的 buckets
3. 找出改 key 对应的桶地位
4. 如果 map 正在迁徙切该桶没有被迁徙，迁徙该桶
5. 遍历该桶，如果找到雷同的 key，返回 val 的地位。如果没有找到，找出下一个空地位，赋值 tophash、key，返回 val 的地位
6. 判断 map 是否须要扩容，如果扩容，返回 5 的操作
7. 如果以后 buckets 和溢出 buckets 都没有地位了，增加一个溢出 buckets，赋值 tophash、key 到第一个空位，返回 val 的地位

源码剖析：

// 新增或者替换 key val  m[key]=val
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  //@Step1 如果 map 为 nil，panic
  if h == nil {panic(plainError("assignment to entry in nil map"))
  }

  // 判断有没有协程正在写 map
  if h.flags&hashWriting != 0 {throw("concurrent map writes")
  }
  hash := t.hasher(key, uintptr(h.hash0))

  // 设置 map 写的标记
  h.flags ^= hashWriting

  //@Step2 buckets 为 nil，new 一个
  if h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
  }

again:
  //@Step3 找出 key hash 对应的桶
  bucket := hash & bucketMask(h.B)
  if h.growing() {
    //  @Step4 如果桶须要迁徙，则把旧桶迁徙
    growWork(t, h, bucket)
  }
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  top := tophash(hash)

  var inserti *uint8
  var insertk unsafe.Pointer
  var elem unsafe.Pointer
  //@Step5 寻找 map 中有没有存在的 key
  //  5-1 如果存在，更新 key 的值，则返回 val 的地位
  //  5-2 如果不存在，则记录 bucket 最近一个空地位的 tophash、key、value 的地位
  //  5-2-1 判断 bucket 有没有溢出，如果没有溢出，则下一步。//  5-2-2 溢出了则找出下一个溢出桶，持续 bucketloop 上述操作
bucketloop:
  for {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {
        // 判断以后元素是否为空，如果为空，记录第一个为空的地位（不便找不到 key 时插入）if isEmpty(b.tophash[i]) && inserti == nil {inserti = &b.tophash[i]
          insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
          elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
        }
        if b.tophash[i] == emptyRest {break bucketloop}
        continue
      }
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      if !t.key.equal(key, k) {continue}
      elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
      // 找到了 key
      goto done
    }
    // 在惯例桶中没有找到数据，在溢出桶持续找
    ovf := b.overflow(t)
    if ovf == nil {break}
    b = ovf
  }

  //@Step6 如果增加一个元素会造成 bucket 超过负载（6.5），或者溢出 bucket 太多
  //  裁减桶，返回下面逻辑 bucketloop 持续寻找 val 地位
  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)
    goto again 
  }

  //@Step7 以后 bucket 和溢出桶都满了，从新增加一个溢出桶
  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))
  }

  // 贮存 key、tophash 的地位。h.count +1
  if t.indirectkey() {kmem := newobject(t.key)
    *(*unsafe.Pointer)(insertk) = kmem
    insertk = kmem
  }
  if t.indirectelem() {vmem := newobject(t.elem)
    *(*unsafe.Pointer)(elem) = vmem
  }
  typedmemmove(t.key, insertk, key)
  *inserti = top
  h.count++

  // 返回 val 的地位
done:
  if h.flags&hashWriting == 0 {throw("concurrent map writes")
  }
  h.flags &^= hashWriting
  if t.indirectelem() {elem = *((*unsafe.Pointer)(elem))
  }
  return elem
}

七、删除 key value

删除 key 的时候产生了什么呢？同样，咱们先来看一下流程图：

源码剖析：

// 删除 key、val
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
  // 判断 map 是否处于写状态
  if h.flags&hashWriting != 0 {throw("concurrent map writes")
  }

  hash := t.hasher(key, uintptr(h.hash0))
  // 把 map 置为写状态
  h.flags ^= hashWriting

  //1 找出对应的桶地位
  //  如果须要迁徙，持续迁徙
  bucket := hash & bucketMask(h.B)
  if h.growing() {growWork(t, h, bucket)
  }
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  bOrig := b
  top := tophash(hash)

  //2
  //  2-1 找出 tophash key val 地位
  //  2-2 把 tophash 置为 emptyOne（以后地位为空，但前面还有元素）//  2-3 以后 bucket 前面没有元素，则置为 emptyRest（以后地位为空，且前面没有元素）search:
  for ; b != nil; b = b.overflow(t) {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if b.tophash[i] == emptyRest { // 如果发现对应的 tophash 曾经是 emptyRest 状态，则标识前面没有数据了
          break search
        }
        continue
      }
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      k2 := k
      if !t.key.equal(key, k2) {continue}
      e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
      // 革除 val
      if t.indirectelem() {*(*unsafe.Pointer)(e) = nil
      } else if t.elem.ptrdata != 0 {memclrHasPointers(e, t.elem.size)
      } else {memclrNoHeapPointers(e, t.elem.size)
      }
      // 把 tophash 置为 emptyOne（以后地位为空，但前面还有元素）b.tophash[i] = emptyOne
      //3 判断下一个地位（可能是溢出桶第一个）tophash 是不是 emptyRest
      //  3-1 如果不是，间接到 notLast 完结流程
      //  3-2 如果是，往前搜寻，把所有 emptyOne 置为 emptyRest
      if i == bucketCnt-1 {if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {goto notLast}
      } else {if b.tophash[i+1] != emptyRest {goto notLast}
      }
      for {b.tophash[i] = emptyRest
        if i == 0 {
          if b == bOrig {break}
          c := b
          for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { }
          i = bucketCnt - 1
        } else {i--}
        if b.tophash[i] != emptyOne {break}
      }
      
    notLast:
      // 数量减 1
      h.count--
      break search
    }
  }
}

六、迭代 key value

遍历 key-val 就比较简单了。给定一个随机桶地位 startBucket，和随机桶内数据地位 offset，开始遍历 map 的每个值：

源码剖析：

// 初始化迭代器
func mapiterinit(t *maptype, h *hmap, it *hiter) {
  //1 初始化迭代器
  it.t = t
  if h == nil || h.count == 0 {return}
  it.h = h
  it.B = h.B
  it.buckets = h.buckets

  //2 给一个随机数，决定迭代桶的开始地位和桶内开始迭代的程序
  r := uintptr(fastrand())
  if h.B > 31-bucketCntBits {r += uintptr(fastrand()) << 31
  }
  it.startBucket = r & bucketMask(h.B)          // 桶的偏移量
  it.offset = uint8(r >> h.B & (bucketCnt - 1)) // 桶内偏移量

  it.bucket = it.startBucket
}

// 迭代器迭代
//  1 从随机偏移桶循环迭代每个桶数据
//  2 桶内从随机偏移量开始遍历
//  3 列出该办法隐掉了当正在进行扩容时怎么迭代，须要理解参考源码
func mapiternext(it *hiter) {

  if h.flags&hashWriting != 0 { // 有协程正在写
    throw("concurrent map iteration and map write")
  }
  t := it.t
  bucket := it.bucket
  b := it.bptr
  i := it.i
  checkBucket := it.checkBucket

next:
  if b == nil { // 以后桶指针为 nil，标识桶内数据曾经遍历实现，须要遍历下一个桶
    if bucket == it.startBucket && it.wrapped { // 曾经遍历到开始的桶
      it.key = nil
      it.elem = nil
      return
    }
    bucket++
    if bucket == bucketShift(it.B) {
      bucket = 0
      it.wrapped = true
    }
    i = 0
  }
  for ; i < bucketCnt; i++ {offi := (i + it.offset) & (bucketCnt - 1) // 从桶内哪个地位开始遍历
    if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {// 没数据
      continue
    }
    k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
    e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
  b = b.overflow(t)
  i = 0
  goto next
}

参考：

https://github.com/golang/go/…