Golang-哈希表

Golang

字数统计: 2k阅读时长: 7 min

 2022/11/22 

map实现原理

Go语言采用哈希查找表，并且使用链表解决哈希冲突

内存模型：

type hmap struct{
   count        int     //K,V数目. 调用len()返回此值
   flags        uint8   //标志位，是否已有其他协程在执行写操作 
   B            unit8   //桶的数量的对数  2^B
   noverflow    uint16  //使用的溢出桶近似数
   hash0        uint32    
   buckets      unsafe.Pointer  //桶的指针
   oldbuckets   unsafe.Pointer  //旧桶, 等量扩容时 buckets长度和oldbuckets相等，双倍扩容 ，buckets长度会是oldbuckets两倍
   nevacuate    uintptr     //扩容阶段下一个要迁移的旧桶编号 next vacuate
   extra        *mapextra   //溢出桶相关信息
}

mapextra {
    overflow    *[]*bmap  
    oldoverflow *[]*bmap  
  
	// nextOverflow holds a pointer to a free overflow bucket.  
	nextOverflow *bmap 
}

buckets是一个指针，指向一个结构体：

1
2
3

type bmap struct{
   tophash [bucketCnt]uint8 
}

在运行期间，bmap结构体其实不止包含 tophash 字段，因为哈希表中可能存储不同类型的键值对，而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。
bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段，
不过我们能根据编译期间的 cmd/compile/internal/gc.bmap 函数重建它的结构：

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

bmap: 我们常说的桶，最多装8个key，根据key计算出来的hash值的高8位来决定落入桶的哪个位置（一个桶最多有8个位置）

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。
但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来。

slice 和 map 分别作为函数参数时有什么区别？

当 map 和 slice 作为函数参数时，在函数参数内部对 map 的操作会影响 map 自身；而对 slice 却不会

主要原因：一个是指针（*hmap），一个是结构体（slice）。
Go 语言中的函数传参都是值传递，在函数内部，参数会被 copy 到本地。
*hmap指针 copy 完之后，仍然指向同一个 map，因此函数内部对 map 的操作会影响实参。
而 slice 被 copy 后，会成为一个新的 slice，对它进行的操作不会影响到实参。

哈希函数

map 的一个关键点在于，哈希函数的选择。
在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。
这是在函数 alginit() 中完成，位于路径：src/runtime/alg.go 下。
选择 hash 函数主要考察的是两点：性能、碰撞概率。

key的定位

桶的数量m = 2^B
取模：hash%m, 但是开销太大，代码实现上用的位操作代替, 与运算 hash&(m-1)

hash冲突的解决办法：
“拉链法”: 在冲突的桶后面练一个新桶
开放地址法：遍历后面的桶，key相等或者为nil

map遍历过程

扩容过程不是一个原子操作，每次最多只搬运两个bucket，如果触发了扩容操作，那么很长一段时间里，map的状态都除以一个中间态：有些bucket已经搬迁到新家，而有些bucket还待在老地方
难点在于：遍历如果发生在扩容过程中，会涉及遍历新老bucket的过程

查看汇编命令：

go tool compile -S main.go

// ......
0x0124 00292 (test16.go:9)      CALL    runtime.mapiterinit(SB)

// ......
0x01fb 00507 (test16.go:9)      CALL    runtime.mapiternext(SB)
0x0200 00512 (test16.go:9)      MOVQ    ""..autotmp_4+160(SP), AX
0x0208 00520 (test16.go:9)      TESTQ   AX, AX
0x020b 00523 (test16.go:9)      JNE     302

先是调用 mapiterinit 函数初始化迭代器(器hiter)，然后循环调用 mapiternext 函数进行 map 迭代。

// 生成随机数 r
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
	r += uintptr(fastrand()) << 31
}

// 从哪个 bucket 开始遍历
it.startBucket = r & (uintptr(1)<<h.B - 1)
// 从 bucket 的哪个 cell 开始遍历
it.offset = uint8(r >> h.B & (bucketCnt - 1))

赋值过程

mapassign函数
检查标志位 flags

对 key 计算 hash 值，根据 hash 值按照之前的流程，找到要赋值的位置（可能是插入新 key，也可能是更新老 key），对相应位置进行赋值。
源码大体和之前讲的类似，核心还是一个双层循环，外层遍历 bucket 和它的 overflow bucket，内层遍历整个 bucket 的各个 cell

准备两个指针，一个（inserti）指向 key 的 hash 值在 tophash 数组所处的位置，另一个(insertk)指向 cell 的位置（也就是 key 最终放置的地址），当然，对应 value 的位置就很容易定位出来了。
这三者实际上都是关联的，在 tophash 数组中的索引位置决定了 key 在整个 bucket 中的位置（共 8 个 key），而 value 的位置需要“跨过” 8 个 key 的长度。
在循环的过程中，inserti 和 insertk 分别指向第一个找到的空闲的 cell。
如果之后在 map 没有找到 key 的存在，也就是说原来 map 中没有此 key，这意味着插入新 key。那最终 key 的安置地址就是第一次发现的“空位”（tophash 是 empty）。
果这个 bucket 的 8 个 key 都已经放置满了，那在跳出循环后，发现 inserti 和 insertk 都是空，这时候需要在 bucket 后面挂上 overflow bucket。

在正式安置 key 之前，还要检查 map 的状态，看它是否需要进行扩容。如果满足扩容的条件，就主动触发一次扩容操作。

这之后，整个之前的查找定位 key 的过程，还得再重新走一次。因为扩容之后，key 的分布都发生了变化。
最后，会更新 map 相关的值，如果是插入新 key，map 的元素数量字段 count 值会加 1；在函数之初设置的 hashWriting 写标志出会清零。

ps：mapassign 函数返回的指针就是指向的 key 所对应的 value 值位置，有了地址，就很好操作赋值了

删除过程

先判断flags标志位，是否有其他协程在进行写操作。如果有直接返回panic
计算key的hash，找到落入的bucket。检查此map如果处于扩容过程中，执行一次搬迁操作
找到key的具体位置，在bucket中挨个cell寻找，找到对应位置后，对key和value进行清零操作
最后将hamp接口体的count数量-1，将对应位置的tophash置为empty

扩容过程

什么时候需要扩容：
1.装载因子 > 6.5 . locadFactor := count / (2^B)
2.使用的溢出桶过多： B<15 ,count > 2^B ; B>15 ,count >2^15

hashGrow() 分配新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上
真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中
olldbuckets 为 nil扩容完成

Key为什么是无序的

map 在扩容后，会发生 key 的搬迁，原来落在同一个 bucket 中的 key，搬迁后，有些 key 就要远走高飞了（bucket 序号加上了 2^B）。
而遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。

我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

ps: “迭代 map 的结果是无序的”这个特性是从 go 1.0 开始加入的

原文作者：June

原文链接：https://jatshw.com/2022/11/22/Golang-%E5%93%88%E5%B8%8C%E8%A1%A8/

发表日期：November 22nd 2022, 12:00:00 am

更新日期：March 22nd 2023, 4:58:12 pm