本文学习 Golang 的 Map 数据结构, 以及 map buckets 的数据组织结构.
hash 表是什么
从大学的课本里面, 我们学到: hash 表其实就是将 key 通过 hash 算法映射到数组的某个位置, 然后把对应的 val 存放起来.
如果出现了 hash 冲突(也就是说, 不同的 key 被映射到了相同的位置上时), 就需要解决 hash 冲突. 解决 hash 冲突的方法还是比较多的, 比如说开放定址法, 再哈希法, 链地址法, 公共溢出区等(复习下大学的基本知识).
其中链地址法比较常见, 下面是一个链地址法的常见模式:
Position 指通过 Key 计算出的数组偏移量. 例如当 Position = 6 的位置已经填满 KV 后, 再次插入一条相同 Position 的数据将通过链表的方式插入到该条位置之后.
在 PHP 的 Array 中是这么实现的, golang 中也基本是这么实现. 下面我们学习下 Golang 中 map 的实现.
Golang Map 实现的数据结构
Golang 的 map 中, 首先把 kv 分在了 N 个桶中, 每个桶中的数据有 8 条(bucketCnt). 如果一个桶满了(overflow), 也会采用链地址法解决 hash 的冲突.
下面是定义一个 hashmap 的结构体:
- type hmap struct {
- // 长度
- count int
- // map 的标识, 下方做了定义
- flags uint8
- // 实际 buckets 的长度为 2 ^ B
- B uint8
- // 从 bucket 中溢出的数量,(存在 extra 里面)
- noverflow uint16
- // hash 种子, 做 key 哈希的时候会用到
- hash0 uint32
- // 存储 buckets 的地方
- buckets unsafe.Pointer
- // 迁移时 oldbuckets 中存放部分 buckets 的数据
- oldbuckets unsafe.Pointer
- // 迁移的数量
- nevacuate uintptr
- // 一些额外的字段, 在做溢出处理以及数据增长的时候会用到
- extra *mapextra
- }
- const (
- // 有一个迭代器在使用 buckets
- iterator = 1
- // 有一个迭代器在使用 oldbuckets
- oldIterator = 2
- // 并发写, 通过这个标识报 panic
- hashWriting = 4
- sameSizeGrow = 8
- )
- type mapextra struct {
- overflow *[]*bmap
- oldoverflow *[]*bmap
- nextOverflow *bmap
- }
- type bmap struct {
- tophash [bucketCnt]uint8
- }
表中除了对基本的 hash 数据结构做了定义外, 还对数据迁移, 扩容等操作做了定义, 这里我们可以忽略, 等学习到时我们再深入了解.
深入 桶列表 (buckets)
buckets 字段中是存储桶数据的地方. 正常会一次申请至少 2^N 长度的数组, 数组中每个元素就是一个桶. N 就是结构体中的 B. 这里面要注意以下几点:
为啥是 2 的幂次方 为了做完 hash 后, 通过掩码的方式取到数组的偏移量, 省掉了不必要的计算.
B 这个数是怎么确定的 这个和我们 map 中要存放的数据量是有很大关系的. 我们在创建 map 的时候来详述.
bucket 的偏移是怎么计算的 hash 方法有多个, 在 runtime/alg.go 里面定义了. 不同的类型用不同的 hash 算法. 算出来是一个 uint32 的一个 hash 码, 通过和 B 取掩码, 就找到了 bucket 的偏移了. 下面是取对应 bucket 的例子:
- // 根据 key 的类型取相应的 hash 算法
- alg := t.key.alg
- hash := alg.hash(key, uintptr(h.hash0))
- // 根据 B 拿到一个掩码
- m := bucketMask(h.B)
- // 通过掩码以及 hash 指, 计算偏移得到一个 bucket
- b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
深入 桶 (bucket)
一个桶的示意图如下:
每个桶里面, 可以放 8 个 k,8 个 v, 还有一个 overflow 指针(就是上面的 next), 用来指向下一个 bucket 的地址. 在每个 bucket 的头部, 还会放置一个 tophash, 也就是 bmap 结构体. 这个数组里面存放的是 key 的 hash 值, 用来对比我们 key 生成的 hash 和存出的 hash 是否一致(当然除了这个还有其他的用途, 后面讲数据访问的时候会讲到). tophash 中的数据, 是从计算的 hash 值里面截取的. 获取 bucket 是用的低 bit 位的 hash,tophash 使用的是高 bit 位的 hash 值(8 位)
为啥 bucket 一次要存 8 个 kv, 而不是一个 kv 放一个 bucket, 然后链地址法做处理就 OK 了 据我分析, 有几点原因: a, 一次分配 8 个 kv 的空间, 可以减少内存的分配频次; b, 减少了 overflow 指针的内存占用, 比如说 8 个 kv, 采用一个一个存储的话, 需要 8 * 8B (64 位机) = 64B 的数据存下一个的地址, 而采用 go 实现的这种方式, 只需要 8B + 8B (bmap 的大小) = 16B 的数据就可以了.
为啥需要用 tophash 一般的 hash 实现逻辑是直接和 key 比较, 如果比较成功, 这找到相应 key 的数据. 但是这里用到了 tophash, 好处是可以减少 key 的比较成本(毕竟 key 不一定都是整数形式存在的)
为啥是 8 个 8 * 8B = 64B 整好是 64 位机的一个最小寻址空间, 不过可以通过修改源码自定义吧.
为什么 key 和 val 要分开放 这个也比较好理解, key 和 val 都是用户可以自定义的. 如果 key 是定长的 (比如是数字, 或者 指针之类的, 大概率是这样.) 内存是比较整齐的, 利于寻址吧.
技术总结
golang 实现的 map 比朴素的 hashmap 在很多方面都有优化.
使用掩码方式获取偏移, 减少判断.
bucket 存储方式的优化.
通过 tophash 先进行一次比较, 减少 key 比较的成本.
当然, 有一点是不太明白的, 为啥 overflow 指针要放在 kv 后面? 放在 tophash 之后的位置岂不是更完美?
今天的作业就交完了. 下一篇将学习 golang map 的数据初始化实现.
参考
[1] 深入理解 Go map: 初始化和访问
来源: https://www.cnblogs.com/-lee/p/12777241.html