本文基于 go 1.19

哈希表作为一种十分常用的数据结构，存在于各种编程言语中，它能够让咱们保存键值对数据，并且有着十分高的查找功率。 本文就以 go 言语中的 map 为比方，叙述一下哈希表在 go 中的完结。

哈希表基本操作

在开端之前，需求大概解说一下哈希表这种数据结构，哈希表会预先在内存中分配一段比较大的内存，这段内存用在将来往里边写入数据的时分运用。 哈希表有点相似数组，都是一段接连的内存，可是咱们往哈希表读写数据的时分不同于数组，数组的时分是直接经过下标拜访的， 而哈希表的读写需求先核算 key 的哈希值，依据这个哈希值对哈希表长度取模得到 key 对应的哈希表的下标，然后对哈希表这个下标进行读写操作。

关于哈希表有以下几种常见的操作：

  1. 写入：依据 key 核算 hash 值，对哈希表长度取模得到 key 在内存中的地址，然后往这个地址写入数据。
  2. 读取：依据 key 核算 hash 值，对哈希表长度取模得到 key 在内存中的地址，然后读取这个地址中的数据。
  3. 修正：依据 key 核算 hash 值，对哈希表长度取模得到 key 在内存中的地址，然后修正这个内存地址里边的数据。
  4. 删去：依据 key 核算 hash 值，对哈希表长度取模得到 key 在内存中的地址，然后清空保存这个 key 的那一小块内存。

留意：核算出的 hash 值或许比分配的内存巨细要大，所以才需求对其取模（hash 值 / 哈希表长度 => key 在哈希表的索引）， 确保核算出的 hash 终究落到哈希表的内存规模之内。比方，keyn 核算出来的哈希值为 100，可是咱们的哈希表长度只要 8， 那么 keyn 终究会落在哈希表中下标为 2 的当地（100 % 7 = 2，下标是从 0 开端的，所以这儿是 7）

哈希表的写入

假定咱们现在要有一个长度为 8 的哈希表（下图左），咱们有数据 {"a": 1, "b": 2} 需求存入这个哈希表，存入之后的哈希表为下图右：

go map 设计与实现

阐明：hash(a) = 5，核算 a 的哈希值得到 5，所以将 a:1 存入了哈希表中下标为 5 的地址处。b 同理。

留意：键值都会存储。

哈希表的读取

从哈希表中读取 key 为 b 的键值对：

go map 设计与实现

哈希表的修正

现在，咱们需求将 a 的值修正为 3，相同的，核算其 hash 值，得到 5，然后将哈希表中 5 这个下标的内存修正成 3：

go map 设计与实现

哈希表的删去

假定要将哈希表中 b 这个键删去，会先核算其 hash 值，得到 0，然后将哈希表中 0 这个下标的内存清空：

go map 设计与实现

哈希表的高效之处

经过上面的分析，咱们能够知道，哈希表的内存布局跟数组相似，可是哈希表的存储要经过核算 key 的哈希值来得到其在哈希表中的索引，终究对这个索引的内存进行 CRUD 操作。这样一来，假如咱们需求频频的依据键查找其对应值的话，运用哈希表无疑会大大进步功率。相比之下，假如运用数组来存储，那么每次查找都需求将整个数组遍历一次，功率十分低下。

比方下图，假定咱们一个数组内存布局如下，那么在咱们查找 a:1 的时分，需求从数组的第一个元素开端遍历，每一个元素读取出来看看它的键是不是 a， 取到第 6 个元素（下标 5）的时分，发现它的键是 a，然后取出对应的值 1。

go map 设计与实现

在数组的元素个数少的时分，这种查找功率其实影响不大，但假如咱们有上万个元素的时分，每次查找都要从第一个元素开端遍历，功率无疑会十分低。 相比之下，不论数据再怎样多，运用哈希表的办法，咱们直接经过哈希算法核算一下就能够知道键保存到了哪个槽中。

哈希抵触处理办法

在上一节中，咱们的图将哈希表的每一个槽（slot，又或许叫 cell，都是同一个东西）都标明成只要一个元素了。 但在实践中，往往会呈现核算出来的哈希值对哈希表长度取模后是持平的，也便是不同的 key 会落到同一个槽中（这便是 哈希抵触），

这种状况下，一个槽寄存不下的话，有两种办法能够处理：敞开地址法和链表法。go 里边的 map 运用的是链表法， 具体来说，便是在 hash 抵触的当地，树立一个链表来保存相同 hash 值的 key。

这样一来，咱们经过 hash 算法核算出哈希值的时分，并不能唯一确认对应的值了，由于有或许两个 key 经过哈希算法核算之后，得到的哈希值是相同的。 这种状况怎样办呢？很简略，由于尽管哈希值是相同的，可是它们的 key 是不相同的，再比较一下 key 就能够确认了。具体能够参阅下图：

go map 设计与实现

有哈希抵触的状况下，读取哈希表数据的进程：

  • 核算 c 的 hash 值，得到 0，便是哈希表的索引
  • 获取哈希表中地址 0 上的数据，这会遍历抵触发生的链表
  • 比较 c 跟 b，不持平，持续比较链表下一个元素
  • 比较 c 跟 c，持平，回来 3

哈希扩容

go 里边 map 扩容有两种办法：增量扩容和等量扩容。

哈希表总元素个数过多导致的扩容

这种扩容办法也叫增量扩容。

咱们在上面说过了，其实哈希表的内存布局跟数组相似，都是先分配一段接连的内存。然后在哈希抵触的时分，关于抵触的 key 树立一个链表来保存。 这样就会呈现一种状况，在链表中存在许多抵触的键，这样一来，在查找抵触 key 的时分，需求在这一堆抵触的 key 中进行查找，这个查找相似数组的查找，功率较低。

为了避免这种状况的呈现，一般的哈希表规划会在元素个数总数超越一定数量的时分，对哈希表进行扩容， 这样一来，那些哈希抵触的键就能够相对均匀地散布在哈希表中，从而避免了许多哈希抵触状况下导致的查找功率低下的问题。

扩容之后的容量为本来容量的 2 倍。

go map 设计与实现

go map 的负载因子

在 go 中，map 在实践存储的元素数量超越 map 里 bucket 总数量的 6.5 倍的时分（也便是均匀每个 bucket 中的元素个数大于 6.5 的时分），会进行扩容， 这个 6.5 是完结 map 的那个开发者经过实验核算出来的比较合适的数，这个 6.5 被称为负载因子。

为什么负载因子是 6.5 呢，在 go 的 map 源码中有相关的阐明：

选择负载因子，假如太大，会有许多溢出桶，太小，则会糟蹋许多空间。 我编写了一个简略的程序来查看不同负载的一些统计数据:（64位、8字节 key 和元素）

loadFactor %overflow bytes/entry hitprobe missprobe
4.00 2.13 20.77 3.00 4.00
4.50 4.05 17.30 3.25 4.50
5.00 6.85 14.77 3.50 5.00
5.50 10.55 12.94 3.75 5.50
6.00 15.27 11.67 4.00 6.00
6.50 20.90 10.79 4.25 6.50
7.00 27.14 10.15 4.50 7.00
7.50 34.03 9.73 4.75 7.50
8.00 41.10 9.40 5.00 8.00

列阐明：

  • %overflow: 具有溢出桶的桶的百分比
  • bytes/entry: 每个 key/elem 对运用的开支字节
  • hitprobe: 查找当时 key 时要查看的条目数
  • missprobe: 查找缺少的 key 时要查看的条目数

哈希抵触链上元素太少导致的扩容

这种扩容办法也叫等量扩容。

咱们知道，在哈希抵触的时分，会树立链表来保存键抵触的元素，可是咱们删去那些哈希抵触的键的时分，并不会对删去元素的内存进行开释， 假如每次删去都开释的话，在咱们频频刺进跟删去的时分，功率就十分低下了。 由于刺进一个元素就分配内存，删去一个元素就开释内存（分配内存和开释内存都是相对耗时的操作）。 而这样的成果是，保存抵触键的链表上，有许多空的元素，这样就会导致抵触的时分，查找键的功率降低，由于要遍历许多空的键。

删去的时分不开释，那什么时分会开释呢？哈希抵触的元素许多都被删去的时分，在 go 里边，map 会判别就算没有超越负载因子的状况下， 假如抵触链表占用的空间过大的话，也会进行扩容。但这儿说的扩容其实并不是真正意义上的扩容，仅仅 map 的完结里边，运用的函数是同一个函数。

具体完结办法是，分配跟原哈希表相同巨细的空间，然后将旧哈希表的数据搬迁到新的哈希表。 这样搬迁之后，关于哈希抵触链表上的那些元素，只会搬迁非空的元素，终究成果便是，扩容之后，哈希抵触链表上的元素愈加紧凑，在查找抵触的键的时分会愈加高效。

尽管哈希表的总容量没变，可是数据散布愈加紧凑了，省去了遍历空元素的时间。

go map 设计与实现

go map 概述

  • map 仅仅一个哈希表。数据被排列成一组 bucket。
  • 每个 bucket 最多包括 8 个 键/值 对。
  • 哈希值的低位字节位用于选择 bucket。
  • 每个 bucket 包括每个哈希的几个高位字节位(tophash)，以区别单个桶中的条目。
  • 假如超越 8 个 key 哈希到同一个桶，咱们将额外的桶以链表的办法起来。（处理哈希抵触，链表法）
  • 当哈希表扩容时，咱们会分配一个两倍大的新 bucket 数组。然后 bucket 从旧 bucket 数组增量仿制到新 bucket 数组。
  • map 迭代器遍历 bucket 数组，并按遍历次序回来键（遍历完一般桶之后，遍历溢出桶）。
  • 为了坚持迭代语义，咱们永久不会在它们的桶中移动键（bucket 内键的次序在扩容的时分不变。假如改动了桶内键的相对次序，键或许会回来 0 或 2 次）。
  • 在扩容哈希表时，迭代器仍在旧的桶中迭代，并且有必要查看新桶，查看正在迭代的 bucket 是否现已被搬迁到新桶。

go map 的全体模型

上面讲了哈希表的基本规划思路，接下来就要开端讲 go 里边 map 的规划与完结了。大体上其实便是上面说的姿态，可是有下面几个不相同的当地：

下文的 bucket 和 bmap 都是指的 “桶”。

  • go map 里边存储数据的当地是 bucket（桶），一个 bucket 能够存储 8 个元素，也便是说哈希抵触的时分仍是会在同一个 bucket 中先存储。
  • 假如 bucket 也寄存不下抵触的元素了，那么会新建别的一个桶（叫做溢出桶），旧的 bucket 记载这个新桶的指针，旧的 bucket 寄存不下的元素，会寄存到这个溢出桶中。
  • 假如溢出桶仍是寄存不下，那么再新建一个溢出桶，链接到上一个溢出桶中。

也便是说，在 go 的 map 完结中，哈希核算出来的值决议了 key 应该寄存在哪一个 bucket 中。

go map 的全体结构如下图：

go map 设计与实现

  • buckets 记载了保存 map 数据的一切 bucket（这种下文一致称为一般桶），go 中运用 bmap 这个结构体来标明 bucket，溢出桶也是运用 bmap 结构体标明。
  • 假如 bucket（一般桶）哈希抵触太多导致寄存不下，会新建一个 bucket，在本来的 bucket 上会有一个指针记载新建 bucket 的地址，这个新 bucket 下文一致称为溢出桶。
  • 在创立 map 的时分，假如咱们指定的容量比较大（B >= 4 的时分），那么会预创立一个溢出桶。

也便是说，go 中处理哈希抵触的链表法，链表上的每一个元素是一个 bucket。go map 的完结里边，一个 bucket 能够寄存 8 个键值对。

上面的 bmap 的数据结构如下图：

