Golang--map扩容机制（含源码）

1 等量扩容

1.1 触发条件

溢出桶数量过多

• B大于15时，以15计算，如果溢出桶 >= 2^15次方,触发等量扩容
• 当B小于15时，以B计算，如果溢出桶 >= 大于2^B次方，触发等量扩容

1.2 触发结果

新建等量大小的map，将旧数据挪过去

1.3 源码

路径： go1.18/src/runtime/map.go

// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	if B > 15 {
    
		B = 15
	}
	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
	return noverflow >= uint16(1)<<(B&15)
}

2 增量扩容

2.1 触发条件

承载因子>6.5

• 承载因子：map元素总量/bucket数量。
• map元素总量为：hmap中的count。
• bucket数量：2^B

2.2 触发结果

容量翻倍，挪移数据。

2.3 源码

路径： go1.18/src/runtime/map.go

func overLoadFactor(count int, B uint8) bool {
    
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    //人话：当count大于8且承载因子大于6.5时可满足要求
}

count (
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits
    
    loadFactorNum = 13
	loadFactorDen = 2
)

// bucketShift returns 1<<b, optimized for code generation. 
// 翻译，返回2的B次方
func bucketShift(b uint8) uintptr {
    
	// Masking the shift amount allows overflow checks to be elided.
	return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}