原创分享 golang 中 map 的装载因子以及 B 的计算过程

yudotyang · 2021年04月20日 · 62 次阅读

大家好,在上篇文章hash 表在 go 语言中的实现中介绍了下 golang 中 map 的数据结构以及底层的存储逻辑。 在介绍数据结构的时候,其中 hmap 中有一个重要的字段:B。我们知道 B 值是用来确定 buckets 数组大小的。那么,在用 make 初始化一个 map 的时候,B 值是怎么计算的呢?本文就来介绍下 B 值的计算逻辑。

什么是负载因子

负载因子是衡量 hash 表中当前空间占用率的指标。在 go 中,就是平均每个 bucket 存储的元素个数。

计算公式如下: LoadFactor(负载因子)= hash 表中已存储的键值对的总数量/hash 桶的个数(即 hmap 结构中 buckets 数组的个数)

在各语言的实现中,都会确定一个负载因子的阈值,当负载因子超过这个阈值时,就要进行扩容,以平衡存储空间和查找元素时的性能。

以下是 go 语言中给出各负载因子下的测试表。

loadFactor %overflow bytes/entry hitprobe missprobe
4.00 2.13 20.77 3.00 4.00
4.50 4.05 17.30 3.25 4.50
5.00 6.85 14.77 3.50 5.00
5.50 10.55 12.94 3.75 5.50
6.00 15.27 11.67 4.00 6.00
6.50 20.90 10.79 4.25 6.50
7.00 27.14 10.15 4.50 7.00
7.50 34.03 9.73 4.75 7.50
8.00 41.10 9.40 5.00 8.00
  • %overflow = percentage of buckets which have an overflow bucket
  • bytes/entry = overhead bytes used per key/elem pair
  • hitprobe = # of entries to check when looking up a present key
  • missprobe = # of entries to check when looking up an absent key

根据上面的测试数据,go 中 map 的负载因子被硬性的定为了 6.5,即平均每个 bucket 存储的 key/value 对大于等于 6.5 个的时候,就会进行扩容。

hmap 中的 B 值的初始化计算

初始化 map 空间的时候,我们通过 make 可以指定元素的个数.如下,初始化一个能包含 16 个元素大小的 map:

m := make(map[string]int, 16)

那么,在 hmap 中的 B 值是如何计算的呢? 我们由上一篇文章可知,在 hmap 中,buckets 数组的元素数=2^B 次方。 map 的负载因子≥6.5 时会自动扩容。 当前 map 的 key/value 元素数量为 16。那计算 B 就变成了以下逻辑:

元素个数为 16 的情况下,分配几个 bucket 才能满足负载因子<6.5

即以下公式:

元素个数/bucket数量 ≤ 6.5

进一步演变成以下公式

元素个数 ≤ bucket数量*6.5

将 bucket 数量=2^B 次方带入以上公式,则最终的公式为:

初始元素个数 ≤ 2^B * 6.5

当初始元素个数为 16 时,上述公式为:

16 ≤ 2^B * 6.5

那么,让 B 从 0 开始依次递增,直到遇到让该公式成立的最小 B 值即可。 下面咱们一起来推导:

B 值 不等式 不等式是否成立
0 16 ≤ 2^0 * 6.5 => 16 ≤ 6.5 不成立,B 递增 1
1 16 ≤ 2^1 * 6.5 => 16 ≤ 13 不成立,B 递增 1
2 16 ≤ 2^2 * 6.5 => 16 ≤ 26 成立,B 结束递增

由此可知,当初始元素个数为 16 时,B 为 2,则计算出 bucket 的数量为 2^2 次方,为 4 个 bucket。

下面来看看 go 的源代码的实现:

通过源代码我们可知在 makemap 函数中,计算 B 的代码如下:

B := uint8(0)
for overLoadFactor(hint, B) {
    B++
}
h.B = B

而 overLoadFactor 函数如下

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

再来看 bucketShift 函数的实现:

func bucketShift(b uint8) uintptr {
    return uintptr(1) << (b && (sy 1.PtrSize*8 -1))
}

总结

根据 golang 团队的测试数据,将负载因子定为了 6.5,即平均每个 bucket 保存的元素≥6.5 个时会触发扩容。所以,在初始化 map 时,元素个数确定的情况下,计算 B 值,就转变成至少分配几个 bucket,能使当前的负载因子不超过 6.5。再根据 buckets 数组的个数=2^B 次方计算可得 B 值。

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册