go map 设计与实现

  • bmap 便是 bucket（桶），不论是一般的桶仍是溢出的桶，都是运用 bmap 结构体标明。
  • bmap 中存储数据的办法有点特别，它先存储了 8 个 tophash 值，一个 tophash 的巨细为 1 个字节，每一个 tophash 记载的是 bmap 中每一个元素的哈希值的最高的 8 bit。
  • 接下来是 bmap 存储的 8 个元素的 key，在 8 个 key 之后是 8 个 bmap 存储的值。咱们会发现 key 和 value 的存储是分隔的，而不是 key/value、key/value 这种办法。go 中这种分隔存储的办法有一个好处是能够削减内存对齐的开支，从而更省内存。
  • 终究是 overflow（溢出桶），假如 bmap 存满了，那就会新建一个溢出桶来保存新的数据，经过在旧的 bmap 上记载指针来记载溢出桶。

tophash 的作用是，在哈希抵触的时分，在 bucket 内进行查找的时分，是需求在 bucket 内从第一个元素遍历到终究一个元素来查找的。 假如 key 太大，直接比较 key 的话功率会比较低下，经过记载哈希值的高 8 位，咱们就能够在 buckeet 内查找的时分，先比较哈希值的 前 8 位，这样一来，map 的功率遭到 key 巨细的影响就会比较小。当然哈希值的高 8 位有或许相同，在这种状况下，咱们再比较一下 key 自身 就能够确认 bucket 的那个槽（slot/cell）是否是咱们正在查找的那一个 key。

go map 相关数据结构

咱们大部分内容是跟下面两个结构体打交道：

  • hmap: map 的数据结构，包括了 bucket 的指针、bucket 的数量、键值对的数量等信息。
  • bmap: 桶，存储 key/value 的当地
// go map 数据结构
type hmap struct {
   count     int            // map 的元素数量。调用 len(map) 的时分回来此值
   flags     uint8          // map 符号：iterator/oldIterator/hashWriting/sameSizeGrow
   B         uint8          // 指示了当时哈希表持有的 buckets 的数量（2^B 是 bucket 的数量）
   noverflow uint16         // 溢出桶的数量
   hash0     uint32         // 哈希种子，核算 key 的哈希的时分会传入哈希函数
   buckets   unsafe.Pointer // 指向 buckets 的数组，巨细为 2^B。 假如元素个数为 0 则为 nil。
   // 哈希表扩容的时分记载 buckets 字段。
   // 增量扩容时，oldbuckets 的长度是 buckets 的一半。
   oldbuckets unsafe.Pointer
   nevacuate uintptr   // 指示扩容进度，小于此地址的 buckets 完结搬迁
   extra     *mapextra // 可选字段
}
// mapextra 包括并非在一切 map 上都存在的字段。
// 下面 mapextra 注释是原文的翻译（看完了 map 的悉数源码也还不是很懂这个结构体的作用，除了 nextOverflow 字段）。
type mapextra struct {
   // 假如 key 和 elem 都不包括指针并且是内联的，那么咱们将 bucket type 符号为不包括指针。这避免了扫描此类 map。
   // 可是，bmap.overflow 是一个指针。 为了让溢出桶坚持活动状况，
   // 咱们将指向一切溢出桶的指针存储在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中。
   // overflow 和 oldoverflow 仅在 key 和 elem 不包括指针时运用。
   // overflow 包括 hmap.buckets 的溢出桶。
   // oldoverflow 包括 hmap.oldbuckets 的溢出桶。
   // 直接答应在 hiter 中存储指向切片的指针。
   overflow    *[]*bmap
   oldoverflow *[]*bmap
   // nextOverflow 持有指向闲暇溢出桶的指针。
   nextOverflow *bmap
}
// go map 中的 bucket 结构体（实践保存 key/value 的当地）
type bmap struct {
   // tophash 通常包括此 bucket 中每个键的哈希值的最高的 8 位（1 字节）。
   // 假如 tophash[0] ＜ minTopHash，则 tophash[0] 为桶已搬迁状况。
   // 这是一个长度为 8 的数组，由于一个 bucket 只能存储 8 个元素。
   // tophash 存储的是每一个元素的键的哈希的高 8 位。
   //（经过比较不同键的哈希的高 8 位能够进步 bucket 内的查找性能，由于键或许很大）
   tophash [bucketCnt]uint8
   // 然后是 8 个键，然后是 8 个值。（这儿的 8 是代码写死的）
   // 留意：将一切键放在在一同，然后将一切值放在一同使代码比交替的 key/elem/key/elem/… 杂乱一些，
   // 但它答应咱们消除填充（削减内存对齐导致的内存糟蹋），例如 map[int64]int8，
   // 这种假如运用 key/elem 的办法存储则需求糟蹋几个字节用来对齐。
   keys [bucketCnt]keytype // 8 个键
   values [bucketCnt]valuetype // 8 个值
   overflow *bmap // 指向溢出桶的指针
}

关于 map 的数据结构，需求特别阐明的是，bmap 的源码中实践只包括了 tophash 字段，而后边的三个字段 keys/values/overflow 都是在编译期间动态增加的。这是由于 map 中或许存储不同类型的键值对，所以键值对占据的内存空间巨细只能在编译时进行推导。 这样一来，终究的成果是，咱们在 map 的源码中，拜访 key 和 value 的时分都需求经过 bmap 的首地址加上偏移量来进行拜访的。

比方获取 bucket 中第 i 个 key 的办法：

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

这行代码中，add 是做指针加法运算的函数，具体来说便是第一个参数的地址加上第二个参数（偏移量），得到一个咱们想要的指针。 dataOffset 代表了 bmap 的 keys 第一个元素的偏移量，i 代表了咱们想要获取的 key 在 keys 中的索引：

go map 设计与实现

这样一来，咱们就能够经过 k 这个指针来拜访 bucket 中的 key 了。相同的，要拜访 value 的办法也是相似的， 只要将 dataOffset + i * uintptr(t.keysize) 替换成 dataOffset + bucketCnt * uintptr(t.keysize) 即可。

这种办法尽管不太高雅，可是在性能上能够到达最优。

bmap（桶）源码分析

bmap 便是保存键值对的当地，可是它自身的办法并不多：

// bucket 是否现已完结搬迁
// b 是 bucket 的指针
func evacuated(b *bmap) bool {
   h := b.tophash[0]
   return h > emptyOne && h < minTopHash
}
// 获取 b 的溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
   // bmap 数据结构的终究一个指针便是指向溢出桶的指针
   return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize))
}
// 设置 b 的溢出桶
// bmap 数据结构的终究一个指针指向溢出桶
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
   *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}
// 获取 b 中保存 keys 的指针（指向了桶内的第一个 key）
func (b *bmap) keys() unsafe.Pointer {
   return add(unsafe.Pointer(b), dataOffset)
}

在 ev 顶用到了两个常量，在 bucket 的 tophash 里边，会经过下面几个标志来记载桶里边槽的状况：

// 这个 cell 是空的，并且在更高的索引或溢出处没有更多的非空 cell。
emptyRest = 0
// 这个 cell 是空的
emptyOne = 1
// key/elem 有效。 entry 已被搬迁到较大的哈希表的前半部分（扩容了）。
evacuatedX = 2
// 同上，但搬迁到大的哈希表的后半部分（扩容了）。
evacuatedY = 3
// cell 是空的，bucket 现已被搬迁了
evacuatedEmpty = 4
// 正常填充单元格的最小 tophash。
minTopHash = 5

为了跟正常的 tophash 区别开来，假如核算出来的 tophash 小于 minTopHash，会将核算出来的 tophash 加上 minTopHash：

// tophash 核算 hash 的 tophash 值。
// 这是一个字节的巨细的。（hash 最高的 8 位）
func tophash(hash uintptr) uint8 {
   // top 本质上便是 hash 的前面 8 个字节（goarch.PtrSize*8 - 8，左移位数：指针的字节巨细 - 8 字节）
   top := uint8(hash >> (goarch.PtrSize*8 - 8))
   if top < minTopHash {
      top += minTopHash
   }
   return top
}

这样一来，经过 tophash 这一个字节就能够记载桶里边槽的状况了，十分节约空间。

map 的创立的完结

咱们现已了解了哈希表的基本作业机制了，现在就让咱们来深化了解一下 go 里 map 的完结，先是 map 的创立， map 的创立是经过 makemap() 函数完结的（对应咱们写的代码是 make(map[int]int, 10)），map 的创立进程如下：

  1. 核算 map 所需内存，判别是否在一个合理规模之内。
  2. 运用 new 初始化 hmap 结构体。
  3. 生成随机哈希种子。
  4. 核算出一个最小的 B，也便是依据用户传递给 make 的第二个参数算出一个最小的 B 的值，终究桶的数量为 2^B 个。
  5. 假如 B 大于 0，则给哈希表的 buckets 分配内存。
  6. 终究，回来新创立好的 hmap。

下文在寻址进程中，大量运用了指针的运算，所以假如对 unsafe.Pointer 比较了解的话，看起来会比较轻松，假如不了解也不要紧，能够看看我别的一篇文章《深化了解 go unsafe》。

makemap 完结

makemap 具体源码如下：

// makemap 是 make(map[k]v, hint) 的完结，创立一个 map。
// 假如编译器能够确认 map 或许第一个 bucket 能够在栈上创立，h 和/或 bucket 或许为 non-nil。
// 假如 h != nil，map 能够直接在 h 中创立。
// 假如 h.buckets != nil，buckets 指针指向的那个元素能够作为第一个 bucket。
func makemap(t *maptype, hint int, h *hmap) *hmap {
   // 核算所需求的内存巨细
   mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
   // 假如溢出或许超出最大分配内存，则设置 hint = 0；
   // 这样的话，B 也会等于 0；
   // 则终究的 map 只会有一个 bucket（2^B = 1）
   if overflow || mem > maxAlloc {
      hint = 0
   }
   // 初始化 hmap（分配 hmap 结构体自身所需求的内存）
   if h == nil {
      h = new(hmap)
   }
   // 生成一个随机的哈希种子
   h.hash0 = fastrand()
   // 依据传入的 hint，核算出需求的最小桶数量。
   // 实践上是核算 B 的巨细，桶的数量都是运转时经过 2^B 核算的。
   B := uint8(0)
   // 假如 hint 导致超越了负载因子，则将 B 加 1，一直加到小于负载因子。
   // 简略来说便是：hint / (2^B) > 负载因子，也便是 hint 个键值对放到一切桶中，
   // 每个桶中元素数量大于负载因子（6.5）的时分，则将 B 加 1。
   // 注：map 扩容的时分也是这个判别规范。
   for overLoadFactor(hint, B) {
      B++
   }
   h.B = B
   // 分配初始哈希表。
   // 假如 B==0，则稍后（在mapassign中）推迟分配桶字段。
   // 若 hint 较大，则清零此内存或许需求一段时间。
   if h.B != 0 {
      var nextOverflow *bmap
      // 初始化 buckets（分配 buckets 所需求的内存）
      h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
      // 假如 hint 比较大，则会预先分配溢出桶，记载到 extra 字段中。
      if nextOverflow != nil {
         h.extra = new(mapextra)
         h.extra.nextOverflow = nextOverflow
      }
   }
   return h
}

overLoadFactor 完结

这儿边有一个比较重要的函数，那便是 overLoadFactor，这个函数用来判别某一个数量是否超越 map 的负载因子，假如超越，那就需求扩容了：

