GO 中 map 的实现原理

嗨，我是小魔童哪吒，咱们来回顾一下上一次分享的内容

• 分享了切片是什么
• 切片和数组的区别
• 切片的数据结构
• 切片的扩容原理
• 空切片 和 nil 切片的区别

要是对 GO 的 slice 原理还有点趣味的话，欢送查看文章 GO 中 slice 的实现原理

map 是什么？

是 GO 中的一种数据类型，底层实现是 hash 表，看到 hash 表 是不是会有一点相熟的感觉呢

咱们在写 C/C++ 的时候，外面也有 map 这种数据结构，是 key - value 的模式

可是在这里咱们可别搞混了，GO 外面的 map 和 C/C++ 的 map 可不是同一种实现形式

• C/C++ 的 map 底层是 红黑树实现的
• GO 的 map 底层是 hash 表实现的

可是别忘了 C/C++ 中还有一个数据类型是 unordered_map，无序 map，他的底层实现是 hash 表，与咱们 GO 外面的 map 实现形式相似

map 的数据结构是啥样的？

后面说到的 GO 中 string 实现原理，GO 中 slice 实现原理，都会对应有他们的底层数据结构

哈，没有例外，明天说的 map 必然也有本人的数据结构，相对来说会比前者会多一些成员，咱们这就来看看吧

map 具体 的实现 源码地位是：src/runtime/map.go

// A header for a Go map.
type hmap struct {
   // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
   // Make sure this stays in sync with the compiler's definition.
   count     int // # live cells == size of map.  Must be first (used by len() builtin)
   flags     uint8
   B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
   noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
   hash0     uint32 // hash seed

   buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
   oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
   nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

   extra *mapextra // optional fields
}

hmap构造中的成员咱们来一个一个看看：

通过 extra 字段，咱们看到他是 mapextra 类型的，咱们看看细节

// mapextra holds fields that are not present on all maps.
type mapextra struct {
   // If both key and elem do not contain pointers and are inline, then we mark bucket
   // type as containing no pointers. This avoids scanning such maps.
   // However, bmap.overflow is a pointer. In order to keep overflow buckets
   // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
   // overflow and oldoverflow are only used if key and elem do not contain pointers.
   // overflow contains overflow buckets for hmap.buckets.
   // oldoverflow contains overflow buckets for hmap.oldbuckets.
   // The indirection allows to store a pointer to the slice in hiter.
   overflow    *[]*bmap
   oldoverflow *[]*bmap

   // nextOverflow holds a pointer to a free overflow bucket.
   nextOverflow *bmap
}

点进来，这里次要是要和大家一起看看这个 bmap的数据结构，

这个构造是，GO map 外面桶的实现构造，

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

type bmap struct {tophash [8]uint8 // 存储哈希值的高 8 位
    data    byte[1]  //key value 数据:key/key/key/.../value/value/value...
    overflow *bmap   // 溢出 bucket 的地址
}

源码的意思是这样的：

tophash 个别寄存的是桶内每一个 key hash 值字节，如果 tophash[0] < minTopHash，tophash[0] 是一个疏散状态

这里源码中有一个留神点：

实际上分配内存的时候，内存的前 8 个字节是 bmap，前面跟着 8 个 key、8 个 value 和 1 个溢出指针

咱们来看看图吧

GO 中 map 底层数据结构成员绝对比 string 和 slice 多一些，不过也不是很简单，咱们画图来瞅瞅

咱们的 hmap的构造是这样的，能够关注桶数组（hmap.buckets）

若图中的 B = 3的话的，那么桶数组长度 就是 8

下面看到 每一个 bucket，最多能够寄存 8 个 key / value 对

如果超出了 8 个的话，那么就会溢出，此时就会链接到 额定的溢出桶

了解起来是这个样子的

严格来说，每一个桶外面只会有 8 个键值对，若多余 8 的话，就会溢出，溢出的指针就会指向另外一个桶对应的 8 个键值对

这里咱们联合一下下面 bmap 的数据结构：

• tophash 是个长度为 8 的数组

哈希值低位雷同的键存入以后 bucket 时，会将哈希值的高位存储在该数组中，便于后续匹配

• data 外面寄存的是 key-value 数据

寄存程序是 8 个 key 顺次排开，8 个 value 顺次排开， 这是为啥呢？

因为 GO 外面为了字节对齐，节俭空间

• overflow 指针，指向的是另外一个 桶

这里是解决了 2 个问题，第一是解决了溢出的问题，第二是解决了抵触问题

啥是哈希抵触？

上述咱们说到 hash 抵触 ，咱们来看看啥是hash 抵触，以及 如何解决呢

关键字值不同的元素可能会映象到哈希表的同一地址上就会产生哈希抵触

简略对应到咱们的上述数据结构外面来，咱们能够这样了解

当有两个或以上的键 (key) 被哈希到了同一个 bucket 时，这些键 j 就产生了抵触

对于解决 hash 抵触 的形式大体有如下 4 个，网上查找的材料，咱们援用一下，梳理一波看看：

• 凋谢定址法

当抵触产生时，应用某种探查 (亦称探测) 技术在散列表中造成一个探查 (测) 序列。

