Go map的底层原理

  • map的实现原理
  • map的底层结构
  • map的扩容机制

map的实现原理

数组+链表、拉链法

map的底层结构

hmap

hmap 哈希表

hmap是Go map的底层实现，每个hmap内都含有多个bmap（buckets桶、oldbuckets旧桶、overflow溢出桶），既每个哈希表都由多个桶组成。

type hmap struct {
    count     int    //元素的个数
    flags     uint8  //状态标志
    B         uint8  //可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子
    noverflow uint16 //溢出的个数
    hash0     uint32 //哈希种子

    buckets    unsafe.Pointer //指向一个桶数组
    oldbuckets unsafe.Pointer //指向一个旧桶数组，用于扩容
    nevacuate  uintptr        //搬迁进度，小于nevacuate的已经搬迁
    overflow *[2]*[]*bmap     //指向溢出桶的指针
}

  • buckets
    buckets是一个指针，指向一个bmap数组，存储多个桶。

  • oldbuckets
    oldbuckets是一个指针，指向一个bmap数组，存储多个旧桶，用于扩容。

  • overflow
    overflow是一个指针，指向一个元素个数为2的数组，数组的类型是一个指针，指向一个slice，slice的元素是桶(bmap)的地址，这些桶都是溢出桶。为什么有两个？因为Go map在哈希冲突过多时，会发生扩容操作。[0]表示当前使用的溢出桶集合，[1]是在发生扩容时，保存了旧的溢出桶集合。overflow存在的意义在于防止溢出桶被gc。

bmap 哈希桶

bmap是一个隶属于hmap的结构体，一个桶（bmap）可以存储8个键值对。如果有第9个键值对被分配到该桶，那就需要再创建一个桶，通过overflow指针将两个桶连接起来。在hmap中，多个bmap桶通过overflow指针相连，组成一个链表。

type bmap struct {
    //元素hash值的高8位代表它在桶中的位置，如果tophash[0] < minTopHash，表示这个桶的搬迁状态
    tophash [bucketCnt]uint8
    //接下来是8个key、8个value，但是我们不能直接看到；为了优化对齐，go采用了key放在一起，value放在一起的存储方式，
    keys     [8]keytype   //key单独存储
	values   [8]valuetype //value单独存储
	pad      uintptr
	overflow uintptr	  //指向溢出桶的指针
}

map的扩容机制

增量扩容

Go采用的是增量扩容方案，当map开始扩容后，每一次map操作都会触发一部分扩容搬迁工作（每进行一次赋值，会做至少一次搬迁工作）。由hmap中的nevacuate成员记录当前的搬迁进度。

注：在map进行扩容迁移的期间，不会触发第二次扩容。只有在前一个扩容迁移工作完成后，map才能进行下一次扩容操作。

扩容触发

以下两种情况会触发map扩容

  • （1）存储的键值对数量过多（负载因子已达到当前界限）。
  • （2）由overflow指针所连接的溢出桶数量过多。

Go的负载因子界限：6.5
负载因子 = 哈希表中元素数量 / 桶的数量

扩容情况一：存储的键值对数量过多

这种情况下map会进行翻倍扩容。

Go创建一个新的buckets数组，这个buckets数组的容量是旧buckets数组的两倍，并将旧数组的数据逐步迁移至新数组。

旧的buckets数组不会被直接删除，而是会把原来对旧数组的引用去掉，让GC来清除内存。

扩容情况二：溢出桶数量过多

如果出现了这种情况，可能是因为哈希表里有过多的空键值对，很多桶的内部出现了空洞（装不满）。这个时候就需要通过map扩容做内存整理。目的就是为了清除bmap桶中空闲的键值对。

这种情况下map扩容步骤与情况一基本相同，只不过扩容后map容量还是原来的大小。Go会创建一个与原buckets数组容量相同的buckets数组，并将旧数组的数据逐步迁移至这个新数组。再去除旧数组的引用，让GC来清除内存。