// overLoadFactor 陈述放置在 2^B 个桶中的键值对数量是否超越负载因子。
func overLoadFactor(count int, B uint8) bool {
   return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
  • count > bucketCnt，前半部分判别很简略，便是判别数量一个桶能不能放得下。一个桶就能装下一切数据的话，根本就不必核算了，必定没超越负载因子。
  • 后半部分判别翻译过来是：桶数量 * 负载因子(6.5) < 总键值对数量，意味着均匀每个桶存储的元素个数大于 6.5 了，也便是说超越了负载因子了。
  • 在其他函数中，判别是否超越负载因子的时分都是运用上面这个函数。
  • loadFactorNum 和 loadFactorDen 是预界说的变量，它们相除便是负载因子 6.5。
  • bucketShift(B) 很简略，便是 2^B。

makeBucketArray 完结

在创立 map 的时分，运用了 makeBucketArray 来给 map 的桶分配内存，makeBucketArray 完结进程如下：

  1. 假如判别到 B >= 4，也便是初始化时需求分配的桶数量大于等于 2^4 = 16 的时分，则会预先分配溢出桶，分配的溢出桶个数为 2^(b-4) 个。
  2. 接着，给 map 的桶（buckets 字段）分配内存（包括了一般桶和溢出桶，一般桶和溢出桶的内存一次性分配，溢出桶的内存在一般桶后边）。
  3. 终究，判别到需求分配溢出桶的话（B >= 4），则将溢出桶的指针写入到终究一个一般桶的 overflow 字段。

分配 buckets 内存的两种状况：

  1. 假如 B < 4，那么分配内存的进程很简略，便是分配 buckets 所需求的内存，也便是分配一般桶所需求的内存就足够了，如下图：

go map 设计与实现

  1. 假如 B >= 4，那么分配内存的进程就相对杂乱，会预先分配一部分溢出桶。在后边需求创立溢出桶的时分，就会先运用这时分创立的溢出桶，而不是直接新建，如下图：

go map 设计与实现

阐明：

  • 分配 buckets 所需求的内存的时分，会分配一部分溢出桶所需求的内存，一般桶和溢出桶的内存是接连的，分配给溢出桶的内存就在一般桶的后边。
  • 在 makemap 中会新建 mapextra 结构体，用 nextOverflow 字段来保存溢出桶的指针，指向第一个溢出桶的方位。
  • 终究一个溢出桶的 overflow 指针（指向溢出桶的指针），指向了 buckets 进口，这儿并不是说将第一个一般桶作为终究一个溢出桶的溢出桶，而是一个符号作用。由于前面的溢出桶的 overflow 字段都是 nil，而终究一个溢出桶的 overflow 不是 nil，这样一来，咱们经过判别溢出桶的 overflow 是否为 nil 就能够知道是否是终究一个溢出桶。假如是终究一个溢出桶，那么将 map 里边的 extra.nextOverflow 字段设置为 nil，标明预分配的溢出桶用完了，后边假如再需求溢出桶的时分，就只能直接 new 一个了。
  • buckets 指针下面的一般桶和溢出桶所需求的内存巨细都是 t.bucketsize，也便是 bmap 所需求的内存巨细（当然是内存对齐之后的）。

具体完结如下：

// makeBucketArray 初始化 map bucket 底层的数组（分配 buckets 的内存）。
// 1<<b 是要分配的最小存储桶数。
// dirtyalloc 应该是 nil（不为 nil，标明清空 map），或许是 makeBucketArray 之前运用相同的 t 和 b 参数分配的桶数组。
// 假如 dirtyalloc 为 nil，将分配一段新的内存；不然将铲除 dirtyalloc 指向的内存，将其作为新分配的内存。
//
// 参数：
// t：底层标明 map 的类型
// b：bucket 的巨细为 2^b
// dirtyalloc: 不为 nil 标明要清空，用于 mapclear 函数。
//
// 回来值：
// buckets：正常桶数组进口
// nextOverflow：溢出桶数组进口
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
   // bucket 数量 = 1 << b
   base := bucketShift(b)
   nbuckets := base
   // 关于小的 b，溢出桶不太或许。避免核算开支。
   // 桶的数量小于 2^4 时分，由于数据较少、运用溢出桶的或许性较低，
   // 会省掉创立溢出桶的进程以削减额外开支。
   //
   // 可是大于等于 2^4 的时分，运用到溢出桶的或许性就会比较大，所以需求预先分配溢出桶。
   if b >= 4 {
      // 大于等于 2^4 的时分，额外创立 2^(B-4) 个溢出桶。
      nbuckets += bucketShift(b - 4)
      sz := t.bucket.size * nbuckets // 溢出桶所需求的内存巨细
      up := roundupsize(sz)          // 核算需求的内存巨细
      if up != sz {
         // 分配的内存与实践需求的内存不相同，
         // 或许会比 sz 大一点，重新核算 nbuckets。
         // 下面的 nbuckets 才是终究的 bucket 数量（一般桶 + 溢出桶的数量）
         nbuckets = up / t.bucket.size
      }
   }
   // buckets 地点的内存初始化/清空（mapclear）
   if dirtyalloc == nil {
      // 创立新的 bucket 数组
      buckets = newarray(t.bucket, int(nbuckets))
   } else {
      // 清空原有的内存
      buckets = dirtyalloc
      // buckets 所需求的总内存巨细（单位：字节）
      size := t.bucket.size * nbuckets
      // 清空 buckets 开端的 size 字节巨细的内存
      if t.bucket.ptrdata != 0 {
         // 有指针
         memclrHasPointers(buckets, size)
      } else {
         memclrNoHeapPointers(buckets, size)
      }
   }
   // 上面 b >= 4 的状况
   if base != nbuckets {
      // 处理一下预先分配的溢出桶。
      nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))  // buckets 和溢出桶内存是相邻的，核算第一个溢出桶的指针
      last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) // 终究一个溢出桶
      last.setoverflow(t, (*bmap)(buckets))                             // 终究一个溢出桶的 overflow 指针链接到第一个一般桶
   }
   // 回来一般桶、溢出桶的指针
   return buckets, nextOverflow
}

map 定位 key 的完结

咱们从上面的解说中应该很清楚 map 中 bucket 这个数据结构了（上面的 bmap 那个图），在做查找、修正、删去操作的时分， 都需求先依据 key 找到具体的键值对保存在哪一个 bucket 以及 bucket 中的哪一个方位，所以这个操作其实是十分关键的。 在开端下文之前，就先来讲讲 map 中是怎样定位一个 key 的。

其实定位的进程比较简略，假定现在要查找一个 key，那定位 key 的大概进程如下：

  1. 核算 hash: 依据 key 核算出其哈希值 hash。
  2. 核算 bucket: 哈希值对 buckets 长度取模（hash % len(buckets)），不过实践完结的时分运用了一种优化的办法，位运算（hash & (2^B - 1)），也便是由哈希值的最低 B 位来决议 key 终究运用哪一个 bucket（成果跟直接取模不相同，可是思想相同，都能确保得出的成果落在 len(buckets) 规模内）。
  3. 遍历 bucket（先是一般桶）里边的每一个槽（有 8 个），比较哈希值的最高 8 位（8 bit，也便是 tophash）是否持平，假如持平，则获取存储在 bucket 里边的 key，跟咱们需求定位的 key 做比较，假如持平，则阐明现已找到了 key，假如 key 不持平，则持续遍历下一个槽，直到 bucket 中一切的槽都被遍历完毕。
  4. 假如 bucket 里边的 8 个槽都遍历完了，仍然没有找到咱们需求找的 key。那么会从 bucket 的溢出桶去查找，溢出桶内的查找进程跟一般桶内的查找进程是相同的。
  5. 如此遍历，直到一切溢出桶都遍历完（在找不到的状况下才会遍历 bucket （一般桶）一切的溢出桶）。

这个查找进程能够标明为下图：

go map 设计与实现

留意：确认一个 key 需求 tophash 和 key 都持平，假如 tophash 持平而 key 不持平，则需求持续比较 bucket 中其他的槽。

map 读取数据的完结

从 map 中读取某一个键的办法主要有三个：mapaccess1、mapaccess2、mapaccessK，这三个办法的代码其实是大同小异的，所以这儿只拿 mapaccessK 来解说。

这三个办法的不同之处在于：

  • mapaccess1 只回来 key 对应的值，对应 v := map["k"] 这种写法。
  • mapaccess2 回来 key 对应的值，以及是否存在的标志，对应 v, ok := map["k"] 这种写法。
  • mapaccessK 用于遍历 map 的时分，回来 key 和 value，对应 for k, v := range map {} 这种写法（在迭代的时分在 mapiternext 里边调用）。

mapaccessK 的查找进程

mapaccessK 的查找进程大概便是上一个图说的，只不过下面的描绘愈加具体一点（em… 有点重复了）：

  • 判别 map 是否为空，为空直接回来
  • 核算 key 对应的哈希值 => hash
  • 核算桶的掩码 => m，hash & m 得到 bucket 的索引
  • 判别是否正在扩容，假如是，需求判别 key 对应的桶的数据是否现已被搬迁到新的桶里边：
    • 假如是，则需求重新的桶里边查找。
    • 假如还没有被搬迁，则需求从旧桶中读取。
  • 核算 tophash => top（也便是 hash 的最高 8 位）
  • 遍历找到的桶的每一个槽（slot/cell）
    • 比较 tophash 是否持平
    • 假如不等，判别桶后边是否都没有数据了（b.tophash[i] == emptyRest）
    • 假如没有数据了，跳出循环 => 找不到 key 对应的值
    • 假如还有数据，则持续遍历下一个槽
  • 假如找到一个槽的 tophash 跟上面核算的 tophash 持平，则比较 key 是否持平
    • 是，则回来对应的值（tophash 和 key 都持平，则标明找到了相应的 key，回来对应的值）。
    • 否，持续遍历下一个槽（仍然是先比较 tophash，tophash 持平则再比较 key 是否持平）
  • 溢出桶也找不到，则回来零值（及是否找到的标志）。

mapaccessK 的完结

关于整型的键值的 map，go 里边有针对优化的完结，但其实代码逻辑上都是差不多的，所以不细说了。下面来看看 mapaccessK 的完结：

// 在迭代 map 的时分，回来键值对。
// 参数：
// t: map 类型元信息（记载了 map 中的 key/value 的类型等信息，比方 key 的巨细，可用于核算内存偏移）
// h: map 结构体类型（也便是实践的哈希表类型）
// key: 需求查找的 key
// 回来值：
// 第一个回来值：当时遍历到的 key 的指针
// 第二个回来值：当时遍历到的 key 对应的值的指针
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
   // map 是空的
   if h == nil || h.count == 0 {
      return nil, nil
   }
   // 依据 key 和 hash0 核算 hash
   hash := t.hasher(key, uintptr(h.hash0))
   // hash 的掩码，相似 IP 的掩码
   //（比方，假定 B = 3，一共有 8 个元素，索引为 0～7，那么掩码 m 标明为二进制便是 111）。
   // 用于跟 hash 值做 & 运算（hash & m），得到 hash 对应 bucket 的索引（0～m）
   m := bucketMask(h.B)
   // 依据 hash 核算 bucket 地址，b 是 hash 匹配到的 bucket
   b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
   // 正在扩容，假如 bucket 还没搬迁到新的地址，则需求从 oldbuckets 中拜访
   if c := h.oldbuckets; c != nil {
      // 不是等量扩容，需求从旧桶中读取，所以 m 要移除最高位（右移一位）
      if !h.sameSizeGrow() {
         // 不是等量扩容，则将 m 除以 2，由于是 2 倍扩容，
         // 所以 buckets 的巨细为 oldbuckets 长度的 2 倍，
         // 除以 2 才是旧的桶数量
         m >>= 1
      }
      // key 在 oldbuckets 中的地址
      oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
      if !evacuated(oldb) {
         // b 没有搬迁到新的 buckets 中，还在 oldbuckets 中
         // 则需求从旧桶中查找
         b = oldb
      }
   }
   // 核算 tophash
   top := tophash(hash)
bucketloop:
   for ; b != nil; b = b.overflow(t) {
      // 从 bucket 中查找，一个 bucket 能够存储的元素个数是 bucketCnt，也便是 8
      for i := uintptr(0); i < bucketCnt; i++ {
         // tophash 不匹配，必定不是这个槽
         if b.tophash[i] != top {
            // bucket 剩下的槽是空的，不必再找了，跳出循环
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            // 持续比较下一个槽
            continue
         }
         // tophash 匹配
         // 接下来将这个槽的 key 取出来
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         // key 是指针类型
         if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
         }
         // 比较 key 跟 k 是否持平
         if t.key.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 k, e
         }
         // 留意：履行到这儿，阐明 tophash 持平，
         // 可是 key 不匹配，仍然需求持续遍历。
      }
   }
   // 一般桶和溢出桶的一切槽都找不到，回来 nil
   return nil, nil
}

