关于golang: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 结构图大抵如下所示：

bmap 的外部组成相似于下图：

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 中的地位。如下图所示：

因为可能存在哈希抵触，所以在定位到 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。