Go中MAP底层原理分析

MAP底层原理分析

参考

1. https://golang.design/go-questions/map/principal
2. map | Golang 中文学习文档

---

1. 先来看一下map结构体，（runtime.hmap结构体就是代表着 go 中的map，与切片一样map的内部实现也是结构体）

   type hmap struct {// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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     uint8B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0     uint32 // hash seedbuckets    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 growingnevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)clearSeq   uint64extra *mapextra // optional fields
   }
   

   内部实现图

简单说明一下各个字段含义

• count：表示 hamp 中的元素数量，结果等同于len(map)

• flags : hmap 的标志位，用于表示 hmap 处于什么状态，有以下几种可能

  const (iterator     = 1 // 迭代器正在使用桶oldIterator  = 2 // 迭代器正在使用旧桶hashWriting  = 4 // 一个协程正在写入hmapsameSizeGrow = 8 // 正在等量扩容
  )
  

• B：hmap 中的哈希桶的数量为1 << B

• noverflow，hmap 中溢出桶的大致数量。

• 哈希种子，在 hmap 被创建时指定，用于计算哈希值。

• buckets，存放哈希桶数组的指针。

• oldbuckets，存放 hmap 在扩容前哈希桶数组的指针。

• extra，存放着 hmap 中的溢出桶，溢出桶指的是就是当前桶已经满了，创建新的桶来存放元素，新创建的桶就是溢出桶。

  type mapextra struct {// 溢出桶的指针切片overflow    *[]*bmap// 扩容前旧的溢出桶的指针切片oldoverflow *[]*bmap// 指向下一个空闲的溢出桶的指针nextOverflow *bmap
  }
  

2. 一直说的桶是个什么东西 ？

   hamp 中的buckets也就是桶切片指针，在 go 中对应的结构为runtime.bmap，如下所示

   // A bucket for a Go map.
   type bmap struct {tophash [abi.OldMapBucketCount]uint8
   }
   // OldMapBucketCount是如下的这个变量
   // Maximum number of key/elem pairs a bucket can hold.
   OldMapBucketCountBits = 3 // log2 of number of elements in a bucket.
   OldMapBucketCount     = 1 << OldMapBucketCountBits // 默认为8
   

   表面上看，它只有一个字段tophash，不过实际上来说，bmap的字段不止这些，这是因为map可以存储各种类型的键值对，所以需要在编译时根据类型来推导占用的内存空间，在cmd/compile/internal/reflectdata/reflect.go中的MapBucketType函数的功能就是在编译时构造 bmap，它会进行一系列检查工作，比如 key 的类型是否comparable。

   // MapBucketType makes the map bucket type given the type of the map.
   func MapBucketType(t *types.Type) *types.Type
   

   bmap内部结构：HOB Hash 指的就是 top hash。

实际上bmap结构如下；不过这些字段对我们是不可见的，go 在实际操作中是通过移动 unsafe 指针来进行访问

// 实际运行时定义（简化为可理解的结构）
type bmap struct {// 哈希值高8位数组 (每个槽位1字节)tophash [abi.OldMapBucketCount]uint8  // bucketCnt = 8// 以下是隐式字段（编译器在编译时根据键值类型动态生成内存布局）keys    [abi.OldMapBucketCount]keyType   // 键数组（连续存储）elems   [abi.OldMapBucketCount]elemType  // 值数组（连续存储）注意：1.17+ 改名为 elems// 溢出桶指针（重要：在 keys/elems 之后存储）overflow *bmap
}
// 注意:有些文章还有pad字段 ，该字段是为了保持内存对齐，提高一些操作的效率的

tophash字段是什么 ？

首先，根据字面意思就是一个为uint8类型的长度为 8的数组 ，此时也就定义了 一个桶中可以存放8个键值对，桶中每个元素是uint8，代表每个键（key）对应的hash值得高八位， 用于定位该键（key）在本桶的位置。

另外，tophash还有一些特殊的值，通常是处于扩容的迁移状态下：

const (emptyRest      = 0 // 当前元素是空的，并且该元素后面也没有可用的键值了emptyOne       = 1 // 当前元素是空的，但是该元素后面有可用的键值。evacuatedX     = 2 // 扩容时出现，只能出现在oldbuckets中，表示当前元素被搬迁到了新哈希桶数组的上半区evacuatedY     = 3 // 扩容时出现只能出现在oldbuckets中，表示当前元素被搬迁到了新哈希桶数组的下半区evacuatedEmpty = 4 // 扩容时出现，元素本身就是空的，在搬迁时被标记minTopHash     = 5 // 对于一个正常的键值来说tophash的最小值
)

• minTopHash：当一个 cell（每个tophash元素抽象成每一个cell） 的 tophash 值小于 minTopHash 时，标志这个 cell 的迁移状态。因为这个状态值是放在 tophash 数组里，为了和正常的哈希值区分开，会给 key 计算出来的哈希值一个增量：minTopHash。这样就能区分正常的 top hash 值和表示状态的哈希值
• 其余变量是迁移过程中用到的 ，后续说明

3. key定位过程

   参考文章中说明的很好：

   ---

   key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。

   例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

    10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
   

   用最后的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。

   再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入。

上图中，假定 B = 5，所以 bucket 总数就是 2^5 = 32。首先计算出待查找 key 的哈希，使用低 5 位 00110，找到对应的 6 号 bucket，使用高 8 位 10010111，对应十进制 151，在 6 号 bucket 中寻找 tophash 值（HOB hash）为 151 的 key，找到了 2 号槽位，这样整个查找过程就结束了。

如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

---

key与value的定位方法

// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))// value 定位公式
e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))

b 是 bmap 的地址，这里 bmap 还是源码里定义的结构体，只包含一个 tophash 数组，经编译器扩充之后的结构体才包含 key，value，overflow 这些字段。dataOffset 是 key 相对于 bmap 起始地址的偏移， 也就是bmap中key地址开始的位置：

dataOffset = unsafe.Offsetof(struct {b bmapv int64}{}.v)

当定位到一个具体的 bucket 时，里层循环就是遍历这个 bucket 里所有的 cell，或者说所有的槽位，也就是 bucketCnt=8 个槽位。整个循环过程：

遍历过程中会判断每一个cell的状态 ，判断这个bucket是否搬迁完毕，源码中用到的函数

func evacuated(b *bmap) bool {h := b.tophash[0]return h > empty && h < minTopHash
}

只取了 tophash 数组的第一个值，判断它是否在 0-4 之间。对比上面的常量，当 top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 这三个值之一，说明此 bucket 中的 key 全部被搬迁到了新 bucket。