这儿需求留意的是，假如在扩容的进程中查找，会先判别数据是否现已被搬迁到新桶，假如还没有被搬迁，则需求从旧的桶中查找。

mapaccessK 关键代码

  1. bucket 的定位代码
m := bucketMask(h.B)
// b 便是定位到的 bucket 地点的内存地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

bucket 索引（hash & m）的定位办法如下：

go map 设计与实现

由于 buckets 是指向 bmap 的指针数组，所以咱们能够经过 buckets 加上 bucket 的索引，就能够定位到 bucket 的内存地址。 由于每一个 bmap 的巨细是 t.bucketsize，所以 bucket 的索引乘以 t.bucketsize，也即 (hash&m)*uintptr(t.bucketsize)，便是 bucket 的相对偏移量。 然后 buckets 的地址加上 bucket 的相对偏移量，就能够定位到 bucket 的内存地址。

go map 设计与实现

咱们需求留意的是，咱们核算得到 bucket 的指针后，需求将其转换为 bmap 类型的指针，才干进行后续的操作。

然后 key 和 value 也是经过相似的指针运算来定位的。需求阐明的是：

  • add 函数是做指针算术运算的函数，具体来说便是 add(a, b) 便是 a 地址加上 b 的偏移量，回来的是 unsafe.Pointer 类型的指针。
  • unsafe.Pointer(b) 是 bucket 的内存地址
  • dataOffset 是 bucket 中第一个 key 的地址偏移量，
  • t.keysize 是 key 的巨细
  • t.elemsize 是 map 值的巨细
  • bucketCnt 是 bucket 中槽的数量（8 个，预界说的常量）。

然后咱们能够结合上面的 bmap 内存布局图来了解上面指针核算的代码。

// 读取 bucket 中的第 i 个 key。
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 读取 bucket 中的第 i 个 value
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
  1. b.tophash[i] == emptyRest 判别的了解

go map 设计与实现

emptyRest 是一个比较特殊的符号，它标明 bucket 中的后续槽都是空的。 在 map 删去元素的时分，会判别后边还有没有元素，假如没有元素的话，就会将 b.tophash[i] 设置为 emptyRest。 这样在查找的时分，就能够经过 b.tophash[i] == emptyRest 来判别后边的槽都是空的，就不需求持续遍历了。

  1. indirectkey 和 indirectelem 的了解

咱们发现上面读取 key 和 value 的时分有一个比较特别的操作：

if t.indirectkey() {
    k = *((*unsafe.Pointer)(k))
}
if t.indirectelem() {
    e = *((*unsafe.Pointer)(e))
}

信任不少读者第一次看到这几行代码的时分会跟我相同有点懵逼，从 maptype 的界说咱们能够看出一点端倪：

func (mt *maptype) indirectkey() bool { // store ptr to key instead of key itself
   return mt.flags&1 != 0 // 存储了 key 的指针，而不是 key 自身
}
func (mt *maptype) indirectelem() bool { // store ptr to elem instead of elem itself
   return mt.flags&2 != 0 // 存储了 elem 的指针，而不是 elem 自身
}

简略来说，便是 go 底层在有时分会将 key 和 value 保存为指针，而不是直接保存 key 和 value 自身。 这样一来，go 里边的 map 操作就需求依据 key 和 value 的类型来判别是否需求进行指针解引证，也便是取出实践的 key 和 value。

map 写入和修正的规划与完结

在 go 中，map 的写入和修正都是经过 mapassign 函数来完结的，由于写入和修正本质上是同一个操作，都是找到对应的 key，然后修正对应的值。

mapassign 的完结进程

  1. 核算 key 的 hash 值。
  2. 假如 buckets 还没有初始化，则进行分配内存。
  3. 核算出 bucket 的索引。
  4. 假如正在扩容，则搬迁当时即即将操作的 bucket（也便是上一步核算出来的索引对应的 bucket）。
  5. 核算 tophash。
  6. 遍历 bucket 中的槽，记载下第一个空的槽的 tophash 索引指针、key 指针，value 指针。假如终究找不到 key 的时分，会刺进到这儿。
  7. 假如 bucket 的一切桶都找不到 key，则判别是否需求扩容，需求的话就进行扩容，然后再履行 6 的操作。
  8. 别的一种状况，不需求扩容，并且 bucket 以及它的溢出桶也满了，则需求新建溢出桶来保存 key
  9. 终究，将 tophash/key/value 刺进到需求 bucket 第一个空的槽。又或许假如现已存在，对 value 进行更新。

mapassign 图解

能够分两种状况：

  1. 一般桶和溢出桶都找不到 key 的状况下，将 key 刺进桶中第一个空的槽

go map 设计与实现

  1. 在 bucket 中找到了 key，则会对其进行更新

go map 设计与实现

关于 key 和 value 的存储，有以下两种状况：

  1. 直接保存在 bucket 中：

这样在咱们需求修正 key/value 的时分，经过 bucket 加上 索引 * keysize/valuesize 就能够得到对应键值存储的实践内存。

go map 设计与实现

  1. 在 bucket 中保存的是 key/value 的内存地址（unsafe.Pointer）类型

这样假如咱们需求修正/读取实践的键值的时分，就需求先从 bucket 中获取这个指针，然后解引证得到实践存储键值的内存指针。

go map 设计与实现

留意：在咱们做如下运算的时分（假定 bucket 没有存储实践的 key，而是存储了 key 的指针）：

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

得到的成果是，指向 keys[i]（也便是第 i 个 key）的指针（unsafe.Pointer 类型）。 假如 key 保存在 bucket 中，经过这个指针咱们就能够读写 key 了。 不然，标明这个指针指向的内存存储的仅仅一个指针，假如咱们需求修正实践的 key， 就需求经过 key 指针（A）拿到这儿存储的指针（B），然后再经过 B 来修正实践的 key。

go map 设计与实现

对 value 的读写同理。

mapassign 源码分析

扩容的操作后边会有解析，这一节就先不细说了。

这个函数的界说如下：

// 功用：刺进 key 或许修正 map 中的 key
// 参数：
// t：map 类型元信息
// h：map 结构体（实践保存键值对的当地）
// key：咱们要修正或许刺进的 key
// 回来值：
// 只要一个，那便是咱们刺进或许修正之后的值。
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   if h == nil {
      panic(plainError("assignment to entry in nil map"))
   }
   // 并发写，直接报错
   if h.flags&hashWriting != 0 {
      fatal("concurrent map writes")
   }
   // 核算 key 的哈希值（是一个无符号整数）
   hash := t.hasher(key, uintptr(h.hash0))
   // 在调用 t.hasher 之后设置 hashWriting，
   // 由于 t.hasher 或许会 panic，在这种状况下，咱们实践上还没有进行写操作。
   // 写符号。（假如读操作发现有写标志则会报错）
   h.flags ^= hashWriting
   // 假如 buckets 是空，则新建一个 bucket
   if h.buckets == nil {
      h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   }
again:
   // bucket 指示第几个 bucket（命名貌似有点不合适）
   bucket := hash & bucketMask(h.B)
   // 正在扩容的话，则将 bucket 搬迁到新桶
   if h.growing() {
      growWork(t, h, bucket)
   }
   // b 为即即将写入的 bucket
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   // 核算 key 的 tophash
   top := tophash(hash)
   var inserti *uint8         // 要刺进的 tophash 地址
   var insertk unsafe.Pointer // 要刺进的键地址
   var elem unsafe.Pointer    // 要刺进的值地址
bucketloop:
   for {
      // 循环 bucket 的槽
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            // tophash 不匹配，并且当时槽为空，则记载要刺进的方位（找不到 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))
               // 为什么找到了能够刺进的当地，不间断循环？
               // 原因是，这个函数是寻觅现已存在的 key 的（刺进和修正都是用这个函数），
               // 假如对应的 key 保存到了后边的槽里边的话，这儿直接间断循环便是不对的。
               // 由于在这种状况下，理应更新后边的那个槽。
            }
            // bucket 没有找到对应的 key，一起 bucket 中剩下的槽都是空的。
            // （这意味着 map 中找不到 key，需求刺进这个 key 了）
            // 间断对 bucket 里边槽的遍历。
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            // 尽管找到了闲暇的槽，但仍是要查看 bucket 中的其他槽，看 key 是否现已存在。
            // （假如存在的话，修正 key 对应的值就能够了，当然这个函数里边不会修正，而是回来值的地址，从函数外部修正）
            // 这个很好了解，保存值的指针都拿到了，想修正就很简略了。
            // 假如 key 现已存在，则回来已存在 key 的对应的 elem 的地址。
            continue
         }
         // tophash 持平，仍然需求比较 key 是否持平。
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
         }
         // 可是 key 不想等，持续比较下一个槽
         if !t.key.equal(key, k) {
            continue
         }
         // tophash 持平、key 也持平，阐明现已存在，更新它即可
         // 用 key 更新 k
         if t.needkeyupdate() {
            typedmemmove(t.key, k, key)
         }
         // 核算 value 地点的地址
         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
         // 找到了 key，直接跳转到 done
         goto done
      }
      // 当时的桶里边一切槽都找不到。
      // 持续遍历溢出桶（在溢出桶中查找 key 是否存在/有没有空余的槽）
      ovf := b.overflow(t)
      if ovf == nil {
         // 溢出桶也找不到，跳出循环
         break
      }
      // b 指向下一个溢出桶，下次循环遍历这个溢出桶
      b = ovf
   }
   // 未找到 key，需求刺进这个新的 key。
   // 假如咱们到达了最大负载系数或许咱们有太多的溢出桶，
   // 一起，假如还没有开端扩容，那么现在开端扩容。
   if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
      hashGrow(t, h)
      // 扩容哈希表会使一切内容无效，因而需求再次测验刺进。
      // （上面循环获取到的刺进方位的指针现已失效了，扩容之后刺进的方位改动了，所以需求再次核算要刺进的 bucket，以及要刺进的槽中的方位）
      goto again
   }
   // 标明没有找到能够刺进的当地，则新建一个溢出桶来保存，
   // 溢出桶的第一个元素就用来保存 key，回来溢出桶第一个元素 elem 的地址
    // （这意味着，咱们要刺进的桶，一切的槽都有数据了，并且也不是咱们要找的 key，所需求溢出桶了）
    if inserti == nil {
      // 当时存储桶及其连接的一切溢出存储桶已满，分配一个新的溢出桶。
      newb := h.newoverflow(t, b)
      // 溢出桶的第一个 tophash 的指针
      inserti = &newb.tophash[0]
      // 溢出桶的第一个 key 的指针
      insertk = add(unsafe.Pointer(newb), dataOffset)
      // 溢出桶的第一个 value 的指针
      elem = add(insertk, bucketCnt*uintptr(t.keysize))
   }
   // 在刺进方位存储新 key/elem
   if t.indirectkey() {                   // 这意味着需求给 key 分配内存来保存它
      kmem := newobject(t.key)           // 给 key 分配内存（kmem 是保存 key 的内存指针）
      *(*unsafe.Pointer)(insertk) = kmem // bucket 里边的 key 保存新分配的内存指针
      insertk = kmem                     // insertk 指向新分配的地址（跟上一行并不重复）
      // 终究作用是，insertk 和 kmem 指向了新分配的保存 key 的内存地址。
      // 当然，insertk = kmem 不需求也能够，但这样一来下面也要改成：
      // if t.indirectkey() {
      //     typedmemmove(t.key, kmem, key)
      // } else {
      //     typedmemmove(t.key, insertk, key)
      // }
   }
   if t.indirectelem() {
      vmem := newobject(t.elem)       // 给 elem 分配内存
      *(*unsafe.Pointer)(elem) = vmem // bucket 里边 elem 的槽保存新分配的地址
   }
   // 移动 key 到 insertK（保存新的 key）
   typedmemmove(t.key, insertk, key)
   // 保存 tophash
   *inserti = top
   // map 元素个数 +1
   h.count++
