乐趣区

关于golang:由浅到深入门Go语言Map实现原理

jiezi

导读

Go 源码版本 1.13.8

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

收益序号 收益形容 把握水平
收益 1 大抵 对 Go 语言 Map 底层实现有一个理解 必须把握
收益 2 大抵晓得Go 语言 Map 是如何读取数据的 必须把握
收益 3 相熟Go 语言 Map 底层外围构造体hmap 可选
收益 4 相熟Go 语言 Map 底层外围构造体bmap 可选
收益 5 相熟Go 语言 Map 底层里的溢出桶 可选
收益 6 相熟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 的值的一个 大抵过程：

步骤编号 形容
① 通过 hash 函数获取指标 key 的 哈希 ，哈希和数组的长度通过位操作获取数组地位的 索引(备注：获取索引值的形式个别有取模或位操作，位操作的性能好些)
② 遍历 bmap 里的键，和指标 key 比照获取key 的索引(找不到则返回空值)
③ 依据 key 的索引 通过计算偏移量，获取到对应 value

读过程图示如下：

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

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

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

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

蕴含收益 3、4、5、6

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

外围构造体hmap

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

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

字段释义如下：

字段 解释
count 键值对的数量
B 2^B=len(buckets)
hash0 hash 因子
buckets 指向一个数组 (间断内存空间)，数组的类型为[]bmap，bmap 类型就是存在键值对的构造上面会具体介绍，这个字段咱们能够称之为失常桶。 如下图所示
oldbuckets 扩容时，寄存之前的 buckets(Map 扩容相干字段)
extra 溢出桶构造，失常桶外面某个 bmap 存满了，会应用这外面的内存空间寄存键值对
noverflow 溢出桶里 bmap 大抵的数量
nevacuate 分流次数，成倍扩容分流操作计数的字段(Map 扩容相干字段)
flags 状态标识，比方正在被写、buckets 和 oldbuckets 在被遍历、等量扩容(Map 扩容相干字段) 
备注：本次内容不波及 Map 的扩容逻辑。

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

字段buckets

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

hmap的源码和地址如下：

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
type 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的具体字段如下图所示：

字段释义如下：

字段 解释
topbits 长度为 8 的数组，[]uint8，元素为：key 获取的 hash 的高 8 位，遍历时比照应用，进步性能。如下图所示
keys 长度为 8 的数组，[]keytype，元素为：具体的 key 值。如下图所示
elems 长度为 8 的数组，[]elemtype，元素为：键值对的 key 对应的值。如下图所示
overflow 指向的 hmap.extra.overflow 溢出桶里的 bmap，下面的字段topbits、keys、elems 长度为 8，最多存 8 组键值对，存满了就往指向的这个 bmap 里存
pad 对齐内存应用的，不是每个 bmap 都有会这个字段，须要满足肯定条件

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

// https://github.com/golang/go/blob/go1.13.8/src/cmd/compile/internal/gc/reflect.go
func 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是个构造体，构造图示和字段释义如下：

字段 解释
overflow 称之为 溢出桶 。和hmap.buckets 的类型一样也是数组 []bmap，当失常桶bmap 存满了的时候就应用 hmap.extra.overflow 的bmap。所以这里有个问题失常桶 hmap.buckets 里的 bmap 是怎么关联上溢出桶 hmap.extra.overflow 的bmap呢？咱们上面说。
oldoverflow 扩容时寄存之前的 overflow(Map 扩容相干字段)
nextoverflow 指向溢出桶里下一个能够应用的bmap

源码和地址如下：

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
type 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.go
func 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/

退出移动版