导读

Go源码版本1.13.8

明天要分享的是次要内容是Go语言Map底层实现，目标让大家疾速理解Go语言Map底层大抵的实现原理。读完本篇文章你能够取得收益、以及我所冀望你能获取的收益如下：

收益1和收益2是看了本篇文章心愿大家必须把握的知识点，其余的为可选项，如果你对此感兴趣或者曾经把握了收益1、2能够持续浏览此处的内容。

对于本篇文章的构造次要按如下程序发展：

• 简略看看个别Map的实现思路
• Go语言里Map的实现思路(入门水平：蕴含收益1、2)
• Go语言里Map的实现思路(相熟水平：蕴含收益3、4、5、6)

其次，本篇文章次要以Map的读来开展剖析，因为读弄明确了，其余的写、更新、删除等基本操作根本都能够猜出来了，不是么????。

简略看看个别Map的实现思路

直入主题，个别的Map会蕴含两个次要构造：

• 数组：数组里的值指向一个链表
• 链表：目标解决hash抵触的问题，并寄存键值

大抵构造如下：

读取一个key值的过程大抵如下：

                  key                   |                   v                 +------------------------------------+|      key通过hash函数失去key的hash    |+------------------+-----------------+                   |                   v+------------------------------------+|       key的hash通过取模或者位操作     ||          失去key在数组上的索引        |+------------------------------------+                   |                   v+------------------------------------+|         通过索引找到对应的链表         |+------------------+-----------------+                   |                   v+------------------------------------+|       遍历链表比照key和指标key        |+------------------+-----------------+                   |                   v+------------------------------------+|              相等则返回value         |+------------------+-----------------+                   |                   v                                 value 

接着咱们来简略看看Go语言里Map的实现思路。

Go语言里Map的实现思路(入门水平)

蕴含收益1、2

Go语言解决hash抵触不是链表，理论次要用的数组(内存上的间断空间)，如下图所示：

备注：前面咱们会解释下面为啥用的“次要”两个字。

然而并不是只应用一个数组(间断内存空间)寄存键和值，而是应用了两个数组别离存储键和值，图示如下：

上图中：

• 别离对应的是两个外围的构造体hmap和bmap
• bmap里有两个数组别离寄存key和value

把下面简化的关系转换一下，其实就是这样的一个大抵关系，如下图所示：

咱们通过一次读操作为例，看看读取某个key的值的一个大抵过程：

读过程图示如下：

这么看起来是不是“很简略”、很清晰，所以读到这里，你是不是曾经入门了Go语言Map底层实现并且：

• 大抵对Go语言Map底层实现有一个理解(收益1)
• 大抵晓得Go语言Map是如何读取数据的(收益2)

然而理论状况不止如此，咱们再略微深刻的摸索下，有趣味的能够持续往下看，没趣味能够不必持续往下看了(开玩笑=^_^=)，反正曾经达到目标了，哈哈????。

Go语言里Map的实现思路(相熟水平)

蕴含收益3、4、5、6

想要深刻学习，首先得理解下下面提到了实现Map的两个外围构造体hmap和bmap。

外围构造体hmap

收益3: 相熟Go语言Map底层外围构造体`hmap`

hmap的构造其实刚开始看起来其实还是比较复杂的，有不少的字段，具体字段如下图所示：

字段释义如下：

备注：本次内容不波及Map的扩容逻辑。

重点看一些字段的含意和用途。

字段buckets

buckets指向了一个数组(间断的内存空间)，数组的元素是bmap类型，这个字段咱们称之为失常桶。

hmap的源码和地址如下：

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.gotype hmap struct {    count     int     flags     uint8    B         uint8     noverflow uint16     hash0     uint32    buckets    unsafe.Pointer    oldbuckets unsafe.Pointer    nevacuate  uintptr     extra *mapextra}

外围构造体bmap

收益4: Go语言Map底层外围构造体`bmap`

失常桶hmap.buckets的元素是一个bmap构造。bmap的具体字段如下图所示：