done:
   // 并发写则报错（多个协程一起写 map）
   if h.flags&hashWriting == 0 { // 写标志被铲除了
      fatal("concurrent map writes")
   }
   // 铲除写标志
   h.flags &^= hashWriting
    // bucket 中的值保存的是指针，这个时分就不能回来 bucket 中值的地址了，而是回来 bucket 中值指向的别的一个地址的指针。
   if t.indirectelem() {
      // 获取指向 elem 实践存储地址的指针
      elem = *((*unsafe.Pointer)(elem))
   }
   // 回来存储值的指针
   return elem
}

有几点要留意的：

  1. go 中 map 是不答应并发读写的，假如有，直接报错。
  2. 这儿边咱们看到了有扩容的操作，在 go 中，map 的扩容发生在刺进、修正和删去的时分，是一种渐进式扩容的办法，每次扩容会搬迁两个 bucket，具体的后边讲到扩容的时分会细说。
  3. 在 bucketloop 这个循环中，会记载下第一个空的槽，在找不到 key 的时分会进行刺进操作。
  4. 假如找到，则回来保存值的地址的指针。假如没找到，则将 key 刺进到上一步找到的空的槽中，假如也没有空的槽，则会新建溢出桶来保存新刺进的 key。
  5. 在这个函数中，会判别刺进之后是否超越负载因子，又或许溢出桶是否太多，来决议是否扩容。

关于 key 匹配的进程，其实跟上面的 mapaccess 是相同的进程，先找一般桶，然后查找溢出桶。

map 删去 key 的完结

关于删去操作，其实有一些操作上面现已说过了，如怎样定位一个 key。所以下面的叙述会偏重解说跟删去操作密切相关的操作。

map 删去 key 的进程

  1. 定位 key 地点 bucket，核算 tophash。
  2. 遍历 bucket 的每一个槽，比较 tophash 以及 key，一般桶中查找不到会持续查找溢出桶。
  3. 假如查找到 key 的话，会清空对应 key 在 bucket 内存中的 tophash、key 和 value。
  4. 假如后边的槽没有元素了，则设置 emptyRest 符号。这样在后续查找的时分就能够避免不必要的查找了。

map 删去进程图解

删去的进程比较简略，定位 key 的进程上面有过具体的解说了，这儿只具体画图阐述一下 emptyRest 的符号设置：

go map 设计与实现

map 删去源码分析

// 从 map 中删去 key（以及对应的 elem）
// 参数：
// t：map 类型元数据的结构体
// h：实践保存键值对的桶
// key：需求删去的 key
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
   // map 是空的
   if h == nil || h.count == 0 {
      // 假如 key 的类型不行哈希则 panic
      if t.hashMightPanic() {
         t.hasher(key, 0) // see issue 23734
      }
      return
   }
   // 并发写则抛出 fatal 过错
   if h.flags&hashWriting != 0 {
      fatal("concurrent map writes")
   }
   // 核算 key 的 hash
   hash := t.hasher(key, uintptr(h.hash0))
   // 在调用 t.hasher 之后设置 hashWriting，
   // 由于 t.hasher 或许会 panic ，在这种状况下，咱们实践上没有履行 write（delete）。
   h.flags ^= hashWriting
   // 核算 key 落在哪一个 bucket 中
   bucket := hash & bucketMask(h.B)
   // 假如正在扩容，则搬迁 bucket 到新的内存地址中（搬迁到新的桶）
   // (搬迁当时正在拜访的 bucket)
   if h.growing() {
      growWork(t, h, bucket)
   }
   // 获取 bucket 实例（key 地点的 bucket）
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   // 记载原始的 bucket 实例
   //（目的是为了方便加 emptyRest 符号）
   bOrig := b
   // 核算 tophash
   top := tophash(hash)
search:
   // 在 bucket 内进行查找
   for ; b != nil; b = b.overflow(t) {
      // 遍历 bucket 的每一个槽
      for i := uintptr(0); i < bucketCnt; i++ {
         // tophash 不想等的时分，需求判别后边是否还有元素
         if b.tophash[i] != top {
            // 从 i 开端 bucket 后边都是空的了，
            // 间断查找进程（去除写符号，函数履行完毕）
            if b.tophash[i] == emptyRest {
               break search
            }
            // 还有元素，持续查找
            continue
         }
         // tophash 持平
         // 获取 key 在 bucket 中的内存地址
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         k2 := k // k2 代表的是指向实践存储 key 的指针（unsafe.Pointer） 
         // k2 指向原始的地址
         if t.indirectkey() {
            k2 = *((*unsafe.Pointer)(k2))
         }
         // key 不想等，持续查看下一个 slot（continue）
         if !t.key.equal(key, k2) {
            continue
         }
         // 只要在键中有指针时才铲除键。
         // 清空 key 的内存
         if t.indirectkey() {
            // 铲除 bucket 里边保存 key 的内存
            //（bucket 仅仅存储了 key 的指针）
            *(*unsafe.Pointer)(k) = nil
         } else if t.key.ptrdata != 0 {
            // 铲除包括指针的 key
            memclrHasPointers(k, t.key.size)
         }
         // 值的地址
         e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
         // 清空值
         if t.indirectelem() {
            // 铲除 bucket 里边保存 elem 的内存
            *(*unsafe.Pointer)(e) = nil
         } else if t.elem.ptrdata != 0 {
            // 铲除包括指针的 elem（值）
            memclrHasPointers(e, t.elem.size)
         } else {
            // 铲除不包括指针的 elem 的内存
            memclrNoHeapPointers(e, t.elem.size)
         }
         // tophash 设置为空符号
         b.tophash[i] = emptyOne
         // 假如 bucket 现在以一堆 emptyOne 状况完毕，
         // 将这些状况更改为 emptyRest 状况。
         // 最好将其作为一个独自的函数，但 for 循环当时不行内联。（所以用 goto）
         if i == bucketCnt-1 {
            // 要删去的 key 是 bucket 里边的终究一个元素。
            // 一起还有溢出桶，并且溢出桶里边还有元素 => 标明当时删去的 key 不是 bucket 以及溢出桶里边的终究一个元素。
            if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
               // 不是终究一个元素
               goto notLast
            }
         } else {
            // 要删去的 key 不是 bucket 的终究一个元素。
            // 并且后边还有元素。
            if b.tophash[i+1] != emptyRest {
               goto notLast
            }
         }
         // 履行到这儿的时分，标明刚刚删去的 key 是 bucket 以及溢出桶中的终究一个元素。
         // 假如不是终究一个元素的话，上面的 if 判别现已跳转了。
         // 下面的 for 循环做的工作是：
         // 1. 将当时 key 的标志设置为：emptyRest，标明后边没有元素了。
         // 2. 从 bucket 的第一个 key 动身遍历一切的槽（包括溢出桶），
         //    将终究一个元素今后一直到被删去的 key 的中间的一切槽符号为 emptyRest
         // 目的是，在后续遍历的时分能够避免一些不必要的查找操作，见到 emptyRest 就能够直接间断循环了。
         // 比方，bucket 里 key 的内存布局为 | nil | a | nil | nil | b | nil |
         // b 被删去的时分，b 以及 a 后边的两个元素都要符号为 emptyRest（溢出桶同理）
         for {
            // 给当时遍历到的 bucket 槽打上 emptyRest 符号
            b.tophash[i] = emptyRest
            if i == 0 { // 当时的桶遍历完了（由于是从后往前遍历）
               // b 是一般桶（不是溢出桶）
               if b == bOrig {
                  // 一切空的槽都处理完了
                  break
               }
               // b 是上一次循环处理的桶
               c := b // c 是上一个 b 
               // 查找上一个存储桶，在其终究一个条目处持续。 
               // 如：bucket <- overflow1 <- overflow2 <- ... <- overflowN
               // 假定 c 是 overflow2，那么下面的循环过后，b 便是 overflow1
               // prevB.overflow = b  => 找 prevB，也即：遍历完当时的桶，找前一个桶。
               for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
               }
               // b 指向了前一个 bucket（前一个桶）
               // 处理前一个 bucket 的终究一个槽
               i = bucketCnt - 1
            } else {
               // 持续处理前一个槽
               i--
            }
            // 找到了一个不是空的槽，标明有数据了，不需求再打 emptyRest 符号了。
            if b.tophash[i] != emptyOne {
               break
            }
         }
         // 被删去的元素假如不是终究一个元素，直接跳转到这儿。
      notLast:
         // 找到了元素，并且删去了。
         // map 的元素个数减 1
         h.count--
         // 重置哈希种子，使攻击者更难重复触发哈希抵触。见 issue 25237。
         if h.count == 0 {
            h.hash0 = fastrand()
         }
         // 在 bucket 内找到了对应的元素，并且删去了。
         // 退出循环。
         break search
      }
   }
   // 假如当时没有写符号，则抛出 fatal 过错（不能并发读写 map）
   if h.flags&hashWriting == 0 {
      fatal("concurrent map writes")
   }
   // 铲除写符号
   h.flags &^= hashWriting
}

留意：

  1. go map 不答应并发写，所以假如发现有并发读写，则抛出 fatal 过错。
  2. 假如删去的是终究一个元素，则需求往前遍历，将每一个空的槽设置为 emptyRest 状况。
  3. 假如是 indirectkey、indirectelem，在删去的时分，只会将 bucket 中的指针置为 nil，关于实践的 key 和 value 不会进行处理。（无所谓，GC 会出手）。

map 的扩容完结

从上面的解说中，咱们知道，底层存储 key/value 的是 bucket，而 bucekt 的巨细是一段有一定巨细的接连内存。 假如咱们刺进的元素过多，咱们初始化时分配的 bucket 的内存就会放不下了，这个时分 go 的 map 会有两种办法处理这个问题：

  1. 运用溢出桶（在 bmap 的上再链接一个 bmap，也便是溢出桶，一般桶放不下的时分，就放溢出桶中）
  2. 分配新的更大的空间来寄存现有的这些键值对。在 go 里边新分配的内存空间将会是本来的 2 倍。

map 扩容的条件

map 的扩容发生在刺进或许修正或许删去 key 的时分，扩容的条件在 mapassign 中写了：

// 条件：
// 1. 没有在扩容
// 2. 超越负载因子
// 3. 太多溢出桶
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
}
// 判别是否超越负载因子。
func overLoadFactor(count int, B uint8) bool {
   return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// 判别是否有太多的溢出桶了
// 多的规范是：
// B <= 15 的时分，溢出桶数量大于 2^B 的时分
// B > 15 的时分，溢出桶的数量大于 2^15 的时分
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
   // 假如阈值太低，咱们会做额外的作业。
   // 假如阈值太高，则增加和收缩的 map 会保存大量未运用的内存。
   // “太多” 意味着（大约）与常规桶相同多的溢出桶。
   // 有关具体信息，请拜见incrnoverflow。
   // B > 15 => 2 ^ 15，B <= 15 => 2 ^ B
   if B > 15 {
      B = 15
   }
   return noverflow >= uint16(1)<<(B&15)
}

hashGrow 完结

hashGrow 是被用来分配新的内存空间的，新的内存空间将被用来保存旧的 buckets。需求留意的是，这个函数里边并没有做数据搬迁的操作。 go 的 map 扩容的时分，数据搬迁的办法是渐进式扩容，在咱们刺进/修正/删去 key 的时分会搬迁 2 个 bucket，这样能够避免性能的瞬时颤动。 咱们熟知的 redis 的扩容进程也是渐进式扩容的。

下面是 hashGrow 的完结源码：

