【Go进阶—数据结构】map

哈希表是除了数组之外,最常见的数据结构。Go 语言中的 map 底层就是哈希表,可以很方便地提供键值对的映射。

特性

未初始化的 map 的值为 nil,向值为 nil 的 map 添加元素会触发 panic,这是新手容易犯的错误之一。

map 操作不是原子的,多个协程同时操作 map 时有可能产生读写冲突,此时会触发 panic 导致程序退出。如果需要并发读写,可以使用锁来保护 map,也可以使用标准库 sync 包中的 sync.Map。

实现原理

数据结构

map 的底层数据结构由 runtime/map.go/hmap 定义:

type hmap struct {
    count     int             // 元素个数,调用 len(map) 时,直接返回此值
    flags     uint8
    B         uint8           // buckets 数组长度的对数
    noverflow uint16          // overflow 的 bucket 近似数
    hash0     uint32          // 哈希种子,为哈希函数的结果引入随机性,在调用哈希函数时作为参数传入
    
    buckets    unsafe.Pointer // 指向 buckets 数组,大小为 2^B,元素个数为0时为 nil
    oldbuckets unsafe.Pointer // 在扩容时用于保存旧 buckets 数组,大小为 buckets 的一半
    nevacuate  uintptr        // 指示扩容进度,小于此地址的 buckets 都已迁移完成
    extra *mapextra           // 附加项
}

buckets 数组中保存了 bucket 的指针,bucket 很多时候被翻译为桶,它是 map 键值对的真正载体。它的数据结构定义如下:

type bmap struct {
    tophash [bucketCnt]uint8    // 存储键的 hash 值的高 8 位
}

在运行期间,bmap 结构体其实不止包含 tophash 字段,因为哈希表中可能存储不同类型的键值对,而且 Go 语言(1.17之前)也不支持泛型,所以键值对占据的内存空间大小只能在编译时进行推导。bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的,所以它的定义中就不包含这些字段。在运行时,bmap 摇身一变,成了下面的样子:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

整体的 map 结构图大致如下所示:

【Go进阶—数据结构】map_第1张图片

bmap 的内部组成类似于下图:

【Go进阶—数据结构】map_第2张图片

HOB Hash 指的就是 top hash。key 和 value 是各自放在一起的,并不是 key/value/key/value/... 这样的形式。这样的好处是在某些情况下可以省略掉 padding 字段,节省内存空间。

每个 bucket 设计成最多只能放 8 个 key-value 对,如果有第 9 个 key-value 落入当前的 bucket,那就需要再构建一个 bucket,通过 overflow 指针连接起来。

相关操作

查找

key 经过哈希计算后得到哈希值,共 64 个 bit 位,计算它到底要落在哪个桶时,只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗?B 等于桶的数量,也就是 buckets 数组长度的对数。

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

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

用最后的 5 个 bit 位,也就是 00110,定位到 6 号桶。这个操作实际上就是取余操作,但是取余开销太大,所以代码实现上用位操作代替。再用哈希值的高 8 位,找到此 key 在 bucket 中的位置。如下图所示:

【Go进阶—数据结构】map_第3张图片

因为可能存在哈希冲突,所以在定位到 key 在 bucket 中的位置后,还需要获取对应的 key 值与待查询的 key 进行比较,不相等的话则继续上面的定位过程。如果在当前的 bucket 中没找到,并且 overflow 不为空,还要继续去 overflow bucket 中寻找,直到找到或是所有的 key 槽位都找遍了。如果未找到,也不会返回 nil,而是返回相应类型的零值。

注:如果当前处于搬迁过程(扩容),则优先从 oldbuckets 中查找。

赋值

赋值操作最终调用的是 mapassign 函数,它的初始流程和上面介绍的查找类似,也是通过 key 找到对应的 bucket 中的位置。准备两个指针,一个(inserti)指向 key 的 hash 值在 tophash 数组所处的位置,另一个 (insertk) 指向 cell 的位置(也就是 key 最终放置的地址)。在循环的过程中,inserti 和 insertk 分别指向第一个找到的空闲的 cell,如果最终没有找到 key 的话,就在此位置插入。如果当前桶已经满了,会调用 newoverflow 创建新桶或者使用 hmap 预先在 noverflow 中创建好的桶来保存数据,新创建的桶不仅会被追加到已有桶的末尾,还会增加 hmap 的 noverflow 计数器。

如果当前 key 在 map 中存在,那么就会直接返回目标区域的内存地址;如果不存在,则会为新键值对规划存储的内存地址,通过 typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址。map 并不会在 mapassign 这个运行时函数中将值拷贝到桶中,该函数只会返回内存地址,真正的赋值操作是在编译期间插入的。

扩容

前面在介绍 map 的写入过程时其实省略了扩容操作,随着 map 中元素的逐渐增加,性能会逐渐恶化,所以需要更多的桶和更大的内存保证 map 的性能。在向 map 插入新 key 的时候,会进行条件检测,符合的话就会触发扩容:

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again
}

func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 {
        B = 15
    }
    return noverflow >= uint16(1)<<(B&15)
}

由源码可以看出,触发扩容的条件为下面二者之一:

  1. 装载因子超过阈值,源码里定义的阈值是 6.5;
  2. overflow 的 bucket 数量过多:当 B 小于 15,也即 bucket 总数小于 2^15 时,overflow 的 bucket 数量超过 2^B;当 B >= 15,也即 bucket 总数大于等于 2^15时,overflow 的 bucket 数量超过 2^15。

对于条件一,说明 bucket 数量太少,此时需要扩充 bucket 的数量,称之为增量扩容;对于条件二,说明 bucket 里面键值对太稀疏,此时并不需要扩充 bucket 的数量,称之为等量扩容。无论是那种情况,都需要开辟一个新的 bucket 数组,将旧的 bucket 数组中的键值对移动到新的中来,只不过增量扩容时 bucket 的数量变为了之前的 2 倍。我们来看下扩容的入口 hashGrow 函数的核心代码:

func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    ...
}

我们可以看到,hashGrow 函数只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上,并没有真正地迁移数据。这是因为如果有大量的键值对需要迁移,会非常影响性能。因此 map 的扩容采取了一种“渐进式”的方式,原有的 key 并不会一次性迁移完毕,每次最多只会迁移 2 个 bucket。在插入或修改、删除 key 的时候,都会先检查 oldbuckets 是否迁移完毕,具体来说就是检查 oldbuckets 是否为 nil。如果为假则执行迁移,也即调用 growWork 函数。growWork 函数的代码如下:

func growWork(t *maptype, h *hmap, bucket uintptr) {
    evacuate(t, h, bucket&h.oldbucketmask())

    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

evacuate 函数就是执行迁移的函数,它会对传入桶中的元素进行再分配,大致逻辑如下:该函数会创建用于保存分配上下文的 evacDst 结构体,等量扩容只会创建一个,增量扩容则会创建两个,每个 evacDst 分别指向一个新桶。等量扩容的话,每个 key 都迁移到和之前同一序号的桶中;增量扩容的话,会根据哈希值和新的掩码分流到两个桶中。最后会增加 map 的 nevacuate 计数器并在所有的旧桶都被分流后清空 map 的 oldbuckets 和 oldoverflow。

你可能感兴趣的