golang 中 map 的装载因子以及 B 的计算过程

yudotyang · · 4284 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

大家好,在上篇文章[hash 表在 go 语言中的实现](https://gocn.vip/topics/11937)中介绍了下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: ```go 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的代码如下: ```go B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B ``` 而 overLoadFactor函数如下 ```go func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum * (bucketShift(B)/loadFactorDen) } ``` 再来看bucketShift函数的实现: ```go 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值。

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4284 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传