// hash 扩容（这个办法仅仅分配了空间，实践上还没有做数据仿制的操作）
// 参数：
// t：map 类型元信息
// h：实践保存键值对的结构体
func hashGrow(t *maptype, h *hmap) {
   // 扩容的两种状况：
   // 1、假如咱们到达了负载系数，就要进行 2 倍扩容。
   // 2、不然，假如溢出桶太多，进行等量扩容。
   bigger := uint8(1)
   // 没有超越负载因子，进行等量扩容
   if !overLoadFactor(h.count+1, h.B) {
      bigger = 0 // 等量扩容
      h.flags |= sameSizeGrow
   }
   // 记载旧的 buckets
   oldbuckets := h.buckets
   // 分配新的内存空间，oldbuckets 将会被渐进式搬迁到 newbuckets 中
   newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
   // flags 符号有运用旧桶
   // 正在迭代的时分扩容
   // 先把 h.flags 中的迭代符号位铲除。
   // 终究假如发现 h.flags 中还有迭代符号位，阐明在扩容的进程中有新的迭代操作，
   // 那就把它转移到 oldIterator 中。
   flags := h.flags &^ (iterator | oldIterator)
   if h.flags&iterator != 0 {
      flags |= oldIterator
   }
   // 提交扩容操作
   h.B += bigger // 加上扩容的数量
   h.flags = flags
   h.oldbuckets = oldbuckets // 记载旧桶
   h.buckets = newbuckets    // 指向新的桶数组
   h.nevacuate = 0           // 0 个桶已完结搬迁（当时函数仅仅分配空间，不做搬迁）
   h.noverflow = 0           // 一切溢出桶没有了（移动到了 oldoverflow）
   // 记载扩容前的溢出桶
   if h.extra != nil && h.extra.overflow != nil {
      if h.extra.oldoverflow != nil {
         throw("oldoverflow is not nil")
      }
      h.extra.oldoverflow = h.extra.overflow
      h.extra.overflow = nil
   }
   // 扩容之后，h.B+bigger >= 4 了，预分配了溢出桶（扩容前没有溢出桶）
   // 所以这儿要记载溢出桶
   if nextOverflow != nil {
      if h.extra == nil {
         h.extra = new(mapextra)
      }
      h.extra.nextOverflow = nextOverflow
   }
   // 哈希表数据的实践搬迁进程是经过 growWork() 和 evacuate() 增量完结的。
}

数据搬迁的两条线

go map 在扩容的时分，数据搬迁会有两条线进行：

  1. 从第一个 bucket 开端搬迁。
  2. 刺进、修正、删去的时分，key 的哈希值定位到的 bucket 会被搬迁。

具体如下图：

go map 设计与实现

假如现已被搬迁，则不再需求搬迁。

这样一来就能够确保在一定的操作次数之后，悉数 bucket 都被搬迁。就算你每次刺进、修正、删去都是同一个 key（也便是同一个 bucket）， 咱们第一条线的搬迁都会在每次写操作的时分，搬迁一个 bucket。这样无论怎样，写操作到了一定次数之后，一切的 bucket 都会被搬迁了。

什么时分 bucket 搬迁之后下标会改动？

当然这儿说的是增量扩容，假如是等量扩容，bucket 的下标不会改动。

先说答案：hash & m 的最高位是 1 的时分。

咱们知道，在定位 bucket 的时分是经过 hash & m 的办法来定位 bucket 的索引的（具体能够看上面定位 key 的那一节）， 而 2 倍扩容之后，bucket 的长度是本来的 2 倍，转换为二进制的时分，便是在本来的基础上多了一位，所以 hash & m 的成果就会多一位， 而最高的那个二进制位假如是 1，阐明 hash & m 的成果是大于新的 bucket 数组长度的一半的（也便是比本来的索引都要大）。 那么会最高位是 1 会比本来的索引会大多少呢？答案是 bucket 数组的长度的一半（也便是 2^(B-1)）：

go map 设计与实现

咱们能够再看看之前的那个核算 bucket 索引的图：

go map 设计与实现

咱们会发现，当 B = 3 的时分，不论 hash 是什么，hash & m 的成果都是 0~7。 而只要当 B = 4 的时分，hash & m 的成果才有或许落入 8~15 规模内，并且只要 hash & m 的最高位是 1 的时分才有或许。

所以结论是，当 hash & m 的最高位是 1 的时分，bucket 的下标就会改动。 而 hash % m 的其他位跟之前是相同的，所以下标增加的规模其实便是 2^(B - 1)，也便是旧的 buckets 的个数。

bucket 搬迁图解

go map 设计与实现

阐明：

  • oldbuckets 是搬迁前的桶，buckets 是搬迁后的桶（也便是当时的 h.buckets）。
  • hash & m 为 0xxx 的时分，会搬迁到 x 这个 bucket 中。
  • hash & m 为 1xxx 的时分，会搬迁到 x + 2^(B-1) 这个 bucket 中（也便是 y 中），由于 1000 便是 2^(4 - 1)。

假定需求搬迁的是 oldbucket，下标为 3，那么 oldbucket 里边的 key 或许搬迁的方位只或许是右边的 x 和 y 指向的 bucket。 这取决于 oldbucket 里边的 key 哈希值的倒数第 4 位； 假如是 0，那么就搬迁到 x 指向的 bucket，假如是 1，那么就搬迁到 y 指向的 bucket。

oldbucket 中一切的 key 只会搬迁到 x 或 y 中。一起 x 和 y 也只或许有 oldbucket 的 key，不或许有其他旧的 bucket 的 key。这是由 hash & m 能够推断出来的。

bucket 搬迁源码分析

开端之前，咱们要记住 x 和 y 是怎样来的。

在开端看代码之前，咱们需求明确一点：尽管整个哈希表是渐进式搬迁的，可是单个 bucket 的搬迁不是渐进式的。

  1. 咱们先看看 growWork 函数：

这是搬迁桶的函数，一次会搬迁两个桶。不过实践上并不是严格的两个，由于搬迁的函数会先判别桶是否现已被搬迁， 假如桶还没有被搬迁，才会进行搬迁，假如桶现已被搬迁则不做任何操作。

// 桶搬迁
// 参数：h 需求扩容的 map，t map 类型信息，bucket 旧桶的索引
// 1、搬迁当时拜访到的桶（mapassign、mapdelete 的时分）
// 2、持续逐个搬迁 bucket，直到搬迁完结（这个是从第一个桶开端搬迁的）
func growWork(t *maptype, h *hmap, bucket uintptr) {
   // 搬迁当时拜访到的桶
   evacuate(t, h, bucket&h.oldbucketmask())
    // 持续逐个搬迁 bucket，直到搬迁完结
   if h.growing() {
      evacuate(t, h, h.nevacuate)
   }
}
  1. 然后看看 evacuate 函数：

这个便是实践做搬迁操作的函数。它会依据 hash & m 的倒数第 B 位是否为 1 来决议将 key 搬迁到 h.buckets 的前半部分仍是后半部分。

// 搬迁的目的地（旧桶 -> 方针桶）
// evacuate 中会界说两个这个 evacDst 变量，
// 一个指向 h.buckets 的前半部分，一个指向后半部分。（对应前一个图的 x，y）
// 搬迁的时分，会依据 key 的哈希值的倒数第 4 位来决议搬迁到哪个 evacDst 中。
type evacDst struct {
   b *bmap          // 搬迁目的地 bucket
   i int            // key/elem 在搬迁方针 bucket 里边对应的下标
   k unsafe.Pointer // 方针 bucket 下一个保存 key 的地址指针
   e unsafe.Pointer // 方针 bucket 下一个保存 elem 的地址指针
}
// 扩容的时分，bucket 搬迁的完结
// oldbucket 需求搬迁的旧桶索引
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
   // b 指向旧桶
   b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   // 扩容之前的桶的数量
   // oldbucket+newbit 对应 y，oldbucket 对应 x
   newbit := h.noldbuckets()
   // 假如 b 没有搬迁，则进行搬迁
   if !evacuated(b) {
      // xy 包括 x 和 y（低和高）搬迁目的地。
      // 搬迁的时分，在 h.buckets 中，前 noldbuckets 个桶便是 x，后 noldbuckets 个桶便是代表 y。
      var xy [2]evacDst
      // x 存储了新桶的地址
      x := &xy[0]
      // x 指向 oldbucket 或许搬迁到的新桶（h.buckets 的前半部分）
      x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
      // x 桶中下一个用来保存旧桶的 key 的地址
      x.k = add(unsafe.Pointer(x.b), dataOffset)
      // x 桶中下一个用来保存旧桶的 elem 的地址
      x.e = add(x.k, bucketCnt*uintptr(t.keysize))
      // 假如不是等量扩容（有或许会搬迁到 oldbucket+newbit 的方位上）
      if !h.sameSizeGrow() {
         y := &xy[1]
         // y 指向增量空间上的第 oldbucket+newbit 个方位
         y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
         // y 桶中下一个保存旧桶 key 的地址
         y.k = add(unsafe.Pointer(y.b), dataOffset)
         // y 桶中下一个保存旧桶 elem 的地址
         y.e = add(y.k, bucketCnt*uintptr(t.keysize))
      }
      // 开端搬迁旧桶（一起也会搬迁溢出桶）
      for ; b != nil; b = b.overflow(t) {
         // 旧 bucket 上第一个 key
         k := add(unsafe.Pointer(b), dataOffset)
         // 旧 bucket 上第一个 value
         e := add(k, bucketCnt*uintptr(t.keysize))
         // 遍历 bucket 的槽
         // 获取需求搬迁的 key/elem(k/e) 对，搬迁到新桶上(&xy[useY])
         for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
            // 获取旧的 tophash
            top := b.tophash[i]
            // bucket 的这个槽是空的
            if isEmpty(top) {
               // 写入已搬迁符号
               b.tophash[i] = evacuatedEmpty
               // 处理下一个 key/elem
               continue
            }
            // tophash 过错
            if top < minTopHash {
               throw("bad map state")
            }
            // 仿制一份 k
            k2 := k
            // k2 指向实践的 key
            if t.indirectkey() {
               k2 = *((*unsafe.Pointer)(k2))
            }
            // useY 决议了是搬迁到 x 仍是 y，假如是等量扩容，那么便是搬迁到 x
            var useY uint8
            // 假如不是等量扩容
            if !h.sameSizeGrow() {
               // 核算哈希以做出搬迁决议（是否需求将此 key/elem 搬迁到桶 x 或桶 y）。
               hash := t.hasher(k2, uintptr(h.hash0))
               if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
                  // 下面这段是原英文注释的翻译（或许不太精确）：
                  // 假如 key != key（不是一个数字），则散列或许（并且或许）与旧散列彻底不同。
                  // 此外，它是不行再现的。
                  // 在迭代器存在的状况下，再现性是必需的，由于咱们的搬迁决策有必要与迭代器所做的任何决策相匹配。
                  // 走运的是，咱们能够恣意发送这些 key。
                  // 此外，tophash 关于这些类型的 key 没有意义。咱们让 tophash 的最低位的决议怎样搬迁。
                  // 咱们为下一个级别重新核算一个新的随机 tophash，这样在屡次扩容后，这些 key 将均匀散布在一切桶中。
                  useY = top & 1
                  top = tophash(hash)
               } else {
                  // 原理参阅上面那个图。
                  if hash&newbit != 0 { // 取决于 oldB + 1 位是 0 仍是 1
                     useY = 1
                  }
               }
            }
            if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
               throw("bad evacuatedN")
            }
            // 记载旧桶的搬迁状况
            b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
            // dst 是搬迁的方针 bucket
            dst := &xy[useY]
            // 方针 bucket 装不下了，运用溢出桶
            if dst.i == bucketCnt {
               // 创立溢出桶
               dst.b = h.newoverflow(t, dst.b)
               dst.i = 0
               // dst.k 指向溢出桶的第一个 key 的地址
               dst.k = add(unsafe.Pointer(dst.b), dataOffset) 
               // dst.e 指向溢出桶的第一个 elem 的地址
               dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
            }
            // 运用 & 运算优化，不必进行鸿沟查看
            // 记载 tophash
            dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
            // 将旧的 key/elem 仿制到 dst 指向的槽
            if t.indirectkey() { // bucket 的 key 保存的是指针
               // 修正实践存储 key 的内存
               *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
            } else {
               // 修正 bucket 中保存 key 的内存
               typedmemmove(t.key, dst.k, k) // copy elem
            }
            if t.indirectelem() { // bucket 的 elem 保存的是指针
               // 修正实践存储 elem 的内存
               *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
            } else {
               // 修正 bucket 中保存 elem 的内存
               typedmemmove(t.elem, dst.e, e)
            }
            // 方针桶的元素个数 +1
            // dst 指向下一个空的槽（slot/cell）
            dst.i++
            // 这些更新或许会将这些指针推到 key 或 elem 数组的结尾。
            // 这不要紧，由于咱们在桶的结尾有溢出桶指针，以避免指针指向桶的结尾。
            // 假如指向数组结尾，在下次搬迁的时分，会创立溢出桶。
            dst.k = add(dst.k, uintptr(t.keysize))
            dst.e = add(dst.e, uintptr(t.elemsize))
            // 上面有判别 dst.i == bucketCnt，所以这儿不会溢出
         }
      }
      // 取消链接溢出桶并铲除 key/elem 以协助 GC。（铲除旧桶的内存）
      if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
         b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
         // tophash 状况不能铲除。
         // 可是 key/elem 都能够铲除。
         ptr := add(b, dataOffset)
         n := uintptr(t.bucketsize) - dataOffset
         memclrHasPointers(ptr, n)
      }
   }
   // 刚刚搬迁的桶，便是次序搬迁的下一个桶，
   // 则需求更新 nevacuate 字段，标明现已搬迁了多少个桶
   if oldbucket == h.nevacuate {
      advanceEvacuationMark(h, t, newbit)
   }
}
  1. advanceEvacuationMark 的作用是更新 nevacuate 字段，标明现已搬迁了多少个桶。