沿此序列一一单元地查找，直到找到给定 的关键字，或者碰到一个凋谢的地址 (即该地址单元为空) 为止（若要插入，在探查到凋谢的地址，则可将待插入的新结点存人该地址单元）。

查找时探查到凋谢的 地址则表明表中无待查的关键字，即查找失败。

• 再哈希法

同时结构多个不同的哈希函数。

• 链地址法

将所有哈希地址为 i 的元素形成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中

因此查找、插入和删除次要在同义词链中进行。链地址法实用于常常进行插入和删除的状况。

• 建设公共溢出区

将哈希表分为根本表和溢出表两局部，但凡和根本表发生冲突的元素，一律填入溢出表。

仔细的小伙伴看到这里，有没有看进去 GO 中的 map 是如何解决 hash 抵触的？

没错，GO 中的 map 解决 hash 抵触 就是应用的是 链地址法来解决键抵触

再来一个图，咱们看看他是咋链 的，其实咱们上述说的溢出指针就曾经揭晓答案了

如上图，每一个 bucket 外面的溢出指针 会指向另外一个 bucket，每一个bucket 外面寄存的是 8 个 key 和 8 个 value，bucket 外面的溢出指针又指向另外一个 bucket， 用相似链表的形式将他们连接起来

GO 中 map 的基本操作有哪些？

map 的利用比较简单，感兴趣的能够在搜索引擎上查找相干材料，晓得 map 具体实现原理之后，再去利用就会很简略了

• 有 map 的初始化
• map 的增、删、改、查

GO 中 map 能够扩容吗？

当然能够扩容，扩容分为如下两种状况：

• 增量扩容
• 等量扩容

咱们 map 扩容也是有条件的，不是随随便便就能扩容的。

当一个新的元素要增加进 map 的时候，都会查看是否须要扩容，扩容的触发条件就有 2 个：

• 当负载因子 > 6.5 的时候，也就是均匀下来，每个 bucket 存储的键值对达到 6.5 个的时候，就会扩容
• 当溢出的数量 > 2^15 的时候，也会扩容

这里说一下啥是 负载因子 呢？

有这么一个公式，来计算负载因子：

负载因子 = 键的数量 / bucket 数量

举个例子：

若有 bucket 有 8 个，键值对也有 8 个，则这个哈希表的负载因子就是 1

哈希表也是要对负载因子进行管制的，不能让他太大，也不能太小，要在一个适合的范畴内，具体的适合范畴依据不同的组件有不同的值，若超过了这个适合范畴，哈希表就会触发再哈希（rehash）

例如

• 哈希因子太小的话，这就表明空间利用率低
• 哈希因子太大的话，这就表明哈希抵触重大，存取效率比拟低

留神了，在 Go 外面，负载因子达到 6.5 时会触发 rehash

啥是增量扩容

就是当负载因子过大，也就是哈希抵触重大的时候，会做如下 2 个步骤

• 新建一个 bucket，新的 bucket 是原 bucket 长度的 double
• 再将原来的 bucket 数据 搬迁到 新的 bucket 中

可是咱们想一想，如果有上千万，上亿级别键值对，那么迁徙起来岂不是很耗时

所以 GO 还是很聪慧的，他采纳的逐渐搬迁的办法，每次拜访map，都会触发一次迁徙

咱们画个图来瞅瞅

咱画一个 hmap，外面有 1 个bucket0，这个桶的满载是 4 个 key-value，此时的负载因子是 4

实际上是不会触发扩容的，因为 GO 的默认负载因子是 6.5

然而咱们为了演示不便，模仿一下扩容的成果

当再插入一个键值对的时候，就会触发扩容操作，扩容之后再把新插入的键值对，放到新的 bucket 中，即bucket1，而旧的 bucket 指针就会指向原来的那个 bucket

最初，再做一个迁徙，将旧的 bucket，迁徙到新的 bucket 下面来，删掉旧的 bucket

根据上述的数据搬迁图，咱们能够晓得

在数据搬迁的过程中，原来的 bucket 中的键值对会存在于新的 bucket 的后面

新插入的键值对，会存在与另外一个 bucket 中，自然而然的会放到原来 bucket 的前面了

啥是等量扩容

等量扩容，等量这个名字感觉像是，裁减的容量和原来的容量是一一对齐的，也就是说成倍增长

其实不然，等量扩容，其实 buckets 数量没有变动

只是对 bucket 的键值对从新排布，整顿的更加有条理，让其使用率更加的高

例如 等量扩容后，对于一些 溢出的 buckets，且外面的内容都是空的键值对，这时，就能够把这些升高效率且有效的 buckets 清理掉

这样，是进步 buckets 效率的一种无效形式

总结

• 分享 map 是什么
• map 的底层数据结构是啥样的
• 什么是哈希抵触，并且如何解决
• GO 的 map 扩容形式，以及画图进行了解

欢送点赞，关注，珍藏

敌人们，你的反对和激励，是我保持分享，提高质量的能源

好了，本次就到这里，下一次 GO 中 Chan 的实现原理分享

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是 小魔童哪吒，欢送点赞关注珍藏，下次见~