朱晓峰

一只生之无趣死之乏味的丧家之犬

0%

golang map 实现原理初探

Posted on Edited on In

最近一直在学习golang，本文是对于golang中map的实现原理的一次初探，我个人觉得原理比具体代码实现更有价值，所以主要探究原理，如有错误，敬请斧正。

本文基于go 1.14.2版本

是什么Map

本文所讨论的Map是一种key-value键值对的存储结构，其中key是不能重复的。

实现的关键是哈希表，hash表的输入一般都大于输出，所以要解决冲突。

冲突解决方法

  1. 开放定址法

    如果算出来的hash值所在的数组元素不为空，那就往这个数组后面继续找空的位置，找的方式又有几种常见方式：

    1. 线性探测法

      顺序往后找空的位置，到最后一位就从头开始，如果都没有，那就返回数组已满，插入失败。实际上再快满的时候就应该扩容了。

      数组长度为p，步长为1，索引位置的迭代式是 i = (i + 1) % p

    2. 线性补偿探测法

      找一个和数组长度p互质的q，然后根据上述的迭代式，步长为q，索引位置的迭代式为 i = (i + q) / p

      p与q互质就保证了可以探测到数组中的每一个元素

    3. 随机探测

      将步长又常数改为随机数，生成一个随机数序列R，

      i = ( i + Rj ) % p

    4. 二次探测再散列法

      冲突，就再做一次hash

  2. 拉链法

    当产生冲突时，在该位置延伸出一个链表用来存储value。相比于开放地址法，用链表的方法仅会在相同hash值的地方出现链表，而其他不冲突的地方，可以快速查找到，所以总体的平均查找长度比较短。缺点也显而易见，因为用链表，所以需要额外存储指针的空间，而且内存地址不一定连续。

    比如你有很多标有序号和不同颜色的珠子，面前有8个桶，每个桶里有一根绳子，你按照珠子的序号找到对应的桶，把珠子串到桶里的绳子上。珠子的序号和颜色（作为key），珠子本身作为value。当你要查找珠子的时候，根据序号找到桶，再沿着绳子一个一个找颜色匹配的珠子。

    如果哈希表本身长度不大，即桶的数量不多，但是延伸出来的链表很长的话，查找性能依旧是很差的，所以引入一个指标来衡量：负载因子（loadFactor）

    负载因子 = 填入散列表中的元素个数 / 桶的数量

    也就是该哈希表中链表的平均长度

    golang会在loadFactor > 6.5的时候对桶的数量进行扩容，以保证查找性能

Map的实现关键原理

hash函数选择

一般来说，k-v结构都需要将key进行hash，然后取模最终确定其在底层数据结构里的位置。

  • java是利用hashCode()和hash()来确定元素的位置的

  • golang分两种情况：如果cpu支持aes，则使用aes hash，否则使用memhash，而memhash是参考xxhash、cityhash实现的，性能非常好

    // runtime variable to check if the processor we’re running on

    // actually supports the instructions used by the AES-based

    // hash implementation.

    更多hash函数性能对比可以参考：More-Hash-Function-Tests

底层结构

hmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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  // 代表有2^B个桶 log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	// noverflow是溢出桶的数量，当B<16时，为精确值
	// 当B>=16时，为估计值
	hash0     uint32 // hash种子 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
}

不论是c++、java还是golang，hashmap的实现里桶的数量一般都是2的整数幂，2^B，因为这样可以避免取模运算：

设hash后的值为n，桶的数量m=2^B

则有 n mod m = n & (m - 1)

利用位运算代替昂贵的取模运算是常见的优化方法

bmap
1
2
3
4
5
6
7
8
9
10
11
12
// 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.
}

bmap就是上文一直说的桶，即bucket的实际结构

这里只显示定义了一个tophash，实际上里面还存了k/v和overflow，由于k/v字节长度不定，所以需要编译器来优化，不能在这边显示定义。

go在使用hash值的时候很有意思，会把hash的二进制值一分为二，低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key

扩容

bucket的链表越来越长，性能会退化，那么就要进行扩容，扩大bucket的数量。

当 元素个数/bucket 即loadFactor大于等于6.5时，就会进行扩容，把bucket数量扩成原本的两倍，当hash表扩容之后，需要将那些老数据迁移到新table上(源代码中称之为evacuate)， 数据搬迁不是一次性完成，而是逐步的完成（在assign（即赋值）和remove时进行搬移），这样就分摊了扩容的耗时。同时为了避免有个bucket一直访问不到导致扩容无法完成，还会进行一个顺序扩容，每次因为写操作搬迁对应bucket后，还会按顺序搬迁未搬迁的bucket，所以最差情况下n次写操作，就保证搬迁完大小为n的map。

扩容会建立一个大小是原来2倍的新的表，将旧的bucket搬到新的表中之后，并不会将旧的bucket从oldbucket中删除，而是加上一个已删除的标记。

只有当所有的bucket都从旧表移到新表之后，才会将oldbucket释放掉。如果扩容过程中，阈值又超了呢？如果正在扩容，那么不会再进行扩容。

1
2
3
4
5
6
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
	hashGrow(t, h)
	goto again // Growing the table invalidates everything, so try again
}

性能优化

将hash值一分为二，低位用于查找bucket，高位用于查找bucket中的key，分库分表也是这种这思想，尽可能快地缩小需要查找的数据量。

key-value在bmap中的实际存储顺序不是通常理解的k1v1k2v2k3v3……，而是k1k2……k8v1v2……v8，不用kv交替的顺序存储，而是k堆一块，v堆一块，这样可以更有效地利用内存对齐带来的性能提升。

如果key或者value的小于128字节，则会直接存储在bmap里，否则会存储指针

1
2
3
4
5
6
// Maximum key or elem size to keep inline (instead of mallocing per element).
// Must fit in a uint8.
// Fast versions cannot handle big elems - the cutoff size for
// fast versions in cmd/compile/internal/gc/walk.go must be at most this elem.
maxKeySize  = 128
maxElemSize = 128

java和go是用桶加链表的思想来实现hashmap的，但是java在链表达到一定长度时，会用红黑树来优化查询速度。

go的map出现冲突时，不会单独再申请一个value的结构，然后通过链表串起来，而是当bmap中的value数量大于8个，就申请一个新的bmap挂在前一个bmap的overflow里。这种可以显著减少对象的数量，减轻内存管理的压力，对gc友好。而且在创建map时，会预先分配一些overflow bucket。但问题就是，目前go还不会shrink空的bmap，所以即使用delete删除掉map中的kv，也不会被gc回收，导致内存泄漏。

所以需要针对于一个特殊的场景进行特殊扩容，当我们持续向map中插入数据并将它们全部删除时，如果map中的数据量没有超过阈值，就会不断积累溢出桶造成缓慢的内存泄漏。runtime: limit the number of map overflow buckets 引入了sameSizeGrow通过重用已有的哈希扩容机制，一旦map中出现了过多的溢出桶，它就会创建新桶保存数据，gc会清理老的溢出桶并释放内存。

参考文章