咱们上面说了，哈希表扩容的时分，会有两条线，advanceEvacuationMark 便是处理次序搬迁的那条线，让 nevacuate 指向下一个未搬迁的桶。 为什么需求做这个处理呢？这是由于别的一条线的搬迁是随机的，拜访到哪个桶就搬迁哪个桶，这就导致了，次序搬迁的那条线，在将 nevacuate 指向下一个桶的时分，其实下一个桶是现已搬迁了的，咱们下次次序搬迁的时分必定不需求搬迁这个桶。 那么处理办法便是，持续向后查找，找到第一个未搬迁的桶。

// 记载搬迁进度（从次序搬迁的方位往后遍历，确保 nevacuate 指向下一个没有搬迁的桶）
// 参数：h 需求扩容的 map，t map 类型信息，newbit 是旧桶的数量
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
   // nevacuate 索引加 1
   h.nevacuate++
   // 往后找一个未搬迁的桶（最多遍历 1024 个桶）。
   stop := h.nevacuate + 1024
   if stop > newbit {
      stop = newbit
   }
   // 向后遍历，找到第一个未搬迁的桶。
   for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
      h.nevacuate++
   }
   // 这意味着一切旧桶都搬迁完了
   if h.nevacuate == newbit {
      // 扩容现已完结。开释旧的一般桶数组。
      h.oldbuckets = nil
      // 也能够丢弃旧的溢出桶。
      // 假如它们仍然被迭代器引证，那么迭代器将保存指向切片的指针。
      //（可是 h 不再需求保存指向切片的指针）
      if h.extra != nil {
         h.extra.oldoverflow = nil
      }
      // 移除等量扩容标志
      h.flags &^= sameSizeGrow
   }
}

这儿需求留意的是下面几行代码：

stop := h.nevacuate + 1024
if stop > newbit {
    stop = newbit
}

咱们在将 nevacuate 加上 1 之后，还会持续往后遍历 1024 个 bucket，假如 bucket 已搬迁，则将 nevacuate 加 1。

假如没有这个操作会怎样？那就意味着或许有许多的 bucket 都现已搬迁了，可是次序搬迁的方位（nevacuate）还没有更新， 这样或许会导致次序搬迁的方位每次都指向了已搬迁的 bucket。 终究导致，搬迁的时分，只搬迁了拜访到的 bucket，而没有搬迁次序搬迁方位上的那个 bucket。

也便是说，每次搬迁的时分只会搬迁 1 个 bucket，而不是 2 个，这样一来 growWork 需求调用的次数比本来更多，也便是说，需求写操作次数更多才干完结悉数 bucket 的搬迁。

这个函数做的工作能够标明成下图：

go map 设计与实现

在这个图中，nevacuate 一开端是 1，然后由于 3 这个 bucket 在这次 growWork 中现已搬迁了， nevacuate 假如要指向下一个未搬迁的 bucket 的话，就要越过之前现已搬迁的 2，以及本次 growWork 中现已搬迁的 3， 所以终究 nevacuate 指向了 4，也便是下一个未搬迁的 bucket。

等量扩容的作用

在上面咱们解说的时分，其完结已假定了扩容是增量扩容（2 倍扩容），但实践上还有一种扩容办法，便是等量扩容。 等量扩容的时分，扩容前后的 bucket 其实数量是相同的，那么为什么还要进行扩容呢？

这是由于，溢出桶太多了，数据十分零星地散布在了许多的溢出桶中，这样会导致 bucket 中许多槽都是空的， 这样一来，进行查找、修正、删去的时分，需求遍历许多的溢出桶，这样会导致性能下降。如下图：

go map 设计与实现

这个图中，咱们假定要查找的 key 地点的一般桶以及前两个溢出桶都是空的，又或许 key 不在前面三个桶中，那只要遍历到终究一个溢出桶的时分才干找到咱们要查找的 key。为了针对这种键值对数量没有到达扩容的阈值，可是溢出桶太多的状况，Go 言语提供了等量扩容的办法。

在等量扩容的时分，会将一切的溢出桶都搬迁到新的 bucket 中，这样一来，bucket 中的槽就会被填满，而溢出桶也或许不再需求。

终究，针对上图的状况，key = foo 会被搬迁到一般桶中，这样在查找的时分，只需求遍历一般桶就能够找到了。 当然，实践中的状况是，关于零星散布在多个溢出桶中的键值对，会被逐个往前挪，终究作用便是，桶中没有空的槽，除了终究一个 key 今后的槽。

咱们能够结合下图幻想一下：

当然下图仅仅描绘了一下部分 key，假如 key 散布。实践上 key 在触发等量扩容的状况下，是零星地散布在不同的 bucket 中的（包括溢出桶）。

go map 设计与实现

map 的迭代完结

go 的 map 迭代的时分，咱们会发现，回来成果的次序并不固定，这是由于 map 的迭代是无序的。 在 map 遍历的时分，每次都会从一个随机的 bucket 开端遍历，并且选了一个 bucket 之后， 还会从 bucket 中随机选择一个槽开端遍历，这样一来，每次遍历的成果都是不相同的。

map 迭代器数据结构

迭代器的功用：记载要遍历的 map，以及当时遍历到的 bucket 以及槽的索引，以便进行下一次遍历。

go 的 map 迭代器的数据结构如下：

// 哈希迭代结构。
type hiter struct {
   // 有必要排在第一位。 写入 nil 标明迭代完毕
   key unsafe.Pointer
   // 有必要在第二个方位（拜见 cmd/compile/internal/walk/range.go）。
   elem unsafe.Pointer
   t    *maptype       // map 的类型信息，包括 key、elem 的类型等信息
   h    *hmap          // 需求迭代的 hmap
   // hash_iter 初始化时的 bucket 指针
   buckets unsafe.Pointer
   // 当时正在遍历的 bucket
   bptr *bmap
   // 坚持 hmap.buckets 的溢出桶存活
   overflow *[]*bmap
   // 坚持 hmap.oldbuckets 的溢出桶存活
   oldoverflow *[]*bmap
   // bucket 迭代开端方位（随机选择的 bucket）
   startBucket uintptr
   // 在迭代期间开端的桶内偏移量（应该足够大以包容 bucketCnt-1）
   offset uint8
   // 现已从桶数组的结尾环绕到开端
   wrapped     bool
   B           uint8   // 便是当时遍历的 hmap 的那个 B
   i           uint8   // 当时遍历的 bucket 内 key 的索引
   bucket      uintptr // 当时遍历的 bucket
   checkBucket uintptr
}

几点留意的：

  1. 悉数键值对遍历完的时分，key 会被置为 nil，这样一来，咱们就能够经过 key 是否为 nil 来判别是否遍历完了。（当然这个不必开发者来判别，for...range 底层现已帮咱们做了这个判别）。
  2. hiter 结构体保存了当时正在迭代的 bucket（bptr）、bucket 中的 key 的索引（i）等信息，这样一来，咱们就能够经过这些信息来确认下一个 key 的方位。

迭代器的初始化完结

go 的 map 初始化是经过 runtime.mapiterinit 来完结的，这个函数的完结如下：

// mapiterinit 初始化用于 range 遍历 map 的 hiter 结构。（初始化 hiter）
// 'it' 指向的 hiter 结构由编译器次序传递在仓库上分配，或由 reflect_mapiterinit 在堆上分配。
// 两者都需求将 hiter 置零，由于结构包括指针。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
   // hiter 记载 map 的类型信息
   it.t = t
   // 假如 map 是空的直接回来
   if h == nil || h.count == 0 {
      return
   }
   // 个人猜测：内存对齐判别，这个由编译器决议的
   if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
      throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
   }
   // it 相关上 map
   it.h = h
   // 获取桶状况的快照
   it.B = h.B
   // 当时的 buckets
   it.buckets = h.buckets
   // bucket 里边没有包括指针
   if t.bucket.ptrdata == 0 {
      // 分配当时切片并记住指向当时切片和旧切片的指针。
      // 这将坚持一切相关的溢出桶处于活动状况，即便在迭代时表增加和/或溢出桶增加到表中。
      h.createOverflow()
      it.overflow = h.extra.overflow
      it.oldoverflow = h.extra.oldoverflow
   }
   // 决议从哪里开端遍历。
   // 战略：随机选定一个 bucket，然后从该 bucket 开端遍历。
   // 生成随机数
   var r uintptr
   if h.B > 31-bucketCntBits {
      r = uintptr(fastrand64())
   } else {
      r = uintptr(fastrand())
   }
   // r => 扫描的进口（随机选的 bucket）
   it.startBucket = r & bucketMask(h.B)
   // 随机定位的 bucket 中的槽。
   it.offset = uint8(r >> h.B & (bucketCnt - 1))
   // 记载当时扫描的 bucket
   it.bucket = it.startBucket
   // 记住咱们有一个迭代器。
   // 能够与另一个 mapiteinit() 一起运转。
   if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
      atomic.Or8(&h.flags, iterator|oldIterator)
   }
   // 开端遍历
   mapiternext(it)
}

这个函数主要功用是初始化迭代器，咱们最需求关怀的是，这个函数里边会生成一个随机数，然后经过这个随机数来决议从哪一个 bucket 开端遍历， 以及从 bucket 中的哪一个槽开端遍历（也是随机的）。

map 遍历图解

那为什么从随机定位的 bucket 以及随机定位的 key 就能够完结遍历呢？其实很简略，假如看过我之前写的 《go chan 规划与完结》的话， 就会知道 chan 的完结中是经过数组来完结环形行列的。而咱们能够凭借环形行列的特性来了解 map 的遍历。遍历到终究一个 bucket 之后， 下一个 bucket 便是第一个 bucket，这样就完结了环形遍历。相同的，遍历到终究一个 key 之后，下一个 key 便是第一个 key，这样也完结了环形遍历。

咱们需求做的便是，在遍历开端的时分，记载第一个 bucket，然后每次遍历 bucket 的时分， 比较当时的 bucket 是否是第一个 bucket，是的话，意味着遍历完毕了。 相同的，关于 bucket 内 key 的遍历也是。

不过，在实践完结中，key 有点不相同，key 的遍历是经过将 i 从 0 遍历到 7，关于每一个 i，加上 it.offset，然后对 8 取模， 这样就能够完结环形遍历了，代码如下：

for ; i < bucketCnt; i++ {
   // 桶内第 i 个元素
   offi := (i + it.offset) & (bucketCnt - 1)
}

具体遍历进程如下图：

go map 设计与实现

发生在扩容期间的遍历