字段释义如下：

推断出bmap构造字段的代码和地位如下：

// https://github.com/golang/go/blob/go1.13.8/src/cmd/compile/internal/gc/reflect.gofunc bmap(t *types.Type) *types.Type {  // 略...  field := make([]*types.Field, 0, 5)    field = append(field, makefield("topbits", arr))  // 略...      keys := makefield("keys", arr)    field = append(field, keys)  // 略...      elems := makefield("elems", arr)    field = append(field, elems)  // 略...      if int(elemtype.Align) > Widthptr || int(keytype.Align) > Widthptr {        field = append(field, makefield("pad", types.Types[TUINTPTR]))    }  // 略...      overflow := makefield("overflow", otyp)    field = append(field, overflow)  // 略...}

论断：每个bmap构造最多寄存8组键值对。

hmap和bmap的根本构造合起来

别离理解了hmap和bmap的根本构造后，咱们把下面的内容合并起来，就失去如下的Map结构图：

溢出桶

收益5: 相熟Go语言Map底层里的溢出桶

下面讲bmap的时候，咱们不是失去了个论断么“每个bmap构造最多寄存8组键值对。”，所以问题来了：

失常桶里的bmap存满了怎么办?

解决这个问题咱们就要说到hmap.extra构造了，hmap.extra是个构造体，构造图示和字段释义如下：

源码和地址如下：

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.gotype mapextra struct {    overflow    *[]*bmap    oldoverflow *[]*bmap    nextOverflow *bmap}

问题：失常桶hmap.buckets里的bmap是怎么关联上溢出桶hmap.extra.overflow的bmap呢？

答：就是咱们介绍bmap构造时里的bmap.overflow字段(如下图所示)。bmap.overflow是个指针类型，寄存了对应应用的溢出桶hmap.extra.overflow里的bmap的地址。

问题又来了：

问题：失常桶hmap.buckets里的bmap是什么时候关联上溢出桶hmap.extra.overflow的bmap呢？

