关于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时的主流程:

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

源码剖析：

// 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]会产生什么呢？同样，咱们先通过一个流程图理解一下主流程：

判断map是否为空
判断是否有协程在并发的写、
定位到key对应的桶地位，如果map正在扩（等量）容且该桶还未被迁徙，定位到旧桶的地位
遍历该桶的每个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的时候产生了什么呢？同样，咱们先来看一下流程图：

判断map是否为空、判断有没有协程并发写
如果buckets为空，申请一个长度为1的buckets
找出改key对应的桶地位
如果map正在迁徙切该桶没有被迁徙，迁徙该桶
遍历该桶，如果找到雷同的key，返回val的地位。如果没有找到，找出下一个空地位，赋值tophash、key，返回val的地位
判断map是否须要扩容，如果扩容，返回5的操作
如果以后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/…

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

map

一、简略构造

二、哈希表的设计

1、构造

2、寻址

3、hash抵触

4、扩容

三、map的数据结构

图解构造

源码剖析

四、创立map

五、通过key获取val

六、增加key value

七、删除key value

六、迭代key value

评论

发表回复取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

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

map

一、简略构造

二、哈希表的设计

1、构造

2、寻址

3、hash抵触

4、扩容

三、map的数据结构

图解构造

源码剖析

四、创立map

五、通过key获取val

六、增加key value

七、删除key value

六、迭代key value

评论

发表回复 取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

发表回复取消回复