go 的 map 规划中，是不答应在迭代的时分进行刺进、修正、删去的，但仅仅在获取下一个键值对的时分不答应， 在迭代器获取了键值对之后，就算还没有悉数遍历完 map 的一切元素，仍是能够答应做刺进、修正、删去操作的。 这样一来，有或许会呈现一些古怪的现象，比方刺进的 key 遍历不出来，或许遍历出来的 key 有重复等等。这是需求开发者留意的当地。

别的，迭代能够发生在扩容的进程中，可是扩容其实对迭代其实是没有什么影响的。由于迭代的时分会做一些判别尽量确保一切 key 都能被遍历到。 但不能确保咱们对 map 做了写操作后仍然能够悉数 key 都遍历。

在遍历的进程中，假如 map 发生了扩容，那么遍历的进程就会变得杂乱一些。由于在扩容的进程中，map 会新建一个 bucket， 然后将本来的 bucket 中的 key 重新散列到新的 bucket 中。所以在遍历的进程中，假如发现当时的 bucket 现已发生了扩容， 需求做一些判别，比方：

  1. 假如发现 bucket 还没有搬迁，则从 oldbuckets 中遍历。
  2. 假如发现 bucket 在搬迁之后索引跟本来的不相同，则越过。

具体能够参阅下图：

go map 设计与实现

这儿假定的条件是：旧桶个数为 4，增量扩容后，新桶个数为 8。hiter 当时迭代的是新桶。

阐明：

  1. h.oldbuckets 指向了还没搬迁完的桶，h.buckets 是当时的桶。
  2. hiter 迭代器要迭代的是新的桶。迭代器初始化的时分正在进行 2 倍扩容。
  3. checkBucket 是下一个要遍历的桶（索引为 1），图中的状况是，这个桶还没有被搬迁。所以需求从 h.oldbuckets 中读取。
  4. checkBucket 中的 key 有或许会搬迁到 h.buckets 中的 1 或许 5 方位。（具体能够看上面桶搬迁的完结那一节）
  5. 假如 key 是要被搬迁到 5 中的话，那么遍历的时分会越过，由于后边会遍历到 5 中的 key。
  6. 关于第 5 点，在遍历 5 这个 bucket 的时分，由于咱们是运用当时遍历的 bucket 的下标结合旧桶的长度核算在旧桶中的下标的，所以仍是能够取得到旧桶，然后遍历的时分取出那些应该搬迁到 5 这个 bucket 的 key，关于那些应该要搬迁到 1 的 key 则越过。
  7. 下一个要遍历的桶的索引为 2。

关于第 6 点桶索引核算的特别阐明，假如是增量扩容，核算 bucket 的下标办法如下：

// bucket 是当时要遍历的 bucket 的下标
// it.h.oldbucketmask() 是旧桶的 B 的掩码
oldbucket := bucket & it.h.oldbucketmask()

当然假如这个桶现已搬迁，那么仍是会重新桶遍历（也便是 bucket & it.h.oldbucketmask() 里的 bucket 自身）。

键值对遍历源码分析

map 中完结遍历的函数是 mapiternext，这个函数做的工作，也便是上面两个图描绘的遍历进程，代码如下：

// 参数：迭代器实例
func mapiternext(it *hiter) {
   // 获取底层的 hmap 实例
   h := it.h
   // 正在刺进、修正、删去 key 但时分，不能获取下一个 key，
   // 留意：这不能确保刺进、修正、删去之后，进行迭代。
   if h.flags&hashWriting != 0 {
      fatal("concurrent map iteration and map write")
   }
   t := it.t           // *maptype
   bucket := it.bucket // 当时遍历到的 bucket 下标（int 类型）
   b := it.bptr        // 当时 bucket 的指针（实践的 bucket，bmap 指针类型）
   i := it.i           // 迭代器当时遍历到的方位（bucket 内 key 的方位）
   checkBucket := it.checkBucket // 这个用来判别是否是增量扩容的
next:
   // 留意：下面的 if 的功用是，获取下一个桶。
   // 假如 b 是 nil，有以下两种状况：
   // a. 第一次遍历，还没有遍历到任何 bucket。
   // b. 遍历完终究一个 bucket 了。
   if b == nil {
      // 现已迭代完了，直接退出函数
      if bucket == it.startBucket && it.wrapped {
         // for...range 查看到 key 是 nil 会间断迭代
         it.key = nil
         it.elem = nil
         return
      }
      // 假如正在扩容
      if h.growing() && it.B == h.B {
         // 迭代器是在扩容进程中发动的，扩容没有完结。
         // 假如咱们正在查看的存储桶没有搬迁，
         // 那么咱们需求遍历旧存储桶，一起只回来将搬迁到此存储桶的数据。
         // 那些需求搬迁到另一个下标的桶则越过。
         oldbucket := bucket & it.h.oldbucketmask()
         // 获取旧桶
         b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
         if !evacuated(b) { // 旧桶还没有搬迁
            checkBucket = bucket
         } else { // 现已搬迁了，获取新桶
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
            checkBucket = noCheck
         }
      } else {
         // 并没有在扩容，获取新的桶
         b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
         checkBucket = noCheck
      }
      // bucket 指向了下一个要迭代的桶的下标
      bucket++
      // 判别当时遍历的桶是否到终究一个桶了
      if bucket == bucketShift(it.B) {
         bucket = 0
         it.wrapped = true // 现已从第一个随机定位的 bucket 遍历到终究一个 bucket 了，下一个应该是第一个 bucket 了
      }
      // 开端遍历新的 bucket 的时分，重置 i
      i = 0
   }
   // 开端遍历桶内的键值对
   for ; i < bucketCnt; i++ {
      // 核算桶内键值对的下标（从随机的 it.offset 下标开端遍历）
      offi := (i + it.offset) & (bucketCnt - 1)
      // 假如槽是空的，或许 key 现已搬迁，则越过。
      if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
         continue
      }
      // 桶内第 i 个元素的 key 的指针
      // 获取 key 或 elem 的解析前面的小节有具体的解说了，不再赘述。
      k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
      if t.indirectkey() {
         k = *((*unsafe.Pointer)(k))
      }
      // 桶内第 i 个元素的 elem 的指针
      e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
      // 增量扩容的 key 判别
      // 需求判别搬迁之后的 key 落入的是 h.buckets 的前半部分仍是后半部分（x 仍是 y）
      // 具体看上面的搬迁完结。
      if checkBucket != noCheck && !h.sameSizeGrow() {
         if t.reflexivekey() || t.key.equal(k, k) {
            // key 是可比较的
            // 假如这个 key 将会被搬迁到 h.buckets 的后半部分，越过它
            hash := t.hasher(k, uintptr(h.hash0))
            if hash&bucketMask(it.B) != checkBucket {
               continue
            }
         } else {
            // 关于不行比较的 key，
            // 是由 tophash 的最低位来决议搬迁到前半部分仍是后半部分的。
            // 取 checkBucket 的最高位来比较，由于 checkBucket 的最高位决议了
            // 当时遍历的 bucket 是上半部分仍是后半部分的 bucket。
            if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
               // 假如当时的 key 没有落入当时遍历的 bucket，则越过它
               continue
            }
         }
      }
      if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
         !(t.reflexivekey() || t.key.equal(k, k)) {
         // 上面的判别：
         // 1、标明 key 还没有搬迁。
         // 2、或许，key 是不行比较的。
         // 则直接回来
         it.key = k
         if t.indirectelem() {
            e = *((*unsafe.Pointer)(e))
         }
         it.elem = e
      } else {
         // 自迭代器发动以来，哈希表已扩容。
         // key 现已被搬迁到其他当地。
         // 查看当时哈希表中的数据。
         // 此代码处理已删去、更新或删去并重新刺进 key 的状况。
         // 留意：咱们需求重新符号 key，由于它或许已更新为 equal() 但不是相同的 key（例如 +0.0 vs -0.0）。
         // 获取当时遍历到的 key/elem。
         rk, re := mapaccessK(t, h, k)
         if rk == nil {
            // key 现已被删去了，持续遍历下一个 key
            continue
         }
         // 外部是经过 it 的 key/elem 来获取当时遍历到的键值对的
         it.key = rk
         it.elem = re
      }
      // 记载当时迭代的 bucket
      it.bucket = bucket
      // 遍历到下一个 bucket 了，更新 bptr
      if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
         it.bptr = b
      }
      // 迭代器的 i 指向 bucket 内的下一个 key
      it.i = i + 1
      // 记载是否需求查看 key 的符号
      it.checkBucket = checkBucket
      // 找到了键值对（保存在 it.key/it.elem 中了），回来。
      // mapiternext 外部能够经过 hiter 的 key/elem 属性来获取当时遍历到的 key/val。
      // 遍历下一个元素的时分，再次调用 mapiternext 函数。
      //（无所谓，hiter 会记住迭代到哪里的）
      // 也即：每遍历一个元素，调用一次 mapiternext 函数。
      return
   }
   // 当时的 bucket 遍历完了，那么持续从溢出桶中查找下一个元素。
   // b 指向溢出桶，迭代溢出桶
   b = b.overflow(t)
   // 遍历下一个桶了，key 从 0 开端遍历
   i = 0
   // 遍历当时 bucket 的溢出桶
   goto next
}

小结

  • 哈希表相比数组，能够很快速地查找，所以常见的编程言语都会有对应的完结。
  • 哈希抵触有两种处理办法：敞开地址法和链表法，go 里的 map 运用的是链表法。
  • 哈希表初始化分配的是比较小的内存，只能寄存少数键值对，可是随着咱们刺进的数据越来越多，哈希表会进行扩容，避免哈希表的读写性能下降。
  • go 的 map 扩容有两种办法：键值对太多的时分会进行 2 倍扩容，溢出桶太多会进行等量扩容。
  • map 中运用 buckets 来存储桶，一个桶里边能够存储 8 个键值对，一个桶满了的时分，会创立溢出桶来保存多出来的 key。
  • map 中桶的结构体是 bmap，它里边的会将一切 key 接连存储，一切的 value 也会接连存储。
  • map 定位 key 的时分，会运用哈希值与 B 的掩码做 & 运算（咱们能够将其了解为一种模运算的别的一种完结），从而得到 bucket 的下标，然后遍历这个 bucket 中的每一个槽。先比较 tophash，假如 tophash 持平再比较 key，假如 tophash 和 key 都持平，则标明找到了咱们要找的 key。假如这两者有一个不等，持续比较下一个 key。
  • 假如一个 bucket 中的一切 key 被遍历完了也没有找到，那么持续从溢出桶中查找。
  • map 读取数据是经过 mapaccess1、mapaccess2、mapaccessK 完结的，关于整型键值的 map 有优化的 mapaccess 完结（关于 bmap 里键值的拜访愈加高效）。
  • map 写入和修正数据都是经过 mapassign 函数完结的，这个函数在找不到 key 的时分会进行刺进操作。
  • map 删去数据是经过 mapdelete 函数完结的。删去的时分会需求将 bucket 结尾的一切空的槽的符号更新为 emptyRest。
  • map 扩容的条件有两个：超越负载因子、溢出桶太多。只要在增量扩容的时分，key 所对应的 bucket 的下标才有或许发生变化。
  • map 扩容的时分，会搬迁当时正在写入、删去的 bucket，一起也会从第一个 bucket 开端搬迁，一次写操作会搬迁两个 bucket。这样能够确保在一定的写操作今后，一切 bucket 都能搬迁完结。
  • 等量扩容的时分，key 在新桶中的 bucket 下标不变，可是 key 在桶内的散布会愈加地紧凑，从而会进步查找功率。
  • map 的迭代是经过 hiter 结构体来完结的，迭代的进程中 hiter 会记载当时的 bucket、key，一般桶迭代完后，迭代溢出桶。map 的迭代是经过 mapiternext 函数完结的，每次获取键值对都是经过这个 mapiternext 函数。
  • map 迭代假如发生在增量扩容的时分，关于未搬迁的 bucket，会判别 key 的 bucket 是否会发生变化，假如 key 对应的 bucket 现已改动，则迭代的时分会越过。