Golang -- map capacity expansion mechanism (including source code)

1 Expand capacity equally

1.1 The trigger condition

There are too many overflowing barrels

• B Greater than 15 when , With 15 Calculation , If the bucket overflows >= 2^15 Power , Trigger equal expansion
• When B Less than 15 when , With B Calculation , If the bucket overflows >= Greater than 2^B Power , Trigger equal expansion

1.2 Trigger result

Create a new one of the same size map, Move the old data

1.3 Source code

route ： go1.18/src/runtime/map.go

// overflow buckets  Too much 
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 Incremental capacity expansion

2.1 The trigger condition

Load factor >6.5

• Load factor ：map Total elements /bucket Number .
• map The total amount of elements is ：hmap Medium count.
• bucket Number ：2^B

2.2 Trigger result

Capacity to double , Move data .

2.3 Source code

route ： go1.18/src/runtime/map.go

func overLoadFactor(count int, B uint8) bool {
    
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    // People words ： When count Greater than 8 And the bearing factor is greater than 6.5 It can meet the requirements 
}

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

// bucketShift returns 1<<b, optimized for code generation. 
//  translate , return 2 Of B Power 
func bucketShift(b uint8) uintptr {
    
	// Masking the shift amount allows overflow checks to be elided.
	return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}