大家好，在上篇文章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值。
有疑问加站长微信联系（非本文作者）