答：Map写操作的时候。这里间接看要害代码：

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.gofunc mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {  // 略again:    // 略...    var inserti *uint8  // 略...bucketloop:    for {        for i := uintptr(0); i < bucketCnt; i++ {      // key的hash高8位不相等            if b.tophash[i] != top {        // 以后地位bmap.tophash的元素为空且还没有写入的记录(inserti曾经写入的标记为)                if isEmpty(b.tophash[i]) && inserti == nil {          // inserti赋值为以后的hash高8位 标记写入胜利                    inserti = &b.tophash[i]                    // 略...                }                // 略...                continue            }            // 略...            goto done    }    // 失常桶的bmap遍历完了 持续遍历溢出桶的bmap 如果有的话        ovf := b.overflow(t)        if ovf == nil {            break    }        b = ovf    }  // 略...  // 没写入胜利(蕴含失常桶的bmap、溢出桶的bmap(如果有的话))    if inserti == nil {    // 调配新的bmap写    newb := h.newoverflow(t, b)    // 略...    }    // 略...}// 持续看h.newoverflow的代码func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {  var ovf *bmap  // 如果hmap的存在溢出桶 且 溢出桶还没用完    if h.extra != nil && h.extra.nextOverflow != nil {    // 应用溢出桶的bmap    ovf = h.extra.nextOverflow    // 判断桶的bmap的overflow是不是空    // 这里很奇妙。为啥？    // 溢出桶初始化的时候会把最初一个bmap的overflow指向失常桶，值不为nil    // 目标判断以后这个bmap是不是溢出桶里的最初一个        if ovf.overflow(t) == nil {      // 是nil      // 阐明不是最初一个            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))        } else {      // 不是nil      // 则重置以后bmap的overflow为空      ovf.setoverflow(t, nil)      // 且 标记nextOverflow为nil 阐明以后溢出桶用完了            h.extra.nextOverflow = nil        }    } else {    // 没有溢出桶 或者 溢出桶用完了    // 内存空间重新分配一个bmap        ovf = (*bmap)(newobject(t.bucket))  }  // 生成溢出桶bmap的计数器计数    h.incrnoverflow()  // 略...  // 这行代码就是下面问题咱们要的答案:  // 失常桶`hmap.buckets`里的`bmap`在这里关联上溢出桶`hmap.extra.overflow`的`bmap`    b.setoverflow(t, ovf)    return ovf}// setoverflow函数的源码func (b *bmap) setoverflow(t *maptype, ovf *bmap) {  // 这行代码的意思：通过偏移量计算找到了bmap.overflow，并把ovf这个bmap的地址赋值给了bmap.overflow    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf}

上面代码这段代码解释了，下面的源码中为何如此判断预调配溢出桶的bmap是最初一个的起因。

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go// 创立hmap的失常桶func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {  // 略...    if base != nbuckets {    // 略...    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))    // 把溢出桶里 最初一个 `bmap`的`overflow`指先失常桶的第一个`bmap`    // 获取预调配的溢出桶里`bmap`时，能够通过判断overflow是不是为nil判断是不是最初一个        last.setoverflow(t, (*bmap)(buckets))  }  // 略...}

当hmap存在溢出桶时，且以后溢出桶只被应用了一个bmap时，咱们能够失去如下的关系图：

同时咱们能够看出失常桶的bmap和溢出桶的bmap理论形成了链表关系，所以这也解释了开篇咱们说到的“Go外面Map的实现次要用到了数组”，其次还用到了链表。

再次剖析Map的读

收益6: 相熟Go语言Map是如何读取数据的

通过下面的学习，咱们再次通过一次读操作为例，看看读取某个key的值的一个大抵过程：

联合代码剖析下整个大体的过程：

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {    // ...略        // ①通过hash函数获取以后key的哈希    hash := alg.hash(key, uintptr(h.hash0))    m := bucketMask(h.B)    // ②通过以后key的哈希获取到对应的bmap构造的b    // 这里的b 咱们称之为“失常桶的bmap”    // “失常桶的bmap”可能会对应到溢出桶的bmap构造，咱们称之为“溢出桶的bmap”    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))        // ...略        // 获取以后key的哈希的高8位    top := tophash(hash)bucketloop:    // 上面的for循环是个简写，残缺如下。    // for b = b; b != nil; b = b.overflow(t) {    // 能够晓得b的初始值为下面的“失常桶的bmap”，则：    // 第一次遍历：遍历的是“失常桶的bmap”    // 如果失常桶没找到，则    // 绿色线条④ 持续遍历：如果以后“失常桶的bmap”中的overflow值不为nil(阐明“失常桶的bmap”关联了“溢出桶的bmap”)，则遍历以后指向的“溢出桶的bmap”持续 蓝色线条的③④⑤步骤    for ; b != nil; b = b.overflow(t) {        // 因为b的初始值为“失常桶的bmap”，第一次先遍历“失常桶的bmap”        for i := uintptr(0); i < bucketCnt; i++ {            // 蓝色线条③ 比照key哈希的高8位            // 比照哈希的高8位目标是为了减速            if b.tophash[i] != top {                // emptyRest 标记位：示意以后地位曾经是开端了；删除操作会设置此标记位                if b.tophash[i] == emptyRest {                    break bucketloop                }                continue            }            // 找到了雷同的hash高8位，则：找到对应索引地位i的key            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))            if t.indirectkey() {                k = *((*unsafe.Pointer)(k))            }            // 蓝色线条④ 比照key是不是统一            if alg.equal(key, k) {                // 蓝色线条⑤ key是统一，则：获取对应索引地位的值                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])}

参考：1.《Go语言设计与实现》https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/2. Go源码版本1.13.8 https://github.com/golang/go/tree/go1.13.8/src

查看《Go语言轻松系列》更多内容

链接 http://tigerb.cn/go/#/kernal/