朱晓峰

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

0%

golang map 实现原理初探

最近一直在学习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

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

    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搬到新的表中之后,并不会将旧的bucketoldbucket中删除,而是加上一个已删除的标记。

只有当所有的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会清理老的溢出桶并释放内存